Example
A deadlock occurs when every member of some group of two or more threads must wait for one of the other members to do something (e.g., to release a lock) before it can proceed. Without intervention, the threads will wait forever.
A pseudocode example of a deadlock-prone design is:
thread_1 {
acquire(A)
...
acquire(B)
...
release(A, B)
}
thread_2 {
acquire(B)
...
acquire(A)
...
release(A, B)
}
A deadlock can occur when thread_1 has acquired A, but not yet B, and thread_2 has acquired B, but not A. As shown in the following diagram, both threads will wait forever.
How to Avoid Deadlocks
As a general rule of thumb, minimize the use of locks, and minimize code between lock and unlock.
Acquire Locks in Same Order
A redesign of thread_2 solves the problem:
thread_2 {
acquire(A)
...
acquire(B)
...
release(A, B)
}
Both threads acquire the resources in the same order, thus avoiding deadlocks.
This solution is known as the "Resource hierarchy solution". It was proposed by Dijkstra as a solution to the "Dining philosophers problem".
Sometimes even if you specify strict order for lock acquisition, such static lock acquisition order can be made dynamic at runtime.
Consider following code:
void doCriticalTask(Object A, Object B){
acquire(A){
acquire(B){
}
}
}
Here even if the lock acquisition order looks safe, it can cause a deadlock when thread_1 accesses this method with, say, Object_1 as parameter A and Object_2 as parameter B and thread_2 does in opposite order i.e. Object_2 as parameter A and Object_1 as parameter B.
In such situation it is better to have some unique condition derived using both Object_1 and Object_2 with some kind of calculation, e.g. using hashcode of both objects, so whenever different thread enters in that method in whatever parametric order, everytime that unique condition will derive the lock acquisition order.
e.g. Say Object has some unique key, e.g. accountNumber in case of Account object.
void doCriticalTask(Object A, Object B){
int uniqueA = A.getAccntNumber();
int uniqueB = B.getAccntNumber();
if(uniqueA > uniqueB){
acquire(B){
acquire(A){
}
}
}else {
acquire(A){
acquire(B){
}
}
}
}
