Deadlocks

1Deadlock is a cycle of waiting

maya's save thread holds a lock on essay.txt. A backup process holds the printer. Save needs the printer to print the file; backup needs essay.txt to copy it. Each waits for the other. Neither can run. That standstill is deadlock: a set of processes in which every member is Waiting for a resource another member holds, and no one can make progress.

Starvation is different: one process waits a long time while others keep running. In deadlock nobody in the set runs. The next concepts are the four conditions that must all hold, the picture of the wait, and the arithmetic that refuses an unsafe grant.

Figure. Each holds what the other wants. The two wait-edges form a cycle. That cycle is the deadlock.

The standstill

1. HoldSave has the file. Backup has the printer.
2. WaitSave wants the printer. Backup wants the file.
3. No progressNeither can finish. That pair is deadlocked.

Coding lab. A wait-for cycle runs in the app, with checks on your output.

2Coffman's four conditions

Coffman's four conditions are all necessary for deadlock. Mutual exclusion: at least one resource is not shareable — the file lock is held by one process. Hold and wait: a process keeps what it has while asking for more — save keeps the file while asking for the printer. No preemption: the kernel will not yank the file lock away. Circular wait: a cycle of waits, save → backup → save.

Break any one and deadlock cannot form. Make the printer sharable, force save to release the file before asking for the printer, allow preemption of the lock, or impose an order (always lock file before printer) so a cycle cannot appear. The mnemonic MHNC is the four names in that order.

Figure. P0 holds R1 and waits for R2; P1 holds R2 and waits for R1 — a closed wait chain and a deadlock.

How it works

1. Mutual exclusionAt least one resource admits only one holder at a time — a printer, a mutex, a tape drive.
2. Hold and waitA process keeps resources already allocated while blocking on a new request.
3. No preemptionThe OS cannot grab a resource back; only the holding process may release it.
4. Circular waitP0 waits on P1's resource, P1 waits on P2's, and the chain closes back on P0.

3The resource-allocation graph

The resource-allocation graph draws processes as circles and resource types as boxes. An assignment edge from a resource to a process means 'this instance is held'. A request edge from a process to a resource means 'this process is waiting'. save → printer and printer → backup and backup → file and file → save is a cycle.

When every resource type has a single instance, a cycle is necessary and sufficient for deadlock. When a type has several instances, a cycle is only a warning — a different instance might still free someone. The wait-for graph in the lab collapses each held resource away and keeps only process-to-process waits; a cycle there is the deadlock among those processes.

Reuse the directed cycle already drawn under Coffman deadlock conditions: process nodes hold request/assignment edges to single-instance resource boxes. A cycle there means deadlock for sure; with multiple instances a cycle is only necessary, not sufficient.

How it works

1. Draw assignmentsAn arrow from resource R to process P means P currently holds one unit of R.
2. Draw requestsAn arrow from P to R means P is blocked waiting for R.
3. Single instanceIf every box has one dot inside, any cycle is a deadlock.
4. Multiple instancesA cycle may still resolve if another process releases an instance — treat it as a warning, not proof.

4Banker's algorithm and a safe state

Banker's algorithm is avoidance: grant a request only if the resulting state is safe. A state is safe when there exists an order in which every process can finish using what is free now plus what earlier finishers release. Track Allocation (what each process holds), Max (what it might still claim), and Need = Max − Allocation.

The tape-drive walk already on this card uses twelve identical drives and three processes with Max/Allocation (10/5), (4/2), (9/2). Available is 12 − (5+2+2) = 3. Need is 5, 2, 7. P1's need 2 fits in 3, so P1 can run and release 2, Available becomes 5, then P0, then P2. The safe sequence is P1, P0, P2. Unsafe is not already deadlocked — it only means some future request could trap you.

Figure. Safe if some order exists where each process's Need fits in Available plus prior releases — Banker's walks that order.

How it works

1. Compute NeedNeed[i] = Max[i] − Allocation[i] for each process.
2. Find a runnable processPick any process whose Need[i] is less than or equal to Available.
3. Simulate finishAssume it runs to completion and releases Allocation[i]; add those units back to Available.
4. Repeat or failIf every process can be scheduled this way, the state is safe; if you get stuck, it is unsafe.

5Minimum units that guarantee freedom

A counting question asks: N processes, each needing at most M units of one resource, what is the smallest total that guarantees no deadlock? Give every process M−1 units and they can all sit one short. That uses N(M−1) units. One extra unit lets someone finish. The bound is N(M−1)+1.

Three processes, two units each: N=3, M=2, minimum 3×1+1 = 4. With 3 units each process can hold 1 and nobody can take the second. With 4, one spare remains and someone finishes.

Figure. Worst case: each process holds Max−1. One spare unit above that sum lets someone finish and release — so four identical units free three processes that each need two.

How it works

1. Worst-case holdEach of N processes could hold Max_i − 1 units and still want one more.
2. Sum the holdsAdd (Max_i − 1) across all processes — that is the worst simultaneous occupation.
3. Add one spareOne extra unit guarantees someone can finish and release, so no circular wait can persist.