Deadlock Lab
Four conditions have to hold simultaneously for a deadlock to exist. Break any one and it cannot happen. Three of the four are impractical to break in real code, which is why lock ordering is the answer you will actually reach for — and why it is the answer that has to be written down.
SIMULATED
No number on this page was measured. The simulators below drive a wait-for graph and a cycle detector, not a runtime. The model reproduces the behaviour of real systems — work does not overlap on one core, a critical section serialises whatever fraction of the work it covers, a queue whose arrival rate exceeds its service rate grows without bound — but the figures belong to no real machine, runtime or workload. Read the shape of the curve and the direction of the change; never quote the milliseconds.
Build a deadlock yourself
Acquire and release locks by hand and watch the wait-for graph fill in. The moment a cycle closes, nothing in the system can proceed — and no participant is doing anything wrong.
Build a deadlock yourself
Each task takes two locks and holds them until it is done. Choose the order each one uses, then decide who runs next. Nothing is scripted — if it deadlocks, you scheduled it.
T1
T2
2 steps
Task 1 (A→B)
holds Lock A
Task 2 (B→A)
holds Lock B
● Task 1● Task 2▢ Lock A▢ Lock B
Lock Awaits forTask 1· held by
Lock Bwaits forTask 2· held by
2 steps in. Two tasks are taking the same pair of locks in opposite orders. That is not yet a deadlock — it is the *possibility* of one, which is why this bug passes tests for months. To realise it, give each task one lock and then make each ask for the other.
SIMPLIFIEDBlocking acquisition, no timeouts, no try-lock. Those are exactly the escape hatches that turn this hang into a retry.
A global lock order is a proof, not a habit
The practical fix, applied. Impose a total order on the locks and the cycle becomes unconstructible.
A global lock order is a proof, not a habit
The same tasks and the same locks. Turn on the convention and every reachable schedule is checked — not sampled — for a wait-for cycle.
T1
T2
Effective acquisition order
T1: Lock A → Lock B
T2: Lock B → Lock A
Exhaustive check
reachable states
20
states with a cycle
1
verdict
deadlock reachable
deadlock-free states19 · turn the convention on to compare
● Task 1● Task 2▢ Lock A▢ Lock B
Cycle: Task 1 → Lock B → Task 2 → Lock A → Task 1
One of the reachable cycles, found by walking every schedule rather than by waiting for it to happen in production.
1 of the 20 reachable states contain a wait-for cycle. Your tests explore this space at random and mostly miss it — which is the whole difficulty of deadlock: the failing schedules are rare, not impossible, and they get rarer as the machine gets faster. The price is real: a global order means the code that needs B first must still take A first, which sometimes forces you to hold a lock longer than the work requires, or to look up data before you know you need it. Deadlock avoidance costs contention. It is still the cheapest of the options, because the alternatives — lock timeouts with retry, or a watchdog that kills a participant — turn a hang into a partial failure you now have to handle.
SIMPLIFIEDExhaustive over this machine's reachable states. A real program has more state; the argument, not the state count, is what transfers.
Prove it on a graph
The smallest deadlock there is, and the smallest fix.
Two tasks, two locksSIMPLIFIED
Task 1 always acquires A then B. Flip the switch to change what Task 2 does. The cycle detector below is the same function the deadlock simulator uses — it is not told the answer, it walks the graph.
● Task 1● Task 2▢ Lock A▢ Lock B
Task 1waits forLock B· holds A, wants B
Lock Bwaits forTask 2· B is held by Task 2
Task 2waits forLock A· holds B, wants A
Lock Awaits forTask 1· A is held by Task 1
Cycle: Task 1 → Lock B → Task 2 → Lock A → Task 1
Break the circular wait: make every task acquire A before B. The other three conditions can stay exactly as they are.
The four conditions, and which technique breaks each
All four must hold at once. Every deadlock-prevention technique is an attack on exactly one of them — and each attack has a price, which is why only one of them is common.
| Condition | What it means | What breaks it | What that costs |
|---|---|---|---|
| Mutual exclusion | The resource cannot be shared — one holder at a time, by definition. | Remove the sharing. Immutable data, a per-task copy, or a lock-free structure means there is nothing to hold exclusively. | Copies cost memory and can cost consistency; lock-free code costs an enormous amount of care and is rarely worth it for this reason alone. |
| Hold and wait | A task holds one resource while blocking for another. | Acquire everything at once or nothing at all — a single combined lock, or a try-acquire-all that backs off and releases on failure. | Coarser locking reduces concurrency; the all-or-nothing retry can livelock if every task backs off in lockstep. |
| No preemption | A resource cannot be taken away from whoever holds it. | Timed acquisition. try_lock with a deadline: give up, release what you hold, and start over. | The work done before the timeout is thrown away, and a timeout that is too short turns a slow path into a livelock. |
| Circular wait | A cycle in the wait-for graph: each participant waits on a resource the next one holds. | A global lock order. Every task acquires locks in the same total order, so no cycle can form. This is the one that is practical in real code. | Someone has to define, document and enforce the order, and every new lock has to be placed in it — including locks inside libraries you did not write. |
Lessons behind the four conditions
What a deadlock is not
Three failures that look identical from outside and need completely different fixes.
Livelock
- Every task is running. CPU is busy. Nothing advances.
- Typically a back-off-and-retry loop where everyone backs off in lockstep and collides again.
- A cycle detector finds nothing, because nobody is blocked.
Starvation
- The system makes progress. One participant never does.
- Usually an unfair lock, a priority scheme, or a writer behind an endless stream of readers.
- Throughput looks healthy; the p99.9 of one caller does not.
Just slow
- One task holds a lock across an I/O call and everyone queues behind it.
- No cycle, no unfairness — a critical section that is simply far too wide.
- Lock wait time rises with load; the fix is to shrink the section, not to add threads.