Two threads, each holding a lock the other one needs, both waiting forever — deadlock is one of the few concurrency bugs that's actually deterministic once triggered, which makes it both easier to reason about and, once it happens, completely unrecoverable without outside intervention.
Intermediate
3 min read
The classic deadlock scenario
Deadlock happens when two or more threads are each waiting for a resource
the other holds, and neither can proceed:
Thread 1 holds Lock A and is waiting for Lock B. Thread 2 holds Lock B and
is waiting for Lock A. Neither will ever release what it holds, because
each is permanently blocked waiting on the other — the program simply
hangs, with no crash, no error message, and no way out without external
intervention (restarting the process, or a deadlock-detection mechanism
forcibly breaking the cycle).
The four necessary conditions
Deadlock requires all four of these to hold simultaneously — breaking any
single one makes deadlock impossible in that scenario:
Mutual exclusion — a resource can only be held by one thread at a
time (true of any lock by definition).
Hold and wait — a thread holds at least one resource while waiting to
acquire another.
No preemption — a resource can't be forcibly taken away from the
thread holding it; it must be released voluntarily.
Circular wait — there's a cycle of threads, each waiting on a
resource held by the next one in the cycle.
Prevention: breaking one condition on purpose
Since all four conditions are required, deliberately violating any one
prevents deadlock entirely in that code path. The most common and most
practical technique is attacking circular wait directly: establish a
global, consistent ordering for acquiring locks (e.g., "always acquire Lock
A before Lock B, everywhere in the codebase, never the reverse") — if every
thread acquires locks in the same fixed order, a cycle can never form,
because the "reverse" acquisition that would complete the cycle simply
never happens.
Some systems (notably many database engines) allow deadlock to occur but
actively detect it — by periodically checking for a cycle in a graph of
"who's waiting for what" — and recover by forcibly aborting one of the
threads or transactions involved, releasing its locks so the others can
proceed. This trades a small amount of ongoing detection overhead for not
needing to enforce a strict global lock-ordering discipline across an
entire codebase, which can be impractical in a large system with many
independent components.
Livelock: the deadlock look-alike that isn't stuck
A related failure mode: two threads that are technically still executing —
neither is blocked — but are stuck repeatedly reacting to each other in a
way that never makes real progress, like two people in a hallway who each
keep stepping aside in the same direction to avoid a collision that keeps
re-forming. Unlike deadlock, CPU cycles are being spent; unlike healthy
concurrency, no useful work is actually completing.