Deadlock: A Cycle of Waiting

From Threads & Concurrency: deadlock is the state where every participant waits on a resource held by another, so nothing progresses. It isn’t limited to threads — processes, database transactions, and distributed systems all deadlock. This topic gives the systematic treatment: how to represent allocation state, how to detect a deadlock, and the three strategies for handling it (prevention, avoidance, and detection/recovery).

The mental model for everything that follows is a graph: processes waiting for resources, resources granted to processes, and the cycles that form when the waits become circular.

Resources and Allocation State

A resource is anything a process needs exclusive access to: a CPU, a mutex, a database row lock, a tape drive, a chunk of memory. The OS (or application) keeps a snapshot of who holds what:

• Available — units of each resource not currently held.
• Allocation — units of each resource currently held by each process.
• Max — the maximum units each process may ever request (declared up front).
• Need — Max − Allocation, what each process still needs to finish.

This (Allocation, Max, Available) triple is the state of the system, and every algorithm in this topic is a decision made from it.

Resource-Allocation Graphs

Model the state as a directed graph with two node types — processes (circles) and resources (squares):

• Request edge — process → resource: “this process wants this resource.”
• Assignment edge — resource → process: “this resource is granted to this process.”

A cycle in this graph is a red flag. For a system with one instance of each resource, a cycle means deadlock. With multiple instances per resource, a cycle is necessary but not sufficient — which is why we need a stronger tool (the Banker’s algorithm) for the general case.

Wait-For Graphs

A wait-for graph compresses the picture: drop the resources, and draw a directed edge from process A to process B whenever A is waiting for a resource that B holds. Now the rule is clean:

A deadlock exists if and only if the wait-for graph contains a cycle.

This is the graph the kernel’s deadlock detector searches. When a “hung task” or lock-order report appears (see Threads & Concurrency), the watchdog found a cycle in exactly this graph and refused to let the wait block forever.

The Four Necessary Conditions (Recap)

From Threads & Concurrency, all four must hold simultaneously (Coffman conditions):

1. Mutual exclusion — resources are non-sharable.
2. Hold and wait — a process holds a resource while waiting for another.
3. No preemption — resources can’t be forcibly taken.
4. Circular wait — the processes form a cycle of waiting.

Break any one and deadlock disappears. The three classic strategies attack these conditions in different places.

Detection & Recovery

Detection: let processes run, periodically build the wait-for graph, and search for cycles. If one is found, recover.

Recovery options:

• Abort a deadlocked process (lose its work).
• Rollback the process to a checkpoint before it acquired its resources (needs transactional support).
• Preempt a resource from one process and give it to another (risk: the preempted process must be restarted or made to tolerate losing the resource).

Detection is cheap to run periodically but recovery is disruptive — this is the strategy of last resort, typical when resources are preemptible or the workload is rare/degenerate.

Prevention: Break a Condition

Prevention makes deadlock structurally impossible by attacking one Coffman condition:

• Break mutual exclusion: use sharable resources (read locks) wherever possible — limited.
• Break hold-and-wait: require every process to request all its resources up front, atomically. Simple but wasteful (a process holds resources it won’t use for a long time).
• Break no-preemption: allow the OS to steal a resource if the holder can be rolled back — costly in practice.
• Break circular wait: impose a global ordering on resources and require every process to acquire them in that order. This is the practical favorite: lock ordering (always acquire locks A→B→C) that you saw in Threads & Concurrency.

Prevention is simple and predictable, but it reduces resource utilization — processes hold resources longer than strictly needed.

Avoidance: The Banker’s Algorithm

Avoidance sits between prevention and detection: it doesn’t forbid patterns up front, but it checks every request and refuses any allocation that would leave the system in an unsafe state. The classic algorithm is the Banker’s algorithm (so named because it works like a bank that only grants loans it can still cover).

The state is safe if there exists an ordering of the processes such that each, in turn, could finish with the currently available resources — a safe sequence. Formally, a state is safe if a sequence P1, P2, …, Pn exists where for each Pi, its need is ≤ the sum of currently available resources plus everything already released by P1 … Pi−1.

Why safety matters: from a safe state, the OS can always guarantee that at least one process will be able to finish; that process releases its resources; the next can finish; and so on — so no deadlock can ever occur, no matter what the processes do next.

The Safety Algorithm

Given Available, Allocation, and Need:

1. Mark every process unfinished; let Work = Available.
2. Find an unfinished process Pi with Need[i] ≤ Work.
3. If found: mark it finished, add its Allocation[i] to Work, and repeat step 2.
4. If no such process exists and unfinished processes remain, the state is unsafe.

The Request Algorithm

When a process requests resources:

1. If Request > Need — error: the process asked for more than its declared max.
2. If Request > Available — the process must wait.
3. Otherwise, pretend to grant it: subtract from Available, add to Allocation, recompute Need, and run the safety algorithm.
4. If the pretended state is safe → grant. If unsafe → refuse and restore the original state.

The cost: each process must declare its maximum need up front, and the OS must refuse requests it could safely have granted in the short term because the future state would be unsafe. That conservatism is the price of the guarantee.

Worked Example

Five processes, three resource types A/B/C with Available = (3, 3, 2) at start:

Run the safety algorithm with Work = (3, 3, 2):

• P1: need (1,2,2) ≤ (3,3,2) ✓ → finish, Work = (3,3,2)+(2,0,0) = (5,3,2).
• P3: need (0,1,1) ≤ (5,3,2) ✓ → finish, Work = (7,4,3).
• P4: need (4,3,1) ≤ (7,4,3) ✓ → finish, Work = (7,4,5).
• P0: need (7,4,3) ≤ (7,4,5) ✓ → finish, Work = (7,5,5).
• P2: need (6,0,0) ≤ (7,5,5) ✓ → finish.

Safe sequence: P1 → P3 → P4 → P0 → P2 — the state is safe, and any request that preserves safety can be granted. The interactive Banker’s studio below animates this exact state; because it scans processes from P0 upward and takes the first whose need fits, it may walk a different-but-equally-valid safe order — watch for the property (each finish releases enough to cover the next), not the exact order.

Now consider a request that breaks it: if P2 requested (1, 0, 2) when Available = (3,3,2), the pretended state has Available = (2,3,0), and no unfinished process has a need ≤ that — the system would be unsafe, so the OS refuses.

When to Detect vs Avoid vs Prevent

Practice Trajectory

1. Given a resource-allocation state, draw the resource-allocation graph and the wait-for graph; state whether a cycle exists.
2. Hand-run the safety algorithm on the worked example above and confirm the sequence P1→P3→P4→P0→P2.
3. Take a safe state and a request that makes it unsafe; explain why granting it would permit a future deadlock.
4. Pick two of the Coffman conditions and describe a real API that breaks each (e.g., try_lock, transaction timeouts, lock ordering).
5. Trace a wait-for cycle in your running system: take two threads/mutexes acquired in opposite order, reproduce the hang, and fix it with a global lock order.

When It’s the Right Tool