Understanding why deadlock occurs in this implementation

Question

I'm 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 will lead to the following conclusion:

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

ie, there is a dead end. However, if we change the order of the locks received in the second thread, so now it looks like this:

 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 the sample result is as follows:

 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 happens in the first one, which causes a dead end, and why can I fix the change in the second code?

Answer 1

Here's a possible scenario for the first case:

Thread 1 receives Lock1 and goes into sleep mode for 10 milliseconds. Thread 2 now receives Lock2 and goes to sleep for 10 milliseconds.

Now Thread 1 is trying to get Lock2 , but cannot get it from the moment it was received in Thread 2, and Thread 2 is trying to get Lock1 , which is blocked by Thread 1.

In the second case, suppose that the first thread is selected to run. It gets Lock1 , and the other thread is blocked because it is trying to get Lock1 . Now thread 1 goes into sleep mode and goes to the second (nested) synchronized block. He is trying to get it (because he is still free) - now he got locks 2 . Another thread is still blocked.

Only after completion of execution does it release the locks and (since it exits the synchronized block), and now the JVM can decide which thread to choose, but it does not really matter, does the same logic happen.

Answer 2

What you see here is locking ordering, a common method to prevent locking.

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

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

Now thread 1 is trying to get lock 2 nearby, but cannot, because lock 2 is held by thread 2. And thread 2 is trying to get lock 1 further, but cannot, because it is held by thread 1. This is a classic circular resource dependency and therefore leads to a deadlock.

A global method to prevent this is to make sure that all locks are in common order and that locks are always acquired in that general order.

The proof that this works is trivial: since all locks are down-dependent in the general order, you cannot lock loops.

Answer 3

Well, in your first code snippet, the first thread holds Lock1 , and the second holds Lock2 , obviously. Then they try to grab locks for each other, but they fail because the other locks are already held by another thread, which creates a deadlock.

In the second part of the code, however, the second thread does not hold Lock2 and locks out of nothing until the first thread releases the first lock. The first thread will release the first lock after it also grabs the second, as you can see from your output.