Deadlocks
A deadlock is a set of processes each waiting for a resource held by another in the set, so none can proceed.
Cheat sheet
- ▸Coffman conditions (all four needed): Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait.
- ▸Prevention: break one condition (e.g., order resources to kill circular wait).
- ▸Avoidance: Banker's algorithm keeps the system in a safe state.
- ▸Detection: wait-for graph cycle (single instance) or detection algorithm.
- ▸Recovery: kill processes or preempt resources (rollback).
- ▸Ostrich approach: ignore it — used by most general-purpose OSes.
Handling strategies
| Strategy | Idea | Cost |
|---|---|---|
| Prevention | Break a Coffman condition | Low utilization |
| Avoidance | Banker's safe-state check | Needs max demand upfront |
| Detection + Recovery | Find cycle, then kill/preempt | Runtime overhead |
| Ignore | Reboot if it happens | Rare failures |
Visual
P1 ──holds──▶ R1 ◀──wants── P2 ▲ │ └──wants── R2 ◀──holds─────┘ (cycle ⇒ deadlock)
Top 10 campus interview questions
Quick quiz
1. Which is NOT a Coffman condition?
2. Banker's algorithm is used for deadlock:
3. Ordering resource requests breaks:
4. A cycle in a RAG with single-instance resources implies:
5. An unsafe state: