Deadlock and the Coffman Conditions¶

Deadlock occurs when processes wait circularly for resources. Four conditions must all hold simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait. Breaking any one condition prevents deadlock.

Tension Addressed¶

Safety vs. Liveness

Recognizable As¶

Programs that hang indefinitely with threads waiting on each other; lock ordering protocols (break circular wait); try-lock with backoff (break hold-and-wait); resource hierarchies (enforce ordering).

Canonical Sources¶

Coffman et al., "System Deadlocks" (1971); Dijkstra, "Dining Philosophers" (1965)

Transfers To¶

Distributed systems (distributed deadlock), resource allocation (memory, connections), workflow engines (task dependencies)

Sub-concepts: - Livelock: Threads actively responding to each other but making no progress (like two people in a hallway both stepping aside the same direction repeatedly). - Starvation: A thread is perpetually denied resources because others always get priority.