Deadlock Lab (Interactive)
Step two bank transfers into a circular wait, then break a Coffman condition to escape. A step-executable wait-for graph: acquire account mutexes in opposite orders to freeze both threads, then test global lock ordering or TryLock timeouts.
Deadlock: Circular Wait & Lock Ordering Lab
Run two bank transfers that lock accounts in opposite orders — then break a Coffman condition to prevent the freeze.
Coffman Conditions — deadlock needs all 4 simultaneously
- Mutual Exclusion: BROKEN — Only one thread may own each account mutex.
- Hold and Wait: BROKEN — A blocked thread keeps the lock it already grabbed.
- No Preemption: BROKEN — Locks are only released voluntarily.
- Circular Wait: BROKEN — T1 waits for T2 while T2 waits for T1.
› Two bank-transfer threads and two account mutexes initialized. Step them in any order.
How It Works Under the Hood
Deadlock requires all four Coffman conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait. Two transfers locking accounts 100 and 200 in opposite orders create the cycle; both threads sleep at 0% CPU forever. Sorting lock acquisition by resource ID makes circular wait mathematically impossible, while TryLock timeouts break no-preemption — exactly how PostgreSQL’s wait-for-graph detector aborts the younger transaction.
Core Architectural Principles
- All 4 Coffman conditions must hold; the simulator lights each one per state transition.
- Lock ordering (lowest account ID first) makes the circular wait unconstructable.
- Deadlock shows 0% CPU (blocked), distinguishing it from livelock’s 100% CPU spin.
In any transfer or checkout design, preempt the question: "to avoid deadlock I acquire account locks in sorted ID order, and use TryLock with exponential-backoff retries as a belt-and-braces." Recite the four Coffman conditions and note databases detect cycles in wait-for graphs and abort one victim.
Deterministic lock ordering guarantees deadlock-freedom but demands discipline across every code path, while timeouts preserve liveness at the cost of retries.