Menu
This is an interview question.
How to detect and find out if a program is in deadlock? Are there some tools that can be used to do that on Linux/Unix systems?
My idea:
If a program makes no progress and its status is running, it is deadlock. But, other reasons can also cause this problem. Open source tools are valgrind (halgrind) can do that. Right?
232
With the help of the resource allocation graph, the OS can detect deadlocks. If a cycle forms in a system with single instanced resource types, there will undoubtedly be a deadlock. Detecting a cycle, on the other hand, is insufficient in a graph of the multiple instanced resource type.
The OS can detect the deadlocks with the help of Resource allocation graph. In single instanced resource types, if a cycle is being formed in the system then there will definitely be a deadlock. On the other hand, in multiple instanced resource type graph, detecting a cycle is not just enough.
One method to detect deadlock is to construct a resource requirement graph for shared resources. Suppose system created 2 threads Ta and Tb, both Ta and Tb requires resource Ra and Rb. If Ta has acquired Ra, and is requiring Rb, this can be like a directed graph: Ra->Ta->Rb.
Wait for Graph This is the suitable method for deadlock detection. In this method, a graph is created based on the transaction and their lock. If the created graph has a cycle or closed loop, then there is a deadlock.
If you suspect a deadlock, do a ps aux | grep <exe name>, if in output, the PROCESS STATE CODE is D (Uninterruptible sleep) means it is a deadlock.
Because as @daijo explained, say you have two threads T1 & T2 and two critical sections each protected by semaphores S1 & S2 then if T1 acquires S1 and T2 acquires S2 and after that they try to acquire the other lock before relinquishing the one already held by them, this will lead to a deadlock and on doing a ps aux | grep <exe name>, the process state code will be D (ie Uninterruptible sleep).
Tools:
Valgrind, Lockdep (linux kernel utility)
Check this link on types of deadlocks and how to avoid them : http://cmdlinelinux.blogspot.com/2014/01/linux-kernel-deadlocks-and-how-to-avoid.html
Edit: ps aux output D "could" mean process is in deadlock, from this redhat doc:
Uninterruptible Sleep State
An Uninterruptible sleep state is one that won't handle a signal right away. It will wake only as a result of a waited-upon resource becoming available or after a time-out occurs during that wait (if the time-out is specified when the process is put to sleep).
55
I would suggest you look at Helgrind: a thread error detector.
The simplest example of such a problem is as follows.
Imagine some shared resource R, which, for whatever reason, is guarded by two locks, L1 and L2, which must both be held when R is accessed.
Suppose a thread acquires L1, then L2, and proceeds to access R. The implication of this is that all threads in the program must acquire the two locks in the order first L1 then L2. Not doing so risks deadlock.
The deadlock could happen if two threads -- call them T1 and T2 -- both want to access R. Suppose T1 acquires L1 first, and T2 acquires L2 first. Then T1 tries to acquire L2, and T2 tries to acquire L1, but those locks are both already held. So T1 and T2 become deadlocked."
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
