The big idea
The Coffman conditions are the four system properties that—when they all hold simultaneously—make a deadlock possible. They do not guarantee that a deadlock will occur, but they identify the structural prerequisites. Operating-system designers exploit this insight: break (or avoid letting user code establish) at least one of the four conditions, and deadlock cannot arise.
1. Mutual exclusion
At least one resource involved in each request is non-shareable; it can be held by only one task at a time.
Examples
- a printer’s output buffer
- a mutex protecting a critical data structure
- a GPU execution engine in exclusive-compute mode
If every resource could be used concurrently (e.g., read-only memory pages), tasks would never wait for one another, so deadlock disappears.
2. Hold-and-wait
Tasks already holding one or more resources may request additional resources and wait while still holding their current allocations.
Impact
This creates “grab-as-you-go” behaviour: a task locks A, then blocks while trying to lock B, preventing others from using A—even though it cannot make progress itself.
Typical OS countermeasures
- Require tasks to acquire all needed locks in a single atomic request.
- Force a task to release everything before it can ask for something new (two-phase locking in databases).
3. No pre-emption
Resources cannot be forcibly removed from a task; release is voluntary.
When it matters
You cannot simply rip a half-printed page from the printer buffer without corruption, or evict a thread from a critical section without leaving shared state inconsistent.
Design options
- Allow safe pre-emption through rollback (e.g., transactional memory, checkpoint-and-restart).
- Limit no-pre-emption only to truly non-interruptible resources; others (CPU, pageable memory) can be taken away.
4. Circular wait
There exists a closed chain of k ≥ 2 tasks {T₁, T₂, … , Tₖ} such that each Tᵢ holds a resource needed by Tᵢ₊₁ (with Tₖ needing a resource held by T₁).
Graph view
Represent tasks as nodes and outstanding requests as edges. A cycle in this wait-for graph means circular wait. If the first three conditions also hold, the cycle is permanent.
Breaking the circle
- Impose a total ordering on resources: every task must request them in ascending order (e.g., always lock “lower-address” mutex before “higher-address” mutex).
- Use hierarchical lock classes in kernels to enforce that ordering at compile time.
Why all four must hold together
Deadlock is impossible if even one condition is absent. For instance:
- Remove hold-and-wait: tasks never retain resources while blocked → no circular dependency can form.
- Break mutual exclusion: resources are shareable → tasks never block in the first place.
Thus, prevention techniques focus on systematically denying a condition that the workload can tolerate.
Practical illustrations
| Scenario | Which Coffman conditions hold? | Deadlock risk |
|---|---|---|
| Spin-lock protecting a per-CPU list, held only briefly, and never combined with another lock | Mutual exclusion yes; hold-and-wait rarely (lock held, then immediate use); circular wait absent | Low |
| Two database transactions each locking rows in different order | All four conditions can hold | High; requires two-phase locking or wait-die prevention |
Linux read-copy-update (RCU) read-side critical section | Readers do not block writers; writers wait for grace period | Mutual exclusion absent for readers |
Key takeaway
The Coffman conditions form the theoretical backbone of deadlock analysis. By identifying tasks’ interactions with resources in terms of these four properties, an operating system can:
- Prevent deadlock (disallow one condition outright).
- Avoid it dynamically (grant a request only if it keeps the system in a “safe” state).
- Detect and recover when it nonetheless appears (cycle detection plus victim selection).
A deep understanding of these conditions empowers system architects to design kernels, libraries, and user-space code that remain live—able to make progress—no matter how complex the resource-sharing patterns become.