Understanding and Terminating the Enemy- Deadlocks

Concurrent programming is hard. And its even hard when you do it badly. Deadlocks are one of the classical enemies you must try to avoid when writing a concurrent program. Because if you face any deadlocks in your program its really hard to find and fix them.

In this post i’m trying to explain what deadlocks are and I’ll explain how to debug a program to find and fix deadlocks.

There are different definitions for deadlock personally i prefer the following definition since i feel its the perfect one.

“A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause (including itself)” [1]

There are four necessary conditions to be there in a program if its leading to a deadlock. Which means if a program ended up in a deadlock state it that program will satisfy following four conditions.

1. Mutual exclusion : The resources that must involve in the problem must only have mutually exclusive access. Which means only an one thread/ process can have the access to the resources at one time.
2. Hold and wait : There are threads / processors that hold resource/s and wait for another.
3. Non preemptive - The resources that are held by one processes can’t be forcefully released.
4. Circular wait condition : The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list

There will be no deadlocks in a program if it does not satisfy all these conditions .

I’ll explain a simple programming example that will demonstrate a simple deadlock.

public class Resource {



private Object lockA = new Object();



private Object lockB = new Object();





public void accessA() {

  synchronized (lockA) {



      //Access resource A

      System.out.println("GOT A waiting for B");

      synchronized (lockB) {

          //Access resource B

      }



  }

  System.out.println("Done accessA");

}



public void accessB() {

  synchronized (lockB) {

      //Access resource B

      System.out.println("GOT B waiting for A");

      synchronized (lockA) {

          //Access resource A

      }

  }

  System.out.println("Done accessB");

}

}

Look at the above Resource class. It got two public methods accessA and accessB. and two locks that protect resources A and resource B from accessing them in parallel.

if two threads try to invoke this two methods in parallel there can be a deadlock scenario where thread 1 will get the lock for A and waiting for B without releasing the lock for A and other thread will get lock for B and wait for the lock for A. This is the simplest scenario that a deadlock can happen between two threads.


If we look at the program you can see all the necessary conditions are satisfied by that program.

1. Mutual exclusion : resource A and B are Mutual exclusive resources ( Only one thread can access a resource at one time).
2. Hold and wait : The threads that invoke accessA and accessB methods will hold one resource and wait for another.
3. Non preemptive : In this program there is not way for us to signal a thread to release a resource forcefully.
4. Circular wait condition : thread1 <-> thread2
   

Now lets look at how we can eliminate deadlocks. I do not think there is such mechanical way to remove deadlocks from programs. And some times we will have to understand the lock access order of the program and change them in a such a way that they won’t endup in a cycle/s.If its not possible one thing we can do is track the lock order and detect possible deadlocks and forcefully terminate that thread or resource access.(Preemption)

When writing a complex concurrent program with lot of locks its hard to keep track of the lock order. So identifying possible deadlocks in program can be really useful when writing complex program. And it will be a great advantage if we can have a tool that can be used to identify possible deadlocks. I came across this tool JCarder[2] which i find really useful when analyzing programs for deadlocks. And the major advantage i see here is i could integrate it with integration tests.


JCarder detect possible deadlocks by instrumenting programs byte code and tracking the lock order in runtime. Which means it may not detect all the deadlocks in your program as a given execution will not cover all the code.

you can run your program with jcarder by passing vm parameter -javaagent:path/to/jcarder.jar

ex :

java -javaagent:path/to/jcarder.jar -jar yourprogram.jar

Then when your program executes jcarder will dump logs to a file which can be used later to analyze the deadlocks.

Then you can stop the program when you want and run the analyzer with command

java -jar jcarder.jar

Following is the report i got when i execute the above explained program.

Loaded from database files:

Nodes: 2

Edges: 2 (excluding 0 duplicated)



Cycle analysis result:

Cycles:          1

Edges in cycles: 2

Nodes in cycles: 2

Max cycle depth: 2

Max graph depth: 2



Ignoring 0 gated cycle(s).

Ignoring 0 almost identical cycle(s).

Finally if deadlocks are found it will generate a .dot file which can be visualized using dotty

ex :
$dotty jcarder_result_0.dot
or
$dot -T png -o example.png jcarder_result_0.dot


Following is the output i got for my program which clearly shows the deadlock.




Deadlocks are hard to debug and terminate so its always better to write programs carefully so that there won’t be any deadlocks :)


[1]http://homepages.uel.ac.uk/u0214248/Harriet3.htm
[2]http://www.jcarder.org/