Concurrency
Part 4 of 6 · ConcurrencyDeadlock Prevention & Avoidance
Deadlock needs Coffman’s four — mutual exclusion, hold-and-wait, no preemption, circular wait. Production systems break circular wait with lock ordering, avoid hold-and-wait with try-lock + backoff, or redesign with channels / actors so resources are not multi-locked.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Overview
Deadlock is not “locks are slow.” It is a cycle: everyone holds something the next thread needs, and nobody can drop. Interviews want Coffman, a total order, and the humility to not lock two things if a channel would do.
By the end you should be able to:
- Mark Coffman’s four on a dining-philosophers drawing
- Impose a lock rank and sort dynamic sets
- Use try-lock without livelocking
- Contrast prevention, avoidance, detection
- Redesign to single-lock or actors
Two locks: order vs try-lock spin
Prefer
Global lock order (sort ids, acquire ascending)
Circular wait becomes impossible on those mutexes. Nested acquires are boring and reviewable.
- Document rank: dbConn < cache < metrics, or address order.
- C++ std::lock / scoped lock sorts internally.
- Release reverse. Never hold across unknown callbacks.
Alternative
try_lock in a tight loop, no backoff, no order
You broke hold-and-wait sometimes. Two threads can still dance forever (livelock) or hit the unlucky cycle.
- Backoff + jitter, or drop all and retry.
- Timeouts fail into an error, not a silent hang — still not a substitute for order.
- Actors / channels: do not multi-lock across components.
Killing a deadlock
Break one Coffman condition. Prefer order.
- 1
Draw the wait-for graph
A holds L1 wants L2; B holds L2 wants L1. Cycle = deadlock. - 2
Prevention: lock order
Both sort (L1, L2) and acquire L1 then L2. Cycle impossible. - 3
Prevention: no hold-and-wait
try_lock both; on fail drop everything, backoff, retry. - 4
Avoidance / detection
Banker’s is rare in request paths. Detect cycles in a graph and abort a victim in DB engines. - 5
Redesign
One mutex per component, or message passing. Do not lock A and B.
Coffman (all four required)
- Mutual exclusion — the resource is not shareable (a mutex, a row lock).
- Hold and wait — hold one, wait for another.
- No preemption — you cannot steal a mutex from its owner (usually).
- Circular wait — a cycle in the wait-for graph.
Break any one:
| Break | How | Cost |
|---|---|---|
| Mutual exclusion | Make the resource immutable / atomic / lock-free | Not always possible |
| Hold-and-wait | Acquire all at once; try-lock; don’t nest | Hard with callbacks |
| No preemption | Timeouts; abort victim (DB deadlock detector) | Failed work / retry |
| Circular wait | Total order on lock ids | Discipline; the usual winner |
RWLock upgrade is Coffman on one lock flavor: you hold read, wait for write, peer does the same.
Prevention vs avoidance vs detection
Prevention — make a Coffman condition structurally impossible (lock rank). This is what you ship in app code.
Avoidance — Banker’s algorithm: do not grant a request that could lead to unsafe state. Needs max-claim a priori. Almost never in a web worker; still an OS-course question.
Detection — allow deadlock, find the cycle, abort a victim. InnoDB / Postgres deadlock detector on row locks. Your mutexes typically do not detect; they hang until you page.
Recovery — restart the process is a blunt recovery. Prefer prevention.
Philosophers and dynamic sets
Naive: each philosopher picks left, then right → cycle of 5.
Fixes: last philosopher picks right first (asymmetric); butler; sort fork ids then pick both.
locks = sorted(needed, key=id)
for lk in locks: lk.acquire()
try: work
finally:
for lk in reversed(locks): lk.release()C++ std::lock(m1, m2) / std::scoped_lock does the sort+try algorithm for you.
Timeouts: try_lock_for then error. The request fails; the process does not hang. Combine with order so timeouts are rare.
Livelock: two threads drop and retry in lockstep. Backoff + jitter, or a wait queue. Deadlock threads are blocked; livelock threads are running.
Flow
- 1
Thread A holds L1
- waitsL2
- 2
L2
- 3
Thread B holds L2
- waitsL1
- 4
L1
Lesson map
Deadlock Prevention & Avoidance
Deadlock needs Coffman’s four — mutual exclusion, hold-and-wait, no preemption, circular wait. Production systems break circular wait with lock ordering, avoid hold-and-wait with try-lock + backoff, or redesign with channels / actors so resources are not multi-locked.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["Thread A holds L1"] l2["L2"] b["Thread B holds L2"] l1["L1"] a -->|waits| l2 b -->|waits| l1
Channels beat nested locks
If two services must “lock user then lock inventory,” you are designing a distributed deadlock. Prefer a single owner (inventory service serializes via a queue) or an atomic DB transaction with consistent row order (ORDER BY id FOR UPDATE). Mutexes stay inside one process, one rank.
Do not hold a mutex across a CV wait that might need another lock without documenting the rank — wait reacquires, nested Mesa wait is how ranks invert.
Order vs inversion (run this)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Coffman four?
Answer
Mutual exclusion, hold-and-wait, no preemption, circular wait. All four required. Interviews want lock ordering as the practical break.
Prevention vs avoidance?
Answer
Prevention: structure so deadlock cannot occur (order). Avoidance: runtime grant/deny given max claims (Banker’s). Detection: find a cycle later (databases).
How do you lock a dynamic set?
Answer
Sort by a total order (id, address), acquire ascending, release descending. C++ std::lock.
try_lock as a strategy?
Answer
Acquire all without waiting; on failure release everything, backoff, retry. Without backoff you livelock. Not a replacement for order on the hot path.
Livelock vs deadlock vs starvation?
Answer
Deadlock: blocked, no progress. Livelock: running, no useful progress. Starvation: system progresses, one thread never wins (unfair RWLock writers).
Dining philosophers — one fix?
Answer
Sort fork ids; or make one philosopher pick right first; or an arbitrator. Naive left-then-right is the cycle.
Do mutex timeouts prevent deadlock?
Answer
They bound hang time (fail the request). The cycle can still form every time. Prefer order; timeouts are a backstop.
DB deadlocks?
Answer
Engines detect wait-for cycles on row locks and abort a victim (40001 / deadlock found). App retries the transaction. Still sort FOR UPDATE ids to make them rare.
Why not lock across a network call?
Answer
You extend hold-and-wait across RTTs and other services’ locks — distributed deadlock with no process-local detector.
RWLock upgrade?
Answer
Hold-and-wait on the same lock family. Two upgraders cycle. Release read, take write, re-check. RWLock page.
Pitfalls
Draw five forks. Show the cycle. Rewrite acquire as sorted(left, right). Then sketch two code paths locking (cache, db) vs (db, cache) and fix the rank. If you spun try_lock without sleep, add backoff.
Go Deeper
Cluster: CVs · next happens-before