Operating Systems · Lesson 5 of 9 · Updated ·
Deadlocks — The 4 Conditions, Prevention, Avoidance and Banker's Algorithm
A deadlock is when a set of processes are all waiting for each other, so none can ever continue.
Real-life version: two cars meet on a one-lane bridge from opposite ends; neither will reverse.
1. The four necessary conditions (Coffman)
A deadlock can happen only if all four hold at the same time:
- Mutual exclusion — a resource can be used by only one process at a time.
- Hold and wait — a process holds one resource while waiting for another.
- No preemption — resources can't be taken away forcibly.
- Circular wait — P1 waits for P2, P2 waits for … Pn, Pn waits for P1.
Break any one and deadlock is impossible.
2. Handling deadlocks: four strategies
| Strategy | Idea |
|---|---|
| Prevention | design the system so one condition can never hold |
| Avoidance | check each request; grant only if the system stays safe (Banker's) |
| Detection & recovery | let deadlocks happen, detect cycles, then recover |
| Ignore it | "ostrich algorithm" — reboot if it happens (most desktop OSes) |
Prevention examples
- Break hold and wait: request all resources at once.
- Break no preemption: if a request fails, release what you hold.
- Break circular wait: number resources and always request them in increasing order (the most practical fix — also used with database locks).
3. Avoidance: the Banker's algorithm
The system is safe if there's some order (a safe sequence) in which every process can get its maximum need and finish.
Need = Max − Allocation. Available resources (A, B, C) = (3, 3, 2).
| Process | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
Find a safe sequence: repeatedly pick a process whose Need ≤ Available; it finishes and returns its allocation.
| Step | Pick | Need ≤ Available? | Available after it finishes |
|---|---|---|---|
| 1 | P1 | (1,2,2) ≤ (3,3,2) ✓ | (3,3,2) + (2,0,0) = (5,3,2) |
| 2 | P3 | (0,1,1) ≤ (5,3,2) ✓ | + (2,1,1) = (7,4,3) |
| 3 | P4 | (4,3,1) ≤ (7,4,3) ✓ | + (0,0,2) = (7,4,5) |
| 4 | P0 | (7,4,3) ≤ (7,4,5) ✓ | + (0,1,0) = (7,5,5) |
| 5 | P2 | (6,0,0) ≤ (7,5,5) ✓ | + (3,0,2) = (10,5,7) |
Safe sequence: ⟨P1, P3, P4, P0, P2⟩ → the system is in a safe state. (Other safe sequences may exist.)
When a new request arrives, the OS pretends to grant it, runs this check, and grants it only if the state stays safe.
4. Detection and recovery
- Draw a wait-for graph; a cycle means deadlock (for single-instance resources).
- Recover by terminating a process (or all deadlocked ones) or preempting resources and rolling back.
5. Deadlock vs starvation
| Deadlock | Starvation | |
|---|---|---|
| What | processes wait for each other forever | a process waits indefinitely while others progress |
| System progress | stuck for those processes | others keep running |
| Fix | prevent/avoid/detect | aging, fair scheduling |
Common mistakes
- Saying one condition is enough for deadlock — all four are needed.
- Thinking an unsafe state is always a deadlock. Unsafe means a deadlock may happen.
- Forgetting to add back the finished process's allocation in the Banker's table.
Quick recap
- Four conditions: mutual exclusion, hold and wait, no preemption, circular wait.
- Prevention breaks a condition; avoidance (Banker's) keeps the state safe.
- Need = Max − Allocation; find a safe sequence by finishing processes one by one.
- Detection: cycles in the wait-for graph; recover by killing or preempting.