Understanding why deadlock happens in this implementation

Question

I am new to multithreading, and I came across this example:

public class TestThread {
   public static Object Lock1 = new Object();
   public static Object Lock2 = new Object();

   public static void main(String args[]) {

      ThreadDemo1 T1 = new ThreadDemo1();
      ThreadDemo2 T2 = new ThreadDemo2();
      T1.start();
      T2.start();
   }

   private static class ThreadDemo1 extends Thread {
      public void run() {
         synchronized (Lock1) {
            System.out.println("Thread 1: Holding lock 1...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 1: Waiting for lock 2...");
            synchronized (Lock2) {
               System.out.println("Thread 1: Holding lock 1 & 2...");
            }
         }
      }
   }
   private static class ThreadDemo2 extends Thread {
      public void run() {
         synchronized (Lock2) {
            System.out.println("Thread 2: Holding lock 2...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 2: Waiting for lock 1...");
            synchronized (Lock1) {
               System.out.println("Thread 2: Holding lock 1 & 2...");
            }
         }
      }
   } 
}

This causes the following sample output:

Thread 1: Holding lock 1...
Thread 2: Holding lock 2...
Thread 1: Waiting for lock 2...
Thread 2: Waiting for lock 1...

i.e, there is a deadlock. However, if we change the order of locks obtained in the second thread so that it looks like this now:

public class TestThread {
   public static Object Lock1 = new Object();
   public static Object Lock2 = new Object();

   public static void main(String args[]) {

      ThreadDemo1 T1 = new ThreadDemo1();
      ThreadDemo2 T2 = new ThreadDemo2();
      T1.start();
      T2.start();
   }

   private static class ThreadDemo1 extends Thread {
      public void run() {
         synchronized (Lock1) {
            System.out.println("Thread 1: Holding lock 1...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 1: Waiting for lock 2...");
            synchronized (Lock2) {
               System.out.println("Thread 1: Holding lock 1 & 2...");
            }
         }
      }
   }
   private static class ThreadDemo2 extends Thread {
      public void run() {
         synchronized (Lock1) {
            System.out.println("Thread 2: Holding lock 1...");
            try { Thread.sleep(10); }
            catch (InterruptedException e) {}
            System.out.println("Thread 2: Waiting for lock 2...");
            synchronized (Lock2) {
               System.out.println("Thread 2: Holding lock 1 & 2...");
            }
         }
      }
   } 
}

It works as expected, and a sample output looks like this:

Thread 1: Holding lock 1...
Thread 1: Waiting for lock 2...
Thread 1: Holding lock 1 & 2...
Thread 2: Holding lock 1...
Thread 2: Waiting for lock 2...
Thread 2: Holding lock 1 & 2...

Can someone explain to me what is happening in the first one that is causing the deadlock, and why does the change in second code fix it?

Answer 1

Here's a possible scenario for the first case:

Thread 1 acquires Lock1 and goes to sleep for 10 milliseconds. Now Thread 2 acquires Lock2 and goes to sleep for 10 milliseconds.

Now Thread 1 tries to acquire Lock2, but can't get it since it's acquired by Thread 2, while Thread 2 tries to get Lock1 which is locked by Thread 1.

In the second case, let's assume the first thread is picked to run. It gets Lock1, while the other thread is blocked because it's trying to get Lock1 as well. Now thread 1 goes to sleep, and proceed to the second (nested) synchronized block. It tries to get it (because it's still free) - now he got 2 locks. The other thread is still blocked.

Only after it finishes execution, it releases both locks (since it exit the synchronized block), and now the JVM is free to decide which thread to pick, but it doesn't really matter, the same logic happens.

Answer 2

What you see here is lock ordering, a common method for deadlock prevention.

In your first case, consider the following order of execution with the current instruction pointers located at the marked location for each thread:

  Thread 1:
     obtain lock 1
===>
     obtain lock 2
  Thread 2:
     obtain lock 2
===>
     obtain lock 1

Now, thread 1 tries to obtain lock 2 next, but cannot as lock 2 is held by thread 2. And thread 2 tries to obtain lock 1 next, but cannot, because it is held by thread 1. This is a classical circular resource dependency and hence results in deadlock.

A global method to prevent this is to make sure all locks have a total order and locks are always acquired in that total order.

The proof that this works is trivial: Because all lock dependencies are "downward" in the total order, you cannot have lock cycles.