Advanced Concurrency Topic:
Runtime Deadlock Detection I

Heteroclinic.net logo

www.heteroclinic.net

There seems to be something wrong with this project, further study goes to Treetor/jdfr bundle. -- 20130702

Deadlock can be a nightmare, but when it happens, we may not notice it. It may be burried deep in the vast quantity of process/thread instances. Nothing is shown in the GUI, nothing is written in your log. Some programs may behave strangely, you may notice or not. We did some experiments, code hacking. Finally, under the very limited conditions of our experiment, we found such deadlocks are detect-able. Thus, we may provide some remedy. Our knowledge and understanding may be partial, in-complete even wrong. Please do not hesitate to point out them.

Here we choose Java because Java is so convenient to deploy such an application. Other programming languages should be sufficient too. Our mission is to study/understand the deadlock phenomenon not to debate the features of different languages.

The beginning part requires you set up the following Java program in a same package. For convenience, I used the latest JDK and the latest Eclipse IDE.

Util.java

Indy.java

FindRaceCondition.java

By change the two lines in `FindRaceCondition.java', we did some experiments.

Finally when we set

The deadlock is almost certain to happen. Please notice we say almost. In concurrency programming, nothing is certain (but statistically high probability).

Advanced Concurrency Topic:
Runtime Deadlock Detection II
Now we put two new files, if you change the value of the last argument of ThrottledIndy's constructor in file `DeadlockThrottle.java'. You will see deadlock may not be certain. Our experiments shows another mis-understanding that even every method is synchronized, it is still not safe -- at least, deadlock may happen.

DeadlockThrottle.java

ThrottledIndy.java

Here are the results that are not certain:

Advanced Concurrency Topic:
Runtime Deadlock Detection III
We found Indies like to be alone almost all the time, otherwise, the results are really unpredictable or not what we want. So we design a class Duo. First, Duos should be able to do Indy's job. We also put class Resource to a separate file. The experiments is executed from the main of `TestDuoDeadlockableVersion.java'. You will find Duo behave the same as Indy.

Duo.java

Resource.java

TestDuoDeadlockableVersion.java

Advanced Concurrency Topic:
Runtime Deadlock Detection IV
DeadlockException
We did a lot of code hacking to simulate the intrinsic lock of Java Object class. The final result is under our confining box, deadlock is detected, and the late thread yield the resource to the early thread. Please note there may be implementation that is wrong, you can find the remarks I put.

After we give some training to Duos, it seem they are able to handle a situation we don't want to get into. Please notice the difference of Duo and TrainedDuo. The parameter in duowait(long) for example, is 0 for Duo, value greater than 1 for TrainedDuo. Finally, we want to talk something about topology. Topology is not a secret world jargon. It simply means the way to represent connections of different entities in a space. I once try to do some visualization. We have thread, resource, and time. It is a three-dimensional world thus the diagram is not easy to plot. However, if you deal with computer graphics, you won't be strange to edge pair. With the aiding of edge pairs, we can traverse a connected simplex, may we call it a manifold.

The starting function main is in file `TestTrainedDuo.java'.

A result that is still not certain to get

DeadlockException.java

TrainedDuo.java

TestTrainedDuo.java

Advanced Concurrency Topic:
Runtime Deadlock Detection V
Using Graph Theory to Analyze and Detect Deadlock 1/4
Introduction

GraphAnalysisofDeadlockDetection.pdf

So far in our coding project, we tried to produce deadlock, detected it and improvised some exception handling. In this article, we use very basic graph theory knowlege to explain our approach. This article is not peer reviewed. The previous coding projects are not peer reviewed either. If you have any comments or want to point out any errors, please contact the author. In the following section, we try to formalize our approach by giving an algorithm. By doing so, we are not limited to the confining box of a particular programming language.

An Algorithm for Runtime Deadlock Detection
First, we set some pre-requisites. A thread can be considered as a process. A resource can be considered as an object for some particular language.
- A thread has a unique ID.
- For all threads, each of them has a data structure of the resources it locks.
- Each resource also has a unique ID.
- A thread can indicate its status, e.g., waiting status. Other threads can read its status. This thread records the resource it is waiting for.
- A thread can lock multiple resources.
- A resource can be locked by only one thread. Each resource has a data structure recording which thread is holding the lock of this resource. It is well-known, or desired if not, that each resource knows the thread tries to enter waiting status for this resource.

210208pic001algorithm.jpg


It will be an ideal situation that all the threads involved won't change their status, or, the operation of the above algorithm be atomic. All threads involved should be in waiting status. It is obvious their status, if changed, will release more resources for the whole system and improve the situation. We also assume there is no signal missing, which in practice can be handled by time-out waiting and poll resource status boolean.
In the following sections, we are going to use very basic graph theory to analyze deadlock and the approach we take in this article and previous coding project.
Advanced Concurrency Topic:
Runtime Deadlock Detection VI
Using Graph Theory to Analyze and Detect Deadlock 2/4
Deadlock fomation

210208pic002dlform01.jpg

210208pic003dlform02.jpg

210208pic004dlform03.jpg

210208pic005dlform04.jpg

210208pic006dlform05.jpg

210208pic007dlform06.jpg


We use the Figure.(1) to Figure.(6) to show how deadlock is formed. These diagrams are quite self-explaining. Please stare at these diagrams for some minutes to see if there are some hidden messages. Now we raise some very very basic questions related to graph theory. Please notice we emphasize there is no advanced graph thoery knowledge involved!
First, what type of graph are these graphs?
Second, does graph in Figure.(6) provide enough information about deadlock formation?
Third, what is wrong or in-sufficient, of the graph in Figure.(6) in detecting deadlock?
Advanced Concurrency Topic:
Runtime Deadlock Detection VII
Using Graph Theory to Analyze and Detect Deadlock 3/4
Deadlock evasion
The graph show in Figure.(6) is a directed graph. It does show the information about the the formation of a deadlock. But for such directed graph, it is not connected. We can find two isolated parts. Simply put, starting from any node, we can not traverse the whole graph. So we understand deadlock for a system happens because we can not capture a whole picture of all the nodes involved. So we have to revise the system's architecture so a topological structure can navigate the confused threads like a lighthouse or the traffic signals. Now, we present the approach we take in our previous coding projects.
For a healthy system without deadlock yet, the hazard is raised when a running thread tries to acquire the resource already locked by another thread. To enter waiting status is still safe, when the threads resources dependency graph does not form a closed chain. Our threads/resources topological structure will provide sufficient information such that before a thread enters into waiting, deadlock can be detected.
Figure.(7) to Figure.(12) show exactly what we did in our previous coding project and what we propose and formalize as an algorithm in this article.

210208pic008evasion01.jpg

Fig. 7 Threads attempting resources.

210208pic009evasion02.jpg

Fig. 8 Resources locked, but we have bi-directional edges.

210208pic010evasion03.jpg

Fig. 9 $T_2$ attempting $R_1$.

210208pic011evasion04.jpg

Fig. 10 $T_2$ waiting (for $R_1$).

210208pic012evasion05.jpg

Fig. 11 $T_1$ attempting $R_2$, but $T_1$ has sufficient information about the local ecological chain. Namely, $T_1$ can traverse the graph with all the nodes involved.

210208pic013evasion06.jpg

Fig. 12 In our approach, the late thread yields to the early thread. So $T_1$ releases $R_1$. $T_2$ revives. The global system stays healthy.
Advanced Concurrency Topic:
Runtime Deadlock Detection VIII
Using Graph Theory to Analyze and Detect Deadlock 4/4
Discussion
Now we consider a more complex situation. The coding project of this situation can be a good assignment. The dining philosopher problem can also be an example to practice the algorithm we propose.
In the threads/resources lock/wait chain, if the last thread is running, so we consider such a system is health. The last thread is running, then the system has a {\it hope}. There will be the chance that the running thread finishes and releases some locks so other waiting thread(s) may be revived.\\ Figure.(13) shows the initial state of the eco-system (local). $T_3$ is the hope of the system. When it finishes, it will release critical resource. The system will get a new hope and keep fit. In Figure.(14), $T_3$ is attempting $R_3$. But according to the established rule, it must yield to avoid deadlock. In Figure.(15), $T_3$ yielded and $T_2$ becomes the new hope of the system.
We make a metaphor here. In the highway, the administration may deploy patrols densely so every vehicle is under constant surveillance. This is like running a monitoring thread. In our approach, we train the drivers to follow the well-know traffic rules and also make sure they know how to check signals from others and signal their own intention to the others properly.

210208pic014complex01.jpg

210208pic015complex02.jpg

210208pic016complex03.jpg