Deadlock: Coffman Conditions, Detection and Prevention

Why architecture matters here

Deadlock matters architecturally because its cost is discontinuous. A slow lock degrades throughput smoothly; a deadlock takes the affected work to zero and, because threads block behind the frozen ones, the failure spreads - a thread pool with all workers deadlocked stops accepting requests entirely, and health checks that themselves need a lock go dark, so the outage looks like a total node death with no clue why. And it is non-deterministic: the interleaving that triggers it may occur once per million requests, so it passes every test, ships, and detonates at 3am under peak concurrency. A design that cannot rule deadlock out by construction has signed up for exactly this class of incident.

The reason the four-conditions framing is so powerful is that it converts an open-ended 'how do I avoid all possible deadlocks' into a closed 'which one condition will I break, everywhere, by policy'. Mutual exclusion is usually non-negotiable (the resource genuinely cannot be shared), so that one is rarely the lever - though lock-free and immutable-data designs do attack it. Hold-and-wait can be broken by acquiring all needed locks at once or none, but that hurts concurrency and requires knowing your needs up front. No-preemption can be broken by making locks revocable (try-lock, or a database aborting a transaction and rolling it back), which needs the resource to support safe rollback. Circular wait is the condition most codebases target, because it can be broken with a simple, local, checkable rule: impose a total order on all locks and always acquire them in ascending order - a cycle in the wait-for graph then becomes impossible because a cycle requires some thread to acquire a lower-ranked lock while holding a higher-ranked one.

The strategic choice among prevention, avoidance, and detection is really a choice about where you can afford cost. Prevention pays up front in reduced flexibility (you obey an ordering discipline forever). Avoidance pays in requiring advance declaration of maximum resource needs and running a safety check on every allocation - too expensive for general threading, which is why the Banker's algorithm lives mostly in textbooks and specialized schedulers. Detection pays after the fact: you let deadlocks happen, run a cycle-finder periodically, and recover by killing or rolling back a victim - which is exactly what relational databases do, because they can roll back a transaction cheaply and safely. Knowing these trade-offs is what lets you pick the strategy your resource semantics can actually support.

There is also a sibling failure to keep in view: livelock, where threads are not blocked but keep responding to each other and make no progress - two people stepping aside in a corridor in the same direction repeatedly. Naive 'detect contention and back off' schemes can trade deadlock for livelock, which is why real solutions add randomized backoff. The point is that these failures are a family, and the design must address the family, not one member.

The architecture: every piece explained

Top row: the four Coffman conditions, all of which must hold for deadlock. Mutual exclusion - at least one resource is held in a non-shareable mode, so only one thread can use it at a time. Hold-and-wait - a thread holding at least one resource is waiting to acquire additional resources held by others. No preemption - a resource cannot be forcibly taken from the thread holding it; it is released only voluntarily. Circular wait - there exists a set of waiting threads T1..Tn such that T1 waits for a resource held by T2, T2 for one held by T3, and Tn for one held by T1 - a cycle in the wait-for graph. Remove any single condition and the cycle cannot close.

Middle row: the three strategy families plus recovery. Prevention statically denies one condition - most commonly circular wait via a global lock order, or hold-and-wait via all-or-nothing acquisition. Avoidance uses the Banker's algorithm: each thread declares its maximum resource claim, and the allocator grants a request only if the resulting state is safe - meaning there exists some sequencing of threads that can all finish - refusing otherwise, so the system never enters a state from which deadlock is reachable. Detection allows deadlocks to form and periodically searches the resource-allocation graph for a cycle; on finding one it invokes recovery - kill a thread, roll a transaction back to a checkpoint, or preempt a resource - choosing a victim to minimize wasted work.

Bottom rows: the idioms that dominate real code. Lock ordering assigns every lock a global rank and mandates acquiring locks only in ascending rank; this is prevention of circular wait, made checkable - many systems tag locks with levels and assert the invariant at runtime. Try-lock plus timeout attacks no-preemption pragmatically: attempt to acquire with a bounded wait, and on failure release everything already held, back off a randomized interval, and retry - turning a potential deadlock into a bounded, self-resolving retry (with randomized backoff to dodge livelock). The ops strip is the diagnostic reality: thread dumps that show each thread's held and awaited locks, JVM/runtime deadlock detectors, per-operation timeout budgets, and watchdogs that snapshot and alert when threads stall.

End-to-end flow

Trace a real deadlock and its fix. A payment service transfers funds between accounts: transfer(from, to, amount) locks from, then locks to, debits, credits, unlocks both. Under light load it is flawless. Then two transfers run concurrently: T1 does transfer(A, B) and T2 does transfer(B, A). T1 locks A; T2 locks B; T1 now blocks waiting for B (held by T2); T2 blocks waiting for A (held by T1). The wait-for graph has a cycle A-thread -> B-thread -> A-thread. All four conditions hold: the account locks are exclusive (mutex), each thread holds one and waits for another (hold-and-wait), neither can be forced to release (no preemption), and the wait forms a cycle (circular wait). Both threads are frozen; the pool worker running each is gone; two more transfers involving A or B will pile up behind them.

The prevention fix targets circular wait with a global lock order. Give every account a stable, comparable id and always lock the lower id first: lock(min(from,to)); lock(max(from,to)). Now transfer(A,B) and transfer(B,A) both lock A before B. T1 and T2 contend for A; one wins, does its work, releases, and the other proceeds - no cycle can form because no thread ever holds a higher-ranked lock while requesting a lower-ranked one. This fix is local, cheap, and provably correct, which is why lock ordering is the workhorse of deadlock prevention.

Where a global order is impractical - locks discovered dynamically, or acquired across module boundaries you do not control - the try-lock idiom applies instead. Acquire the first lock, then tryLock the second with a short timeout; if it fails, release the first, sleep a randomized few milliseconds, and retry the whole sequence. Two colliding transfers now each grab one lock, each fail to get the second, each release and back off by different random amounts, and on retry one goes first and both complete. The randomized backoff is essential: without it, both retry in lockstep and livelock, repeatedly grabbing and releasing forever.

Now the detection-and-recovery world, which is how a database handles the identical logic. Two transactions update rows A and B in opposite orders and deadlock at the row-lock level. The engine does not prevent this; it runs a deadlock detector that periodically builds the wait-for graph, finds the cycle, picks the cheaper transaction to abort (fewest changes to roll back), rolls it back completely, and returns a deadlock error to that client - who simply retries and now succeeds because the other transaction has finished. This works because a transaction is a preemptible, rollback-able unit: the engine can safely revoke its locks by undoing its work. Application threads holding raw mutexes have no such rollback, which is precisely why prevention (ordering) beats detection for in-process locks while detection wins for transactions. Finally, an operational safety net catches whatever slips through: every lock acquisition carries a timeout budget, a watchdog thread periodically inspects the thread dump for the classic BLOCKED-holding-BLOCKED pattern, and on detection it captures a full dump and pages on-call - so even an un-prevented deadlock becomes a bounded, diagnosable incident rather than a silent hang.

The contrast between the three fixes is the whole lesson. Lock ordering prevented the deadlock structurally at essentially zero runtime cost, but it required a global order that the raw-mutex code could define. Try-lock-with-backoff tolerated the possibility and resolved it dynamically, at the cost of wasted acquire/release cycles and the livelock risk that randomized backoff controls - the right tool when a global order is impossible. Detection-and-recovery let it happen and cleaned up afterward, which only works because a database transaction is a rollback-able unit; application threads holding native locks have no undo, so detection cannot safely revoke their locks and prevention must be used instead. Match the strategy to what your resources can support: order what you can order, time-box what you cannot, and reserve detection for units that can be safely rolled back.

The Coffman conditions as a checklist, with a runnable Java deadlock and its fix

The four conditions come from Coffman, Elphick and Shoshani, "System Deadlocks" (ACM Computing Surveys, 1971). They are necessary, not sufficient: all four must hold for a deadlock, so removing any one rules it out. The useful question for each is what breaking it costs.

The program below reproduces the transfer deadlock from the flow above with two intrinsic locks, then asks the JVM to find the cycle with ThreadMXBean.findDeadlockedThreads(), which reports threads deadlocked on both object monitors and java.util.concurrent ownable synchronizers such as ReentrantLock. Passing ordered switches on the lock-ordering fix, which breaks circular wait by locking the lower account id first.

import java.lang.management.*;

public class Deadlock {
    record Account(int id) {}
    static final Account A = new Account(1), B = new Account(2);
    static boolean ordered;

    static void transfer(Account from, Account to) {
        Account first = from, second = to;
        if (ordered && from.id() > to.id()) { first = to; second = from; }
        synchronized (first) {
            try { Thread.sleep(50); } catch (InterruptedException e) { return; }
            synchronized (second) {
                System.out.println(Thread.currentThread().getName() + " done");
            }
        }
    }

    public static void main(String[] args) throws Exception {
        ordered = args.length > 0 && args[0].equals("ordered");
        Thread t1 = new Thread(() -> transfer(A, B), "A-to-B");
        Thread t2 = new Thread(() -> transfer(B, A), "B-to-A");
        t1.setDaemon(true); t2.setDaemon(true);
        t1.start(); t2.start();
        Thread.sleep(500);

        ThreadMXBean mx = ManagementFactory.getThreadMXBean();
        long[] ids = mx.findDeadlockedThreads();   // null when there is no cycle
        if (ids == null) { System.out.println("no deadlock"); return; }
        for (ThreadInfo ti : mx.getThreadInfo(ids)) {
            System.out.printf("DEADLOCKED %s waiting for %s held by %s%n",
                    ti.getThreadName(), ti.getLockName(), ti.getLockOwnerName());
        }
    }
}

Output on Java 23.0.2 (the hash suffixes vary per run):

$ javac Deadlock.java && java Deadlock
DEADLOCKED A-to-B waiting for Deadlock$Account@4783da3f held by B-to-A
DEADLOCKED B-to-A waiting for Deadlock$Account@254989ff held by A-to-B

$ java Deadlock ordered
A-to-B done
B-to-A done
no deadlock

The threads are daemons so the JVM can exit while two of them are still stuck; in a real service they would stay stuck forever, which is why the detector belongs in a watchdog that calls it every few seconds and logs a full thread dump when it returns non-null. From outside the process, jcmd <pid> Thread.print or jstack <pid> prints the same cycle under a "Found one Java-level deadlock" heading, listing which monitor each thread is waiting to lock and which it already holds. Detection only diagnoses: the JVM cannot revoke a monitor, so the fix is still the ordering rule, applied in every path that takes more than one account lock.