Deadlock: conditions, prevention and avoidance
Coffman's four conditions, the allocation graph and the cycle criterion proved, resource ordering proved, the banker's algorithm with an example, dining philosophers.
A deadlock is a situation in which a group of processes stays blocked forever, because each is waiting for a resource held by another in the group. It is the crossroads with four stopped cars, each waiting for the one on its right to go. In this lesson we look at the four necessary conditions, the resource allocation graph with the cycle criterion, prevention by ordering resources and its proof, the banker’s algorithm with an example, detection and the dining philosophers problem.
The four conditions
Coffman (1971) showed that a deadlock can occur only if four conditions hold simultaneously:
- mutual exclusion: resources are not shareable (a printer, a lock);
- hold and wait: a process holds resources while waiting for others;
- no preemption: resources cannot be taken away by force, only released voluntarily;
- circular wait: there is a chain of processes in which each waits for a resource of the next, and the last for one of the first.
Preventing any one of them makes deadlock impossible.
The allocation graph
The relations between processes and resources are represented by a graph: an edge from a resource to a process means the resource is assigned to that process; an edge from a process to a resource means a pending request.
Theorem. If every resource has a single instance, the system is deadlocked if and only if the allocation graph contains a cycle.
Proof. If there is a cycle, each process in the cycle waits for a resource, which has a single instance and is assigned to the next process of the cycle, also waiting: nobody can proceed or release, so they are deadlocked. Conversely, if there is a deadlock, start from a blocked process: it waits for a resource, assigned to another process, which is in turn blocked (otherwise it would finish and release it); following the chain in the finite graph we must sooner or later return to an already visited process, closing a cycle. ∎
With multi-instance resources a cycle is necessary but not sufficient: another instance may be freed and break the wait.
Prevention
One of the four conditions is denied. The most practical is circular wait.
Theorem. If resources are numbered and every process requests them only in increasing order of number, circular wait cannot occur.
Proof. Suppose, for contradiction, a cycle 
, where 
holds resource 
and waits for 
, held by 
(and 
waits for 
). Since holds and requests , by the rule 
. Along the cycle we get 
, impossible. ∎
This is the rule used in kernels: locks have a documented order, and in Linux a checking tool (lockdep) reports at run time every violation of the order, even if the deadlock has not yet occurred. The other conditions are denied by requesting all resources together at the start (against hold and wait, but it wastes resources) or by allowing preemption for resources whose state can be saved, such as the CPU and memory.
The banker’s algorithm
Avoidance grants a request only if the resulting state is safe: there is an order in which all processes can obtain their declared maximum and terminate. The banker’s algorithm (Dijkstra) performs this check.
Example. One resource with 14 instances and three processes:
| Process | Maximum | Allocated | Remaining need |
|---|---|---|---|
| P1 | 10 | 6 | 4 |
| P2 | 5 | 3 | 2 |
| P3 | 8 | 2 | 6 |
instances are available. The state is safe: P2 (need 2) can finish and return 3, available 6; then P1 (4), available 12; then P3. If now P3 requests 2 instances and they are granted, 1 remains available and P3’s need becomes 4: no process can be sure to finish any more (P2 needs 2, P1 4, P3 4). The state would not be safe, and the request is postponed, even though it would not necessarily cause a deadlock.
The algorithm requires knowing each process’s maximum in advance and costs 
per request, with 
resource types: it is used in specialised systems, not in general-purpose operating systems.
Detection and recovery
Many systems let deadlock happen, detect it by looking for cycles in the wait-for graph and then recover: they terminate one of the processes or take a resource away from it and roll it back to an earlier point. This is the strategy of databases, which abort a transaction and re-run it (Information Systems lesson on transactions). General-purpose operating systems, for application locks, often do nothing: they ignore the problem, leaving applications the task of avoiding it.
The dining philosophers
Five philosophers sit at a round table with a fork between each pair; two are needed to eat. If all simultaneously take the fork on their left, each waits forever for the one on the right: a circular wait. The ordering solution: number the forks and always take the lower-numbered one first. Then one philosopher, the one between fork 5 and fork 1, takes the right one first, and the cycle is broken.
