Why deadlocks need four conditions

A deadlock feels like bad luck, but it can only happen when four specific conditions all hold at once — and breaking any one makes it impossible.

The picture version

Five pictures for a reader who has never debugged a hung program, following two threads and two locks — the code version of two people stuck in a doorway.

Why it exists

Two people reach a narrow doorway from opposite sides at the same moment. Each steps half-in, then stops — neither will back out, because the other might take the gap. They stand there. Nothing is broken; both are behaving “correctly.” They’re just stuck, forever, waiting on each other.

That’s a deadlock, and it’s the bug that makes concurrent programs feel cursed. Your service runs fine for weeks, then one night two threads freeze, requests pile up, and the stack traces show everyone politely waiting — no crash, no error, no obvious culprit. It looks like cosmic bad luck: a one-in-a-million timing fluke.

It isn’t luck. A deadlock is not a random event that sometimes happens when threads share resources. It is a precise structural situation, and it can only occur when four specific conditions are all true simultaneously. These are usually called the Coffman conditions. Miss any one of the four, and a deadlock is not unlikely — it is impossible. That’s the satisfying part: deadlock has a closed-form cause, so it has a closed-form cure.

Why it matters now

Every system that lets more than one thing run at once and share something — threads sharing a mutex, transactions sharing database rows, microservices sharing a connection pool, distributed nodes sharing a lock service — can deadlock. Databases take this seriously enough to ship a deadlock detector: in PostgreSQL, once a transaction has waited on a lock longer than deadlock_timeout, the system checks for a cycle of transactions waiting on each other’s locks and aborts one of them to break it. The reason that detector exists, and the reason it works, is the four-condition structure below. Knowing the four conditions turns “our service hangs sometimes, restart it” into “condition X holds here — break it on purpose.”

The short answer

deadlock = mutual exclusion + hold-and-wait + no preemption + circular wait

Picture to keep: the two people wedged in the doorway — each holding half the gap, each unable to pass, each unwilling to step back. The picture breaks in one useful way: real people eventually get embarrassed and one backs out. Threads have no embarrassment, so somebody has to design the backing-out in.

A deadlock happens exactly when: resources can’t be shared (mutual exclusion), a holder can request more while keeping what it has (hold-and-wait), nobody can forcibly take a resource away (no preemption), and there’s a closed loop of “A waits on B waits on … waits on A” (circular wait). All four are necessary. In the common case of single-instance resources — one lock, one holder — they’re also sufficient: a wait-for cycle means everyone in it is stuck. (With pools of interchangeable resources the cycle test gets weaker, but the four conditions still all have to hold.) Either way, you don’t fix a deadlock by getting lucky with timing — you fix it by designing one of the four conditions out.

How it works

Take the doorway again, but in code. Thread A grabs mutex R1 and then needs R2. Thread B grabs R2 and then needs R1. Each holds one, each waits for the other. Draw the wait-for graph and every arrow leads to the next, all the way around:

flowchart LR
    A[Thread A] -->|waits for| R2[Lock R2]
    R2 -->|held by| B[Thread B]
    B -->|waits for| R1[Lock R1]
    R1 -->|held by| A

Follow the arrows: A waits for R2, which B holds; B waits for R1, which A holds — and you’re back at A. The loop never opens.

Naive fix: make it rarer. This is where most people start, because the bug presented as a timing fluke. Add a small random sleep before acquiring, stagger the threads, reduce the pool size. It works — the hang goes from nightly to monthly — and it fixes nothing. Every arrow in that diagram is still drawable; you’ve only made the schedule that draws them less likely. This is the trap: a fix that improves your metrics while leaving the bug fully intact.

Second naive fix: add a timeout. Give up on a lock after five seconds and return an error. This one is closer to real — and it’s worth being precise about why. If the timing-out thread also drops the locks it was holding and retries, you’ve stumbled into an actual structural fix: you’ve made resources preemptible, just crudely and after a five-second stall. If it keeps holding them while it retries, you’ve built a slower loop around the same deadlock. Either way the cycle can still form, so you keep paying five seconds every time it does — and nothing in the design says how often that is.

The reason the first fix fails outright and the second only half-works is that both are aimed at when the threads interleave, and interleaving was never the cause. The cause is structural, and the structure has exactly four load-bearing walls. Walk them against the diagram and each becomes a place to attack:

• Mutual exclusion — a lock can be held by only one thread at a time. If R1 and R2 were freely shareable (say, read-only data), there’d be nothing to wait for. Break it by not locking: use immutable data, or per-thread copies.
• Hold-and-wait — a thread keeps R1 while blocking on R2. Break it by requiring threads to grab all the locks they’ll need at once, or to release everything before re-requesting. No partial holds, no half-in-the-doorway.
• No preemption — once A has R1, nothing can yank it back. Break it by making resources yieldable: a thread that can’t get its next lock must drop the ones it holds and retry. (In practice the holder lets go rather than something seizing it — trylock-then-release is the textbook version — but a database deadlock detector does the forcible kind, preempting by aborting one transaction and taking its locks back.)
• Circular wait — the loop itself. Break it by imposing a global order on resources: every thread must acquire locks in increasing order, say always R1 before R2. Then a cycle can’t form, because a cycle would require some thread to hold a higher-numbered lock while waiting on a lower-numbered one — which the rule forbids.

The lock-ordering trick is a common move, because it’s cheap and local: you don’t need a detector, a timeout, or a retry loop, just a convention. The deeper point is that all four cures are the same move — make one of the four conditions false. There’s no fifth option, and no amount of careful timing counts as a cure, because timing was never the cause.

One honest seam: “necessary and sufficient” is about the structure, not about whether the bad interleaving actually occurs. A program can have all four conditions latent in its design and run for years because the unlucky schedule never lands. That’s why deadlocks feel like luck — the structure is always there, and luck only decides when it bites. Removing a condition removes the structure, so luck stops mattering.

You started with deadlock = mutual exclusion + hold-and-wait + no preemption + circular wait. What did walking the doorway add to that list of four? — + they're an AND, not an OR. That’s the whole payoff: because all four are necessary, you never have to defeat the deadlock, only one of its four ingredients — and you get to pick whichever one is cheapest to design away in your system.

Check yourself

Before you go — your service has a deadlock between two locks, and a colleague proposes: “let’s use a single global lock for everything instead.” Does that fix it? What did you just pay?

And one more — two transactions deadlock in Postgres, and the database aborts one with a “deadlock detected” error. Which of the four conditions did the database break, and why did it choose that one?

Famous related terms

• Livelock — livelock ≈ deadlock + motion — threads aren’t blocked, they’re actively responding to each other (both step aside, both step back, repeat), so they make no progress despite never sitting still.
• Race condition — race = shared state + unsynchronized access + order-dependent outcome — the bug locks are meant to prevent; ironically, adding locks to fix races is what introduces the deadlock risk.
• Lock ordering / lock hierarchy — lock ordering = global rank on locks + "acquire in rank order" rule — the standard way to kill the circular-wait condition by construction.
• Deadlock detection — detection = wait-for graph + cycle search + victim abort — what databases like PostgreSQL do instead of preventing deadlocks: let them happen, find the cycle, break it.

Going deeper

• Coffman, Elphick, and Shoshani, “System Deadlocks” (ACM Computing Surveys 3(2), 1971) — the primary source, for the question “what exactly did the original statement of the four conditions say,” before decades of paraphrase. The name “Coffman conditions” is a later convention; the paper simply states them.
• Operating Systems: Three Easy Pieces, the “Deadlock” chapter — the explainer, for “how do people actually break these conditions in real code,” with worked lock-ordering and detection examples; free online.
• PostgreSQL’s explicit-locking docs — the rabbit hole: what a production engine tells you to do about deadlocks, and what it promises to handle itself.