Symptom

Production is wedged. Not slow — wedged. CPU is at zero, no errors are being logged, and two threads are sitting in a lock wait with no timeout. The stack traces show thread A holding the account lock and waiting for the ledger lock, thread B holding the ledger lock and waiting for the account lock. Somebody restarts the service and it goes away.

It comes back in three weeks. Then a fix ships that “adds a timeout so it can’t hang,” and now instead of hanging the system throws lock-acquisition failures under load and the transactions retry into the same collision. Then someone adds jitter to the retry, and the incidents become rarer and never stop.

Every step of that is a real thing teams do, and every step treats deadlock as a probabilistic phenomenon to be made rarer. It is not. Deadlock has an exact characterization — four conditions, all of which must hold — and if you break one of them structurally the bug becomes impossible rather than unlikely. That is the difference between a mitigation and a fix, and it is available here in a way it usually is not.

Statement

Deadlock occurs if and only if all four of the following hold simultaneously:

  1. Mutual exclusion. At least one resource is held in a non-shareable mode.
  2. Hold and wait. A process holding at least one resource is waiting to acquire additional resources held by others.
  3. No preemption. A resource cannot be forcibly taken from the process holding it; it is released only voluntarily.
  4. Circular wait. There is a cycle $P_1 \to P_2 \to \dots \to P_n \to P_1$ in which each process waits for a resource held by the next.

The four are individually necessary, and together sufficient. That biconditional is the whole engineering value: it means the space of fixes is exactly four options wide, and it is complete. There is no fifth kind of deadlock prevention, and any strategy you can think of is one of these four in disguise.

A subtlety worth stating: condition 4 implies condition 2 for the general resource model, so the conditions are not independent. But keeping them separate is what makes them useful, because they correspond to four different places you can intervene in a design.

Argument

Necessity. Each condition’s absence directly prevents deadlock:

  • Without mutual exclusion, resources are shareable and nobody waits.
  • Without hold-and-wait, a blocked process holds nothing, so it blocks nobody.
  • With preemption, any wait can be resolved by taking the resource.
  • Without a cycle, the wait-for graph is acyclic, so it has a sink — a process waiting for nothing — which can proceed, complete, release, and unblock its predecessor. Induct: the whole graph drains.

That last one is the real content, and it is worth noticing that it is the same argument as topological sorting: a finite directed acyclic graph always has a vertex with no outgoing edges, and progress at that vertex propagates backwards.

Sufficiency. Given all four, consider the cycle. Each $P_i$ holds a resource $P_{i-1}$ wants (mutual exclusion means it must wait), holds it while waiting (hold-and-wait), and cannot be forced to release (no preemption). No process in the cycle can advance and nothing outside can help them. The state is permanent.

The four fixes, and what they cost.

Break mutual exclusion. Use shareable resources. Read-write locks let readers share; lock-free structures using compare-and-swap remove the lock entirely; immutable data has no exclusion problem at all. This is why persistent data structures and MVCC databases sidestep whole categories of this bug — a reader in PostgreSQL never blocks a writer because it reads an older version. Cost: not all resources can be shared, and lock-free code is genuinely hard to write.

Break hold-and-wait. Acquire everything up front, atomically, or nothing. Java’s tryLock on all resources with rollback does this, as does two-phase locking’s growing phase when combined with a total request. Cost: you must know your full resource set in advance, and holding everything from the start destroys concurrency.

Break no-preemption. Add timeouts and rollback. Database transaction managers do exactly this: detect the cycle, pick a victim, abort it, and let the rest proceed. PostgreSQL runs a deadlock detector after deadlock_timeout (1s by default) and kills one transaction with error 40P01. Cost: you need the work to be rollbackable, which is why this is natural in databases and awkward in general code holding OS mutexes.

Break circular wait. Impose a global ordering on resources and require every process to acquire in increasing order. A cycle would require some process to acquire out of order, so cycles are impossible. This is the one to reach for in application code, because it is static, cheap, and checkable. Linux’s lockdep validates lock ordering at runtime and reports violations before they deadlock; the kernel’s documented mmap/page-lock ordering is exactly this discipline written down. Cost: you must maintain the order globally, which is a real organizational burden, and the order must be a genuine total order over resource classes, not instances — which is why locking two accounts by ID is the standard trick.

Why the timeout fix fails. Adding a timeout does break no-preemption, so it does technically prevent deadlock. What it produces instead is livelock: the threads release, retry, and collide again. The system is not deadlocked and is also not progressing. Deadlock is a safety property violation and livelock is a liveness one, and trading one for the other is not obviously a win.

Forbids

Deadlock with an acyclic wait-for graph. If you observe a hang and the wait-for graph has no cycle, you are not looking at deadlock. You are looking at livelock, starvation, an unbounded wait on external I/O, or a lost wakeup. This is a genuinely useful diagnostic: dump the threads, build the graph, check for a cycle, and if there is none, stop looking for a lock-ordering bug.

Deadlock among lock-free code paths. No mutual exclusion, no deadlock. (ABA problems and livelock remain available.)

Deadlock under a consistently applied global lock order. Not less likely. Impossible. If it happens anyway, some path violated the order, and that is now a findable bug rather than a mysterious one.

A fifth prevention strategy. Every real technique is one of the four. Lock hierarchies are #4, tryLock-with-backoff is #3, arena allocation up front is #2, RCU is #1. This is what a characterization theorem buys you: the design space is enumerated.

Does not forbid

It does not cover starvation or livelock, which are the failures that survive your fix. A thread that repeatedly loses a race for a lock it could acquire is starving, not deadlocked, and no Coffman condition is violated. Priority inversion — where a low-priority thread holds a lock a high-priority thread needs — sank the Mars Pathfinder mission in 1997 and is not deadlock either; priority inheritance is the fix, and it is orthogonal to all four conditions.

It does not apply cleanly to distributed systems, where the graph is not observable. Building the wait-for graph requires a consistent global snapshot, which the Two Generals problem (T061) makes expensive and FLP (T062) makes impossible to do reliably with failures. Distributed deadlock detection is a real subject (Chandy–Misra–Haas edge chasing) and it is much harder than the single-node case, which is why distributed systems overwhelmingly use lease timeouts instead: break no-preemption, accept the livelock risk.

It does not mean detection is always the wrong choice. Prevention costs concurrency. Databases deliberately allow deadlock and detect it, because transactions can be aborted cheaply and forbidding hold-and-wait would serialize the workload. Ostrich algorithm — ignoring the problem — is also defensible: it is what Linux does for most user-space deadlock, on the grounds that the cost of prevention exceeds the cost of the occasional restart.

It does not require locks specifically. The resources can be threads in a bounded pool, database connections, file handles, or network buffers. Thread pool exhaustion where tasks submit subtasks to the same pool and wait for them is textbook hold-and-wait plus circular wait, and it is one of the most common production hangs in JVM services. The fix is the same: separate pools imposes an ordering.

Boundary

  • Prevention vs. avoidance vs. detection. Prevention breaks a condition structurally. Avoidance (the Banker’s algorithm) allows requests only into states from which completion is guaranteed, and requires knowing maximum resource claims in advance, which is why nothing real uses it. Detection lets deadlock happen and recovers.
  • Deadlock is a safety property. “Something bad happens” — the system enters a state with no successor. Starvation and livelock are liveness violations: “something good never happens.” The distinction determines which tools apply, since model checkers find safety violations far more easily.
  • Static detection. Lock-order violations are checkable: Linux’s lockdep at runtime, Rust’s type system by making shared mutable state require a lock, and Java’s -XX:+PrintConcurrentLocks plus jstack for post-mortem. RAII and Rust’s MutexGuard eliminate the forgot to unlock class entirely, which is a different bug but the same discipline.
  • Where the model is too simple. The conditions assume resources are discrete and requests are for whole resources. Deadlock over quantities of a divisible resource — memory, connection counts — behaves differently and is closer to a scheduling problem than a graph one.