OS Notes
The four necessary conditions for deadlock: mutual exclusion, hold and wait, no preemption, and circular wait. Detailed explanation with examples of each condition.
Introduction
For a deadlock to occur, it is not enough to have just one problematic condition — all four conditions must hold simultaneously. These are known as the Coffman conditions (named after Edward Coffman Jr. who formalized them in 1971). Think of them like the ingredients for a fire: you need fuel, oxygen, heat, AND a chemical chain reaction. Remove any one, and the fire cannot start. Similarly, eliminate any one Coffman condition, and deadlock becomes impossible.
Understanding these four conditions is crucial because deadlock prevention works by ensuring at least one condition can never be satisfied.
The Four Conditions
Condition 1: Mutual Exclusion
At least one resource must be held in a non-sharable mode. Only one process can use the resource at a time. If another process requests it, that process must wait.
Example: A printer can only print one document at a time. If Process A is printing, Process B must wait. You cannot have two processes simultaneously sending different data to the same printer — the output would be garbled.
Important: Not all resources require mutual exclusion. Read-only files can be shared by multiple processes simultaneously without issues. Mutual exclusion is only needed for resources that can be corrupted by concurrent access.
Sharable Resources (no mutual exclusion needed)
- Read-only files
- Program code (text segment)
- Shared memory marked read-only
Non-Sharable Resources (mutual exclusion required)
- Printers
- Write-access files
- Tape drives
- Mutex locks
Condition 2: Hold and Wait
A process must be holding at least one resource while simultaneously waiting to acquire additional resources held by other processes.
Example: Process P1 holds the printer AND is waiting for the scanner (which P2 holds). P1 will not release the printer while waiting — it holds and waits.
| │ Process P1 | │ |
| │ Currently HOLDING | Printer, File A │ |
| │ Currently WAITING FOR | Scanner │ |
| │ Process P2 | │ |
| │ Currently HOLDING | Scanner │ |
| │ Currently WAITING FOR | Printer │ |
Real-world analogy: Imagine you are holding a fork in your right hand and waiting for a knife that someone else is using. You refuse to put down the fork while waiting. This is hold-and-wait.
Condition 3: No Preemption
Resources cannot be forcibly taken away from a process. A resource can only be released voluntarily by the process holding it, after it has completed its task.
Example: If Process A holds a mutex lock, the OS cannot simply grab that lock away from A and give it to B. Process A must explicitly call unlock() when it is done.
Why this matters: Some resources genuinely cannot be preempted without causing data corruption. If a process is halfway through writing to a file and you forcibly take the file handle, the file could be left in an inconsistent state.
Resources that CAN be preempted (safely)
- CPU (timer interrupt → context switch)
- Memory pages (can be swapped to disk)
Resources that CANNOT be easily preempted
- Mutex locks (preemption could corrupt shared data)
- Printers mid-job (half-printed document is useless)
- Database write locks (transaction integrity)
Condition 4: Circular Wait
There must exist a circular chain of two or more processes, where each process is waiting for a resource held by the next process in the chain.
Example with 3 processes:
Example with 2 processes (simplest case):
Why ALL Four Must Hold Simultaneously
If any one condition is absent, deadlock cannot occur:
| Missing Condition | Why No Deadlock |
|---|---|
| No Mutual Exclusion | Processes can share resources — no waiting needed |
| No Hold and Wait | Processes request all resources at once or release before requesting new ones |
| Preemption Allowed | OS can take resources from one process and give to another |
| No Circular Wait | The chain of dependencies has an endpoint — someone can eventually proceed |
Identifying Conditions in Practice
Let us analyze a real scenario. Two database transactions:
-- Transaction T1:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- Locks row 1
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- Needs lock on row 2
-- Transaction T2:
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2; -- Locks row 2
UPDATE accounts SET balance = balance + 50 WHERE id = 1; -- Needs lock on row 1- Mutual Exclusion: Yes — row locks are exclusive for writes
- Hold and Wait: Yes — T1 holds lock on row 1 while waiting for row 2
- No Preemption: Yes — database does not forcibly revoke locks (that would break ACID)
- Circular Wait: Yes — T1→row2→T2→row1→T1
All four conditions hold → deadlock is possible (and will occur if timing is right).
Common Exam Questions
Q: Can deadlock occur with only one process? A: No. A single process cannot form a circular wait with itself (unless it tries to lock a non-recursive mutex it already holds — but that is really a programming bug, not a multi-process deadlock).
Q: Can deadlock occur with sharable resources? A: No. If resources are sharable, condition 1 (mutual exclusion) does not hold, so deadlock is impossible.
Q: Are these conditions sufficient for deadlock? A: They are necessary — deadlock cannot occur without all four. They are also sufficient — if all four hold, deadlock exists.
Key Takeaways
- Four Coffman conditions must ALL hold simultaneously for deadlock to occur
- Mutual Exclusion: at least one resource is non-sharable
- Hold and Wait: processes hold resources while waiting for additional ones
- No Preemption: resources cannot be forcibly taken away
- Circular Wait: circular chain of processes each waiting for the next one's resource
- Removing ANY one condition prevents deadlock entirely
- Deadlock prevention strategies work by attacking one or more of these conditions
- In real systems, identifying which conditions hold helps diagnose and fix deadlock-prone code
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Necessary Conditions for Deadlock.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, deadlocks, necessary, conditions, for
Related Operating Systems Topics