Deadlock

A deadlock is when two or more threads are blocked waiting to obtain locks that some of the other threads in the deadlock are holding. Deadlock can occur when multiple threads need the same locks, at the same time, but obtain them in different order.

This can be easily explained with an example

public class Deadlock {

	public static void main(String args[]) {
		String name1 = "one";
		String name2 = "two";
		Thread t1 = new Thread(() ->{ printNames(name1, name2);});
		t1.start();
		//change the order of names
		Thread t2 = new Thread(() ->{ printNames(name2, name1);});
		t2.start();
	}
	public static void printNames(String name1, String name2) {
		System.out.println(Thread.currentThread().getName() + " Acquiring lock for - " + name1);
		synchronized (name1) {
			System.out.println(Thread.currentThread().getName() + " Acquired lock for - " + name1);
			try {
				Thread.sleep(10);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			System.out.println(Thread.currentThread().getName() + " Acquiring lock for - " + name2);
			synchronized (name2) {
				System.out.println(Thread.currentThread().getName() + " Acquired lock for - " + name1);
				System.out.println(Thread.currentThread().getName() + " print both names: " + name1 + " " + name2);
			}
		}
	}
}
Thread-0 Acquiring lock for - one
Thread-0 Acquired lock for - one
Thread-1 Acquiring lock for - two
Thread-1 Acquired lock for - two
Thread-0 Acquiring lock for - two
Thread-1 Acquiring lock for - one

The above program may not terminate most of the time. If above example Thread-0 acquired the lock on one and went to sleep. During that time Thread-1 acquired the lock on two and went to sleep. Note: The order in which thread wakes up may not be consistent all the time. Let's consider that Thread-0 wakes up and went to acquire lock two, it has to wait for Thread-1. Similarily when Thread-1 wakes up it would need to wait for acquiring lock on one. Now we have a situation where both the threads are in WAITING state and program freezes and will not terminate.

This is one of the simpler example detailing about the deadlock occurence. In production systems it is difficult to look over code and identify deadlock issues. Most of the time one need to take thread dump of the system at hung state using tools like jstack and look at the state of Thread running on the JVM instance.

Deadlock Prevention

In some situations it is possible to prevent deadlocks

Lock Ordering

Deadlock occurs when multiple threads need the same locks but obtain them in different order. If you make sure that all locks are always taken in the same order by any thread, deadlocks cannot occur.

Thread 1:

  lock A 
  lock B


Thread 2:

   wait for A
   lock C (when A locked)


Thread 3:

   wait for A
   wait for B
   wait for C

If a thread, like Thread 3, needs several locks, it must take them in the decided order. It cannot take a lock later in the sequence until it has obtained the earlier locks. For instance, neither Thread 2 or Thread 3 can lock C until they have locked A first. Since Thread 1 holds lock A, Thread 2 and 3 must first wait until lock A is unlocked. Then they must succeed in locking A, before they can attempt to lock B or C.

Lock ordering is a simple yet effective deadlock prevention mechanism. However, it can only be used if you know about all locks needed ahead of taking any of the locks. This is not always the case.

Lock Timeout

Another deadlock prevention mechanism is to put a timeout on lock attempts meaning a thread trying to obtain a lock will only try for so long before giving up. If a thread does not succeed in taking all necessary locks within the given timeout, it will backup, free all locks taken, wait for a random amount of time and then retry. The random amount of time waited serves to give other threads trying to take the same locks a chance to take all locks, and thus let the application continue running without locking.


Recommend Reading

  1. How java manages Memory?
  2. Why is it advised to use hashcode and equals together?
  3. Comparable and Comparator in java
  4. How to create Singleton class in Java?
  5. Difference between equals and ==?
  6. When to use abstract class over interface?
  7. Difference between final, finally and finalize
  8. Why is it recommended to use Immutable objects in Java