Write a program that will surely go into deadlock [closed]
I recently got this questions asked in an interview.
I answered that deadlock occurs if the interleaving goes wrong, but the interviewer insisted that a program that will always go into deadlock regardless of interleaving can be written .
Can we write such a program ? Can you point me to some example program like that ?
UPDATE: This question was the subject of my blog in January 2013. Thanks for the great question!
How can we write a program that will always go into deadlock no matter how the threads are scheduled?
Here's an example in C#. Note that the program appears to contain no locks and no shared data. It has only a single local variable and three statements, and yet it deadlocks with 100% certainty. One would be hard-pressed to come up with a simpler program that deadlocks with certainty.
Exercise to the reader #1: explain how this deadlocks. (An answer is in the comments.)
Exercise to the reader #2: demonstrate the same deadlock in Java. (An answer is here: https://stackoverflow.com/a/9286697/88656)
class MyClass
{
static MyClass()
{
// Let's run the initialization on another thread!
var thread = new System.Threading.Thread(Initialize);
thread.Start();
thread.Join();
}
static void Initialize()
{ /* TODO: Add initialization code */ }
static void Main()
{ }
}
The latch here ensure that both locks are held when each thread tries to lock the other:
import java.util.concurrent.CountDownLatch;
public class Locker extends Thread {
private final CountDownLatch latch;
private final Object obj1;
private final Object obj2;
Locker(Object obj1, Object obj2, CountDownLatch latch) {
this.obj1 = obj1;
this.obj2 = obj2;
this.latch = latch;
}
@Override
public void run() {
synchronized (obj1) {
latch.countDown();
try {
latch.await();
} catch (InterruptedException e) {
throw new RuntimeException();
}
synchronized (obj2) {
System.out.println("Thread finished");
}
}
}
public static void main(String[] args) {
final Object obj1 = new Object();
final Object obj2 = new Object();
final CountDownLatch latch = new CountDownLatch(2);
new Locker(obj1, obj2, latch).start();
new Locker(obj2, obj1, latch).start();
}
}
Interesting to run jconsole, which will correctly show you the deadlock in the Threads tab.
Deadlock happens when threads (or whatever your platform calls its execution units) acquire resources, where each resource can only be held by one thread at a time, and holds on to those resources in a such a way that the holds cannot be preempted, and there exists some "circular" relationship between the threads such that each thread in the deadlock is waiting to acquire some resource held by another thread.
So, an easy way to avoid deadlock is to give some total ordering to resources and impose a rule that resources are only ever acquired by threads in order. Conversely, a deadlock can be intentionally created by running threads that acquire resources, but do not acquire them in order. For example:
Two threads, two locks. The first thread runs a loop that attempts to acquire the locks in a certain order, the second thread runs a loop that attempts to acquire the locks in the opposite order. Each thread releases both locks after successfully acquiring the locks.
public class HighlyLikelyDeadlock {
static class Locker implements Runnable {
private Object first, second;
Locker(Object first, Object second) {
this.first = first;
this.second = second;
}
@Override
public void run() {
while (true) {
synchronized (first) {
synchronized (second) {
System.out.println(Thread.currentThread().getName());
}
}
}
}
}
public static void main(final String... args) {
Object lock1 = new Object(), lock2 = new Object();
new Thread(new Locker(lock1, lock2), "Thread 1").start();
new Thread(new Locker(lock2, lock1), "Thread 2").start();
}
}
Now, there have been a few comments in this question that point out the difference between the likelihood and the certainty of deadlock. In some sense, the distinction is an academic issue. From a practical standpoint, I'd certainly like to see a running system that doesn't deadlock with the code I've written above :)
However, interview questions can be academic at times, and this SO question does have the word "surely" in the title, so what follows is a program that certainly deadlocks. Two Locker objects are created, each is given two locks and a CountDownLatch used to synchronize between the threads. Each Locker locks the first lock then counts down the latch once. When both threads have acquired a lock and counted down the latch, they proceed past the latch barrier and attempt to acquire a second lock, but in each case the other thread already holds the desired lock. This situation results in a certain deadlock.
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class CertainDeadlock {
static class Locker implements Runnable {
private CountDownLatch latch;
private Lock first, second;
Locker(CountDownLatch latch, Lock first, Lock second) {
this.latch = latch;
this.first = first;
this.second = second;
}
@Override
public void run() {
String threadName = Thread.currentThread().getName();
try {
first.lock();
latch.countDown();
System.out.println(threadName + ": locked first lock");
latch.await();
System.out.println(threadName + ": attempting to lock second lock");
second.lock();
System.out.println(threadName + ": never reached");
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
public static void main(final String... args) {
CountDownLatch latch = new CountDownLatch(2);
Lock lock1 = new ReentrantLock(), lock2 = new ReentrantLock();
new Thread(new Locker(latch, lock1, lock2), "Thread 1").start();
new Thread(new Locker(latch, lock2, lock1), "Thread 2").start();
}
}