Every deadlock, no matter how complicated the system it happens in, whether it’s a database with thousands of concurrent transactions or two threads fighting over a couple of mutexes, boils down to the same four underlying conditions all being true at once. This is one of those results in computer science that I find genuinely elegant: a phenomenon that can look wildly different across different systems is fully explained by just four simple, necessary conditions, first articulated clearly by Edward G. Coffman Jr. and colleagues in 1971, which is why they’re sometimes called the Coffman conditions.
I want to go through each of these four conditions in detail, show why all four must hold simultaneously for deadlock to be possible, and then connect each one to the specific real-world prevention techniques designed to break it.
The Four Conditions, at a Glance
- Mutual Exclusion: At least one resource must be held in a non-shareable mode, only one process can use it at a time.
- Hold and Wait: A process must be holding at least one resource while simultaneously waiting to acquire additional resources currently held by other processes.
- No Preemption: Resources cannot be forcibly taken away from a process; they can only be released voluntarily by the process holding them.
- Circular Wait: There must exist a set of processes {P1, P2, …, Pn} such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, and so on, with Pn waiting for a resource held by P1, forming a closed cycle.
All four of these conditions are necessary for deadlock, meaning if even one of them doesn’t hold, deadlock cannot occur. This is precisely why deadlock prevention strategies work by targeting and structurally eliminating one specific condition; you don’t need to eliminate all four, breaking just one is sufficient.
Condition 1: Mutual Exclusion
Mutual exclusion means that a resource can only be used by one process at a time; it cannot be simultaneously shared among multiple processes. If two processes could always share a resource freely, there would never be any reason to wait for it, and deadlock over that resource would be impossible.
Examples of resources that inherently require mutual exclusion: a printer (you generally don’t want two documents interleaving mid-print), an exclusive write lock on a database row, a single-instance hardware device, or a mutex protecting a critical section of code.
Not all resources require mutual exclusion, read-only files can typically be accessed by multiple processes simultaneously without conflict, which is why shareable resources generally don’t contribute to deadlock scenarios.
Why it matters for prevention: In principle, if a resource could always be shared, no process would ever need to wait for exclusive access, eliminating deadlock risk for that resource entirely. In practice, though, mutual exclusion is often intrinsic to the nature of certain resources (you genuinely cannot have two processes writing to the same file offset simultaneously without corruption), which is why this condition is rarely the practical target for prevention strategies, it’s often simply unavoidable for the resource types that matter most.
Condition 2: Hold and Wait
Hold and wait describes a situation where a process is currently holding at least one resource and is simultaneously requesting additional resources that are held by other processes. The process doesn’t release what it already has while it waits for more.
Process P1:
[holds Resource A] ----waiting to also acquire----> [Resource B, held by P2]
This condition is what allows partial resource accumulation to create dependency chains between processes. If a process could never hold one resource while waiting for another, entire chains of interdependency (which is what ultimately produces circular wait) simply couldn’t form.
Prevention techniques targeting this condition:
- Require processes to request all needed resources at once, before execution begins, and only start execution once everything is granted simultaneously. This eliminates hold-and-wait entirely, since a process never holds a partial set while waiting for more, either it gets everything up front, or it gets nothing and waits before starting.
- Require a process to release all currently held resources before requesting new ones. If P1 needs Resource B while already holding Resource A, it must first give up A, request both A and B together, and only proceed once both are granted.
Both approaches have real downsides in practice: the “request everything up front” approach can lead to poor resource utilization (a process might hold resources it won’t actually need until much later in its execution) and can be genuinely difficult to implement when a process’s future resource needs depend on runtime conditions that aren’t known in advance.
Condition 3: No Preemption
No preemption means that resources cannot be forcibly taken away from the process holding them; they can only be released voluntarily, typically when the process finishes using them or explicitly releases them.
If preemption were allowed freely, the OS could simply grab a resource away from a waiting/blocked process and hand it to another process that needs it, breaking any potential cycle of waiting before it could solidify into a true deadlock.
Prevention techniques targeting this condition:
- Allow preemption for certain resource types: If a process holding some resources requests another resource that isn’t immediately available, the OS can preempt (forcibly release) the resources the process is currently holding, giving them to other processes, and only restore them to the original process once it can be granted everything it needs at once. This works well for resources whose state can be easily saved and restored, like CPU registers or memory, but is much harder to apply to resources like a printer mid-job or a partially completed database transaction.
- State-saving preemption in schedulers: CPU scheduling itself is a classic example where preemption is not just possible but standard, a process can be forcibly context-switched out, its state saved, and resumed later, which is exactly why CPU contention alone doesn’t typically cause deadlocks the way exclusive-lock contention does.
This condition connects directly to the wound-wait deadlock prevention scheme, discussed in more depth elsewhere, where an older process can forcibly preempt (wound) a younger process holding a needed resource, directly breaking the no-preemption condition in a controlled, deadlock-safe way.
Condition 4: Circular Wait
Circular wait is the condition most people intuitively associate with deadlock, a closed loop of processes, each waiting for a resource held by the next process in the chain, eventually looping back to the first process.
Formally: there exists a set of processes {P0, P1, P2, …, Pn} such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on, up through Pn, which is waiting for a resource held by P0.
P0 --waits for resource held by--> P1 --waits for resource held by--> P2 --waits for resource held by--> P0
This is exactly the pattern that shows up as a cycle in a Resource Allocation Graph, and for single-instance resource systems, detecting a cycle in that graph is equivalent to detecting circular wait, and therefore deadlock.
Prevention techniques targeting this condition:
- Impose a strict, total ordering on resource types, and require that every process request resources only in increasing order according to that ordering. If a process needs both Resource A and Resource B, and A is ordered before B, it must always request A first, then B, never the reverse. This structurally makes circular wait impossible: for a cycle to exist, at least one process would need to request a lower-ordered resource while already holding a higher-ordered one, which is exactly what the ordering rule forbids.
This is one of the most practically popular deadlock prevention techniques precisely because it’s relatively easy to implement (assign a global numeric order to lock types) and doesn’t require the kind of advance knowledge about maximum resource needs that avoidance algorithms like the Banker’s Algorithm demand. Many real-world codebases enforce lock-ordering conventions (sometimes checked automatically by tools) for exactly this reason.
Why All Four Conditions Must Hold Simultaneously
It’s worth emphasizing precisely what “necessary condition” means here: deadlock cannot occur unless all four conditions are true at the same time. If any single one of them is false, deadlock is structurally impossible, regardless of what the other three conditions look like.
This gives deadlock prevention strategies their fundamental design principle: you don’t need an elaborate, comprehensive solution, you only need to reliably break one condition, and the system becomes provably deadlock-free.
| Condition | If broken… |
|---|---|
| Mutual Exclusion | Resources become shareable, no process ever needs exclusive access, so no waiting-for-exclusivity scenario can arise |
| Hold and Wait | Processes never hold partial resources while requesting more, so dependency chains between processes can’t accumulate |
| No Preemption | Resources can be forcibly reassigned, so a stuck process can always have its resources taken and given to someone who can make progress |
| Circular Wait | The wait-for relationships between processes can never form a closed loop, no matter how contention plays out |
A Worked Example Showing All Four Conditions Present
Consider two threads in a multithreaded application:
Thread T1:
lock(mutex_A)
// do some work
lock(mutex_B) // T1 now waits here if mutex_B is held elsewhere
// do more work
unlock(mutex_B)
unlock(mutex_A)
Thread T2:
lock(mutex_B)
// do some work
lock(mutex_A) // T2 now waits here if mutex_A is held elsewhere
// do more work
unlock(mutex_A)
unlock(mutex_B)
If T1 acquires mutex_A and T2 acquires mutex_B at roughly the same time, then T1 tries to acquire mutex_B (held by T2) while T2 tries to acquire mutex_A (held by T1), we get:
- Mutual exclusion: True, mutexes are exclusive by definition.
- Hold and wait: True, each thread holds one mutex while waiting for the other.
- No preemption: True, mutexes in most threading libraries cannot be forcibly taken from the thread holding them.
- Circular wait: True, T1 → mutex_B → T2 → mutex_A → T1 forms a closed cycle.
All four conditions hold, deadlock occurs. This is precisely the textbook example that motivates the most common real-world fix: always acquire mutex_A before mutex_B in both threads, enforcing a global lock ordering, which directly breaks the circular wait condition and eliminates this specific deadlock scenario entirely.
Practical Relevance Across Systems
- Operating system kernels (Linux, Windows) rely heavily on lock-ordering conventions internally, and Linux’s
lockdepvalidator specifically checks for potential circular-wait violations across the many locks used throughout the kernel. - Database systems deal with all four conditions constantly, since row/table locks are inherently exclusive (mutual exclusion), transactions commonly acquire multiple locks over their lifetime (hold and wait), locks generally can’t be preempted mid-transaction without aborting it, and concurrent transactions touching overlapping data can easily form circular wait patterns, which is exactly why most database engines include automatic deadlock detection and victim-transaction rollback as a core feature.
- Distributed systems face the same four conditions, just spread across machines, making circular wait detection harder since no single node has full visibility into the global wait-for graph.
Summary
Deadlock requires four conditions to hold simultaneously: mutual exclusion (resources aren’t shareable), hold and wait (processes hold resources while requesting more), no preemption (resources can’t be forcibly reclaimed), and circular wait (a closed loop of processes each waiting on the next). Because all four are strictly necessary, breaking any single one is sufficient to make deadlock structurally impossible, which is exactly the principle underlying every deadlock prevention technique, from enforced lock ordering (targeting circular wait) to requesting all resources upfront (targeting hold and wait) to allowing forced resource preemption (targeting no preemption). Understanding these four conditions isn’t just academic, it’s the direct foundation for how real operating systems, databases, and concurrent applications are designed to avoid getting permanently stuck.
Frequently Asked Questions
Are all four conditions always present in every deadlock? Yes, by definition. If even one condition is absent, deadlock cannot occur. This is what makes them “necessary” conditions.
Which condition is easiest to target for prevention? In practice, circular wait is the most commonly targeted condition, since enforcing a strict resource-ordering convention is relatively straightforward to implement and doesn’t require advance knowledge of processes’ full resource needs, unlike avoidance techniques.
Can mutual exclusion realistically be eliminated for most resources? Not usually. Many resources are inherently exclusive by nature (a write lock, a physical device), so this condition is rarely a practical target; it’s more of a theoretical starting point in the classic four-condition framework.
Is breaking one condition enough, or do you need to address all four? Breaking just one condition reliably is mathematically sufficient to make deadlock impossible, since all four are individually necessary. You don’t need to address all four simultaneously.
References
- Coffman, E.G., Elphick, M., and Shoshani, A., “System Deadlocks,” ACM Computing Surveys, 1971
- Silberschatz, Galvin, and Gagne, Operating System Concepts, Wiley.
- The Linux Kernel Documentation on lockdep and lock ordering: kernel.org