The idea: let deadlocks happen, then find them
A deadlock is a set of processes where each one is blocked waiting for something another one in the set holds. None of them can run, so none of them will ever release anything. An OS can try to make deadlocks impossible (prevention), refuse risky requests (avoidance, the Banker's algorithm), or grant everything it can and detect deadlocks after the fact, then break them. This page shows detection and recovery.
The four Coffman conditions
Coffman, Elphick and Shoshani (1971) showed that a deadlock can only happen when all four hold together:
- Mutual exclusion: an instance of a resource is held by one process at a time.
- Hold and wait: a process holds some instances while it waits for more.
- No preemption: the OS never takes an instance away; the holder must release it.
- Circular wait: P1 waits for P2, P2 waits for P3, …, and the last waits for P1.
The panel under the graph lights each condition that holds right now. On this page 1 and 3 hold whenever something is held; 2 and 4 depend on the requests.
The resource-allocation graph
The OS can draw its state as a graph. Processes are circles. A resource type is a box with one slot per instance (R2 has two identical instances, like two printers). A request edge P → R means P is blocked waiting for an instance of R. An assignment edge from an instance to P means P holds that instance. A request that can be served at once turns straight into an assignment edge.
A cycle, and when it is a deadlock
No cycle in the graph means no deadlock. If every resource on a cycle has one instance, the cycle is a deadlock: each process on it waits for the next one, forever (Demo: one instance each, cycle = deadlock).
With several instances, a cycle is necessary but not enough. In Demo: cycle but no deadlock (R2 has 2) the graph has the cycle P1 → R2 → P3 → R1 → P1, but the second R2 instance belongs to P4, which is not waiting. When P4 finishes, its R2 goes to P1, P1 finishes and gives R1 to P3 (Demo: P4 releases, the cycle breaks). That is why the OS needs an algorithm, not just a cycle search.
The detection algorithm
It looks like the Banker's safety check, with one change: it uses each process's current Request, not its worst-case Need. It asks: if every process that can get what it asked for runs to the end and returns everything, who is left?
Work = Available
Finish[i] = (Allocation[i] == 0) // holds nothing: cannot be in a deadlock
repeat:
find i with Finish[i] == false and Request[i] <= Work
if none: break
Work = Work + Allocation[i] // Pi finishes and gives everything back
Finish[i] = true
every Pi with Finish[i] == false is deadlocked
It is optimistic on purpose: a process that can get its request is assumed to finish. If it later asks for more and blocks, the next run of the algorithm will catch that. In Demo: several instances, real deadlock, Available = (0, 0, 0):
| Check | Request ≤ Work? | Work after |
|---|---|---|
| P1 | (0, 1, 0) ≤ (0, 0, 0)? no ✗ | (0, 0, 0) |
| P2 | (0, 0, 0) ≤ (0, 0, 0)? yes ✓ | (0, 0, 1) |
| P3 | (1, 0, 0) ≤ (0, 0, 1)? no ✗ | (0, 0, 1) |
| P4 | (1, 0, 0) ≤ (0, 0, 1)? no ✗ | (0, 0, 1) |
| P1 | (0, 1, 0) ≤ (0, 0, 1)? no ✗ | stop |
P2 finishes and returns R3, but nobody wanted R3. P1, P3 and P4 stay false: they are deadlocked. The cost is O(m × n²) for n processes and m resource types.
When to run it
Running it on every blocked request finds a deadlock at once and even names the request that caused it, but it costs time on every wait. Most systems run it on a timer, or when something looks stuck: CPU use drops, or a process has waited too long. PostgreSQL waits deadlock_timeout (1 s) before it searches its wait-for graph (PostgreSQL Lock Manager); InnoDB searches on every lock wait (Two-Phase Locking and Deadlock Detection).
Recovery: kill a victim, or take a resource
- Abort all deadlocked processes: simple, but throws away the most work.
- Abort one at a time, running detection after each, until the deadlock is gone. The victim is the cheapest one: fewest resources held, least CPU time used, lowest priority, easiest to restart. This page uses fewest instances held, then the youngest (Demo: recover, kill a victim, detect again: P4 holds one instance, the same as P1 and P3, and is the youngest).
- Preempt a resource: take an instance away and roll its holder back to a safe point. It needs checkpoints, and the same process must not be picked every time, or it starves.
Databases do exactly this: the victim transaction gets an error (MySQL ERROR 1213) and its locks are released.
Prevent, avoid, detect, or ignore
| Strategy | How | Cost |
|---|---|---|
| Prevention | Break a Coffman condition, usually with a global lock order (Dining Philosophers) | Programmers must follow the order |
| Avoidance | Grant only requests that keep the state safe (Banker's algorithm) | Needs every Max claim in advance |
| Detection | Grant freely, search for deadlocks, kill a victim | Lost work; the search itself |
| Ignore it | Assume deadlocks are rare; a person restarts the program | Hung programs |
General-purpose kernels such as Linux and Windows mostly ignore deadlocks between user programs: a program stuck on two mutexes just hangs. Inside the kernel, Linux uses prevention plus a checker: lockdep records the order in which every lock class is taken and warns when two orders could form a cycle, even if the deadlock never actually happened.
For the everyday two-lock deadlock in code and how a global lock order prevents it, see Deadlock from Lock Order.
What the page leaves out
Requests for several instances at once, and processes that come and go. Finding which request closed the cycle when detection runs on every request. Preemption with rollback and checkpoints. Distributed deadlock detection, where no single node sees the whole wait-for graph (edge chasing, timeouts). Livelock, where processes are not blocked but keep retrying without progress.
See where this page fits on the Operating Systems mind map.