Deadlock, and finding it in a thread dump

A deadlocked program does not crash. It does not log anything. It sits there using no CPU, answering nothing, looking for all the world like it is busy.

That is why this lesson exists: the skill is not avoiding deadlock — it is recognising one in thirty seconds when it happens to somebody else's code at nine at night.

Making one

public class Deadlock {
    private static final Object ACCOUNTS = new Object();
    private static final Object LEDGER = new Object();

    public static void main(String[] args) {
        Thread a = new Thread(() -> {
            synchronized (ACCOUNTS) {
                sleep(50);
                synchronized (LEDGER) {
                    System.out.println("A finished");
                }
            }
        }, "transfer-thread");

        Thread b = new Thread(() -> {
            synchronized (LEDGER) {
                sleep(50);
                synchronized (ACCOUNTS) {
                    System.out.println("B finished");
                }
            }
        }, "audit-thread");

        a.start();
        b.start();
    }

    private static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

transfer-thread holds ACCOUNTS and wants LEDGER. audit-thread holds LEDGER and wants ACCOUNTS. Neither will ever let go. The program prints nothing and never exits.

Note the thread names. new Thread(runnable, "transfer-thread") costs nothing and is the difference between a diagnosable thread dump and a page of Thread-0, Thread-1, Thread-2.

The four conditions

A deadlock needs all four of these at once, which is useful because breaking any one prevents it:

1. Mutual exclusion — a resource only one thread can hold.
2. Hold and wait — a thread holds one and asks for another.
3. No pre-emption — nothing can take a lock away.
4. Circular wait — A waits for B, B waits for A.

You cannot remove the first or third with synchronized. So in practice you break the second or the fourth.

Breaking the cycle: lock ordering

The fix that works in real systems, and it is almost embarrassingly simple: every thread takes locks in the same order.

// Both threads: ACCOUNTS first, then LEDGER. Always.
synchronized (ACCOUNTS) {
    synchronized (LEDGER) {
        …
    }
}

With a global order, a cycle cannot form — thread B can never be holding a later lock while waiting for an earlier one.

When the locks are objects chosen at runtime — transferring between two accounts, say — order them by something stable:

void transfer(Account from, Account to, long paise) {
    // Order by identity hash so any pair is always locked in the same order,
    // whichever direction the transfer is going.
    Account first  = System.identityHashCode(from) < System.identityHashCode(to) ? from : to;
    Account second = (first == from) ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.withdraw(paise);
            to.deposit(paise);
        }
    }
}

Without that, transfer(a, b) and transfer(b, a) running at once is a textbook deadlock — and it is the textbook example precisely because banks kept writing it.

Breaking hold-and-wait: tryLock

if (accounts.tryLock(200, TimeUnit.MILLISECONDS)) {
    try {
        if (ledger.tryLock(200, TimeUnit.MILLISECONDS)) {
            try { … } finally { ledger.unlock(); }
        } else {
            // Could not get both. Release what we have and retry later, rather
            // than holding one forever.
            log.warn("could not acquire ledger, backing off");
        }
    } finally {
        accounts.unlock();
    }
}

More code, and it converts a hang into a log line — which is a very large improvement at nine at night. Add a small random back-off before retrying, or two threads will collide again in lockstep.

Finding one

The program is hung. Here is the whole procedure.

Find the process:

jps -l

Take a thread dump:

jstack <pid>

The JVM detects the common case itself, and prints this at the end:

Found one Java-level deadlock:
=============================
"transfer-thread":
  waiting to lock monitor 0x00007f... (object 0x000000070ff0a1b8, a java.lang.Object),
  which is held by "audit-thread"
"audit-thread":
  waiting to lock monitor 0x00007f... (object 0x000000070ff0a1a8, a java.lang.Object),
  which is held by "transfer-thread"

It names both threads and both locks. That is the answer, and it took about fifteen seconds.

Read the stacks above it to find the exact lines:

"transfer-thread" #21 prio=5 waiting for monitor entry
   java.lang.Thread.State: BLOCKED (on object monitor)
        at Deadlock.lambda$main$0(Deadlock.java:12)
        - waiting to lock <0x000000070ff0a1b8> (a java.lang.Object)
        - locked <0x000000070ff0a1a8> (a java.lang.Object)

waiting to lock is what it wants; locked is what it holds. Two of those and you have the cycle.

Alternatives when jstack is not to hand: jcmd <pid> Thread.print does the same, and on any platform Ctrl+\ (SIGQUIT) makes the JVM print a dump to its own stdout — useful when you have a terminal and nothing else.

Reading thread states

In a dump, the state tells you what kind of problem you have:

Many threads BLOCKED on the same lock is contention — not a deadlock, but a bottleneck, and often the real performance problem.

Many threads WAITING on a pool usually means the pool is exhausted because its tasks are blocked on something else. That is thread-pool starvation, and it looks like a deadlock without being one: no cycle, just everybody waiting on a resource that never frees.

Take two or three dumps a few seconds apart. Threads in the same place in all of them are stuck. Threads that moved are merely busy — one dump cannot tell you the difference.

What the JVM cannot detect

jstack finds deadlocks on synchronized monitors and on java.util.concurrent locks. It does not find:

• two threads each waiting on the other's BlockingQueue,
• a thread pool whose tasks submit to the same pool and wait,
• anything waiting on an external resource that will never arrive.

For those you get no "Found one Java-level deadlock" banner — you get threads WAITING and have to read the stacks yourself. Which is why knowing what WAITING on a queue looks like is worth as much as knowing the banner.

Avoiding it in the first place

In order of how much they help:

1. Do not hold two locks. Most deadlocks disappear if the code holds one.
2. Never call unknown code while holding a lock. A listener, a callback, an overridden method — it may take a lock you have never heard of.
3. Use the concurrent collections rather than locking around plain ones.
4. Lock in a consistent global order when you must hold two.
5. tryLock with a timeout when even that is not guaranteed.
6. Name your threads, so the dump is readable when it happens anyway.

Number two is the one that catches experienced people. synchronized around a block that publishes an event means every listener runs holding your lock — and one of them locks something else.

Check your work

Why deadlock is hard to spot: no crash, no log, no CPU — it looks like the program is busy.

The four conditions: mutual exclusion, hold-and-wait, no pre-emption, circular wait. Break any one.

Which two you can actually break: hold-and-wait, and circular wait.

The lock-ordering fix: every thread takes locks in the same order, and for runtime-chosen locks you order by something stable.

What tryLock converts: a hang into a log line.

The procedure: jps -l, then jstack <pid>, then read the "Found one Java-level deadlock" section.

What to read in a stack: waiting to lock is what it wants, locked is what it holds.

Why take several dumps: one dump cannot distinguish stuck from busy.

What the JVM cannot detect: queue-based cycles, pool starvation, and waits on external resources.

The rule that catches experienced people: never call unknown code while holding a lock.

Practice

1. Run the Deadlock program above. Confirm it prints nothing and does not exit.
2. Find its pid with jps -l and run jstack on it. Find the deadlock section.
3. Read both stacks and identify which line wants which lock.
4. Fix it by ordering the locks. Confirm both threads finish.
5. Remove the thread names and take another dump. Note how much harder it is.
6. Write the two-account transfer without ordering, call it from two threads in opposite directions, and deadlock it.
7. Add the identityHashCode ordering and confirm it survives 10,000 transfers.
8. Rewrite it with tryLock and a timeout. Log the failures and count them.
9. Create pool starvation: a fixed pool of two where each task submits to the same pool and waits. Take a dump and confirm there is no deadlock banner.
10. Take three dumps of a healthy running program a second apart, and identify which threads are genuinely stuck.

Next: the build tools and tests that make all of this checkable.