Deadlock in Java Programs

This article discusses deadlock in Java programs. You may know this stuff, but even so, you might want to look at the third example, which I hadn't considered until recently.

Simple Deadlock

One of the main problems with threading is Deadlock, two threads are both suspended waiting for the other one to do something. The most common cause of deadlock is two threads both acquiring the same set of (two or more) locks, but in a different order. Consider this code:

Object A = new Object();
Object B = new Object();

Thread 1:

synchronized(A)
{                       // <--- preemption
    synchronized(B)
    {   //...
    }
}

Thread 2:

synchronized(B)
{   synchronized(A)
    {   //...
    }
}

Here's the deadlock scenario:

• Thread 1 acquires A, but is then preempted for some reason.
• Thread 2 wakes up, acquires B, but can't get A because Thread 1 has it, so is suspended.
• Thread 1 wakes up, tries to acquire B, but can't because Thread 2 has it, so is suspended.
• Both threads are now suspended forever. They're deadlocked.

A More-realistic Scenario

If all deadlock scenarios were this easy to see, then there'd be no problem, but consider the following code, where two objects with synchronized methods reference each other.

class Boss
{   private Sidekick robin;
    synchronized void set_side_kick(Sidekick kid)
    {   robin = kid;
    }
    synchronized void to_the_bat_cave()
    {   robin.lets_go();
    }
    synchronized void report(String s)
    {/*...*/}
}

class Sidekick
{   private Boss batman;

    Sidekick(Boss boss)
    {   batman = boss;
    }
    synchronized void lets_go()
    {   //...
    }
    synchronized void sock_bam()
    {   batman.report(“Ouch!");
    }
}

Boss     batman = new Boss();
Sidekick robin  = new Sidekick(batman);
batman.set_side_kick( robin );

Here's the deadlock scenario:

• Thread 1 (Alfred) calls batman.to_the_bat_cave(); Alfred now has the lock on batman.
• Thread 1 is preempted just before calling lets_go().
• Thread 2 (Joker) calls robin.sock_bam(). Joker now has the lock on robin.
• Robin tries to report() to batman (on thread 2), but can't because Alfred has the lock. Joker is blocked.
• Thread 1 wakes up, tries to call lets_go(), but can't because Joker has the lock.

The main issue, here, is that the Boss and Sidekick classes may have been written months apart by different programmers. Both of them seem reasonable when taken in isolation. There's no obvious deadlock since there is only a single lock (acquired by the synchronized methods.) The only way to find this sort of problem is to draw the dynamic (run-time) model of the system (using a UML sequence diagram, which shows the objects in the system and the messages they send to one another while enacting some scenario of some use case). You then have to look at the message flow running deadlock scenarios in your head.

Wait-Induced Deadlock

You must also be careful when using wait(). Remember, wait() must be hold the lock on the object that it's waiting for (it must called from within a synchronized block or method). wait() releases the lock, waits to be notified, then reacquires the lock before returning. Now, Consider this code (which appears safe because the locks are acquired in the same order):

Thread 1:

synchronized(A)
{   synchronized(B)
    {   //...
        A.wait();
        //...
    }
}

Thread 2:

synchronized(A)
{   synchronized(B)
    {   //...
    }
}

Here's the deadlock scenario:

• Thread 1 acquires both locks, enters the wait and releases A as a side effect of waiting.
• Thread 2 activates, acquire A, but can't get B because Thread 1 has it.
• Thread 1 is notified, wait() tries to reacquire A but can't because Thread 2 has it.

The code is deadlocked.

The main issue is that the wait() hides the fact that the order-of acquisition isn't the same on both threads. Thread 1 holds the lock on B, but releases the lock on A (in the wait). It re-acquires the lock on A when wait returns, but the order of acquisition is effectively (B,A). Thread 2, however, acquires the two locks in the order (A,B). Any time multiple locks are acquired in a different order, then deadlock is possible.

Resources

Threading is always nasty stuff, and most Java programmers don't know nearly enough about it. The easiest way to learn more about threads is to have me present my one-day "Taming Java Threads" class to your group. (Find details at /training/java.threads.html)

Lacking that, here are a few good books on the subject:

Allen Holub, Taming Java Threads. Find the code for the book on my web site (). You'll also find the original JavaWorld articles (on which the book is based) on the web site.

Doug Lea, Concurrent Programming in Java(TM): Design Principles and Pattern (2nd Ed.).

Scott Oaks and Henry Wong, Java Threads (2nd Ed.)