Deadlocks

A deadlock is two or more threads each holding a resource the other one needs, and each waiting for a resource the other one holds — permanently. Nobody crashes, nothing logs an error, the program simply stops making progress. That's what makes it a distinct, nastier failure mode than a race condition: a race produces a wrong answer you can at least observe; a deadlock produces no answer, silently, and often only under a timing pattern your tests never happened to hit.

The four conditions

Coffman's four conditions (1971) all have to hold at once for a deadlock to be possible. Break any one of them and deadlock becomes structurally impossible, not just unlikely:

1. Mutual exclusion — a resource can be held by only one thread at a time.
2. Hold and wait — a thread holds at least one resource while waiting for another.
3. No preemption — a resource can't be forcibly taken away; it's only released voluntarily.
4. Circular wait — there's a cycle of threads, each waiting on a resource the next one holds.

This is the actual checklist for both diagnosing a deadlock ("which of the four is true here") and preventing one ("which of the four can I make false").

The Dining Philosophers

Five philosophers sit at a round table, a fork between each adjacent pair — five forks for five people, but eating requires two forks, the one on your left and the one on your right. If every philosopher picks up their left fork at the same moment, all five are now holding one fork and waiting for their right — which their neighbour is holding. Nobody can ever pick up a second fork. All four conditions hold: forks are exclusive, each philosopher holds one while waiting for the other, forks can't be taken away, and the five of them form a wait cycle.

It's a toy problem, but every element maps onto something real: forks are locks, philosophers are threads, and "pick up left then right" is the ordinary, seemingly reasonable code that produces a deadlock the moment enough threads run it at once. Drawn as a wait-for graph, collapsing each fork into the edge it represents ("this philosopher is stuck holding one fork, waiting on the one their neighbour has"), the circular-wait condition is literally a cycle with no way out:

Every philosopher holds their left fork and waits on their right — which is their neighbour's left fork, already spoken for. Follow the arrows from any philosopher and you arrive back where you started. That closed loop, with no thread anywhere on it able to proceed, is what "circular wait" means concretely.

Breaking one of the four

Lock ordering is the standard fix, and it breaks circular wait specifically: give every lock a fixed global order (an id, a memory address, anything consistent), and require every thread to acquire locks in that order regardless of which operation it's performing. For the philosophers: number the forks 0–4, and require each philosopher to pick up their lower-numbered fork first. Philosopher 4 (between forks 4 and 0) now reaches for fork 0 first, same as philosopher 0 — the cycle is broken because one philosopher's acquisition order doesn't mirror everyone else's.

Try-lock with a timeout breaks no-preemption: attempt the second lock, and if it's not available within a bound, release the first one and retry from scratch rather than sit and wait. This trades a deadlock for the possibility of livelock (see below) if retries aren't randomised, but it never hangs forever.

Acquire everything at once breaks hold-and-wait: if a thread can't proceed without both resources, don't take the first one until it can also have the second — acquire both atomically, or not at all. This is often the cleanest fix when it's available (a single lock covering both resources, or a lock-free compare-and-swap over the pair), but it's not always possible when the two resources are genuinely acquired at different points in the code.

Deadlock detection takes the opposite approach: let it happen, and build a wait-for graph (thread A waits for a resource thread B holds → edge A→B) that's periodically checked for a cycle. When one's found, pick a victim thread and abort or roll it back. This is what database engines do — see below — because in that setting "prevent all possible orderings in advance" is not practical across arbitrary transactions.

Deadlock vs. livelock

A deadlock is threads that are stopped. A livelock is threads that are still running — still consuming CPU, still doing something — but never making real progress, because they keep reacting to each other in a way that undoes their own work. Two people repeatedly stepping aside to let each other pass in a hallway, in sync, forever, is the canonical mental picture. The naive timeout-and-retry fix above can turn a deadlock into a livelock if every thread retries on the same schedule; the standard cure is the same one used for network collision backoff — randomised, increasing delay before each retry.

Real-world use

• Relational databases run exactly the detection strategy above: Postgres and MySQL both maintain a wait-for graph across transactions and abort one (returning a serialization/deadlock error the application is expected to retry) rather than let two transactions wait on each other's row locks forever.
• Lock ordering by convention is standard practice in any codebase with more than one mutex — "always acquire the account lock before the ledger lock" is a rule, often undocumented and discovered only when it's violated, which is exactly why writing it down (or enforcing it with a lint rule / lock-order graph checker) is worth the trouble on a real system.
• Distributed systems face a harder version: a wait-for graph spanning multiple machines is itself expensive to build and keep consistent, which is why distributed lock services (designing one is a recurring system-design interview question in its own right) lean on lease timeouts — no preemption becomes bounded preemption — rather than true cross-machine cycle detection.

Practice it

The threading round here is judged on output, not on watching your threads run: a solution that deadlocks doesn't produce a wrong answer, it produces no answer at all before the time limit — a timeout, not a mismatch.

Practice the threading round