Deadlocks
A deadlock is a permanent traffic jam inside the operating system: every process holds something the next one needs. Build one yourself, then learn how the OS avoids it.
A set of processes is deadlocked when every process in the set is waiting for an event that only another process in the same set can cause. Since nobody can proceed, they wait forever.
Real-world analogy: The narrow bridge
Mutual exclusion
At least one resource cannot be shared. Only one process can use it at a time, so other processes must wait.
Hold and wait
A process keeps one resource while asking for another resource that is currently being used by someone else.
No preemption
The OS cannot forcibly take a resource away from a process. A resource is released only when the process voluntarily gives it up.
Circular wait
A chain of processes forms: P1 waits for P2, P2 waits for P3, and eventually Pn waits for P1. Each process is waiting on the next one in the loop.
Break any one condition and a deadlock becomes impossible — that is exactly how deadlock prevention works.
P1
P2
Resource Allocation Graph edges
No edges yet — assign some resources above.
Edit Allocation, Max and Available. The algorithm recomputes Need, finds a safe sequence and shows every step. Try changing Available to [1, 0, 0] to see an unsafe state.
| Process | Allocation | Max | Need = Max − Allocation | ||||
|---|---|---|---|---|---|---|---|
| P0 | [7, 4, 3] | ||||||
| P1 | [1, 2, 2] | ||||||
| P2 | [6, 0, 0] | ||||||
| P3 | [0, 1, 1] | ||||||
| P4 | [4, 3, 1] | ||||||
- Work = Available = [3, 3, 2]
- P1: Need = [1, 2, 2] ≤ Work = [3, 3, 2] → run it. Work becomes [5, 3, 2] after it releases its allocation.
- P3: Need = [0, 1, 1] ≤ Work = [5, 3, 2] → run it. Work becomes [7, 4, 3] after it releases its allocation.
- P4: Need = [4, 3, 1] ≤ Work = [7, 4, 3] → run it. Work becomes [7, 4, 5] after it releases its allocation.
- P0: Need = [7, 4, 3] ≤ Work = [7, 4, 5] → run it. Work becomes [7, 5, 5] after it releases its allocation.
- P2: Need = [6, 0, 0] ≤ Work = [7, 5, 5] → run it. Work becomes [10, 5, 7] after it releases its allocation.
- Prevention — design the system so one Coffman condition can never hold (e.g. request all resources at once, or order resources numerically).
- Avoidance — grant a request only if the resulting state is safe (Banker's Algorithm).
- Detection & recovery — allow deadlocks, detect cycles periodically, then kill a process or preempt a resource.
- Ignore it — the “ostrich algorithm”, used by most general-purpose operating systems because deadlocks are rare.
1. How many Coffman conditions must hold simultaneously for a deadlock?
2. The Banker's Algorithm is a technique for deadlock:
3. In a resource allocation graph, an edge from a resource to a process means:
A system has 12 tape drives. P0 holds 5 and may need 10 in total, P1 holds 2 and may need 4, P2 holds 2 and may need 9. Is the state safe?