The Deadly Question!

One of my favorite questions that I ask during an interview is "What is a deadlock and how do you avoid them?"

Typical answers:

Definition: Deadlock happens when Object 1 is waiting for Object 2 which is waiting for Object 1 again.

Avoiding deadlocks: (Answer 1): Using wait & notify. (Answer 2): Using synchronization.

Not only is the terminology wrong, it also clearly shows that the candidate is not sure with the fundamentals of multi-threading. To be frank, I was asked the same question when I was interviewed and I wasn't able to give a proper answer even though I did good amount of multi-threading before to answer this innocent looking question.

Lets suppose there are two threads T1, and T2 running in your application. T1 is executing a method called method1() and T2 is executing method2(). method1() has acquired lock1 and now it is trying to acquire lock2. But at the same time, method2() has acquired lock2 and it is now trying to acquire lock1. method1() cannot relinquish lock1 until it gets lock2 and finishes the job; method2() cannot relinquish lock2 until it gets lock1 and finishes the job. Both the threads, T1 and T2, are now waiting for one another to proceed their execution which will never happen. This situation is called a deadlock or a deadly embrace.

See the following code that is almost sure to encounter a deadlock during it's execution.

public class DeadLockDemo {
private Object lock1 = new Object();
private Object lock2 = new Object();

public void method1() {
while (true) {
// Acquire lock1 first
synchronized (lock1) {
// Acquire lock2 next
synchronized (lock2) {
System.out.println("Method 1");
}
}
}
}

public void method2() {
while (true) {
// Acquire lock2 first
synchronized (lock2) {
// Acquire lock1 next
synchronized (lock1) {
System.out.println("Method 2");
}
}
}
}

public static void main(String[] args) {
final DeadLockDemo deadLockDemo = new DeadLockDemo();
Thread thread1 = new Thread() {
public void run() {
deadLockDemo.method1();
}
};

Thread thread2 = new Thread() {
public void run() {
deadLockDemo.method2();
}
};

thread1.start();
thread2.start();
}
}

How do we avoid this deadlock here? The typical answers like "synchronizing" the code doesn't solve the problem. Actually, deadlock happens because of improper synchronization. The answer is very simple though. Always acquire the locks in the same order. That is, acquire lock1 and then lock2 or lock2 and then lock1. Yes, it's as simple as that. You can try running the code and check it for yourself.

Till then, happy multi-threading!
Srikanth