CODEWITHSUNDEEP
javamultithreadingconcurrencydeadlock
NedStarkOfWinterfell
NedStarkOfWinterfell

Reputation: 5153

Understanding why deadlock happens in this implementation

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?

Upvotes: 8

Views: 179

Answers (3)

Maroun
Maroun

Reputation: 95948

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.

Upvotes: 5

dhke
dhke

Reputation: 15388

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.

Upvotes: 2

Idos
Idos

Reputation: 15310

Well in your first piece of code the first thread is holding Lock1 and the second is holding Lock2 obviously. Then they try to grab each other's locks but they fail because the other locks are already being held by the other thread so a deadlock is created.

In the second piece of code however, the second thread isn't holding Lock2 and is blocked out of anything until the first thread releases the first lock. The first thread will release the first lock after it also grabs the second one, as seen by your output.

Upvotes: 1

Related Questions