Two people meet in the middle of a footbridge just wide enough for one. Each steps aside to let the other pass — but they both step the same way, and end up facing each other again. Then again. Neither will back up first, because "the other one should go." They can stand there forever. Nobody is broken; nobody is doing anything wrong; and yet nothing can happen.

That is a deadlock. In an operating system it looks like this: a set of processes are each holding a resource and waiting for a resource held by another process in the set — arranged in a circle, so every one of them is blocked on a neighbour that will never let go. When it happens, those processes are stuck permanently. They will not use any more CPU, they will not release what they hold, and left alone they will wait until the machine is rebooted.

Deadlock is the dark twin of the locks and semaphores we use to keep concurrent code correct. The very mechanism that stops two threads from trampling each other's data — making them wait for a lock — is exactly the mechanism that can freeze them solid. And unlike a starved process that the scheduler might eventually get to, a deadlocked process is not waiting for its turn. It is waiting for something that can never arrive.

The classic: two threads, two locks, opposite order

Here is the smallest deadlock you can write. Two threads each need both lock A and lock B. Thread 1 grabs A then reaches for B; Thread 2 grabs B then reaches for A. Read the timeline down the middle:

Notice how little it takes. No bug, no crash, no bad data — just two correct threads that happened to acquire the same two locks in opposite orders, at the wrong instant. The interleaving is a matter of luck, which is what makes deadlocks so nasty: your program runs fine ten thousand times and wedges on the ten-thousand-and-first.

When exactly can it happen? The four Coffman conditions

In 1971 Edward Coffman and colleagues pinned down precisely what a deadlock needs. The beautiful part is that all four conditions must hold at the same time — knock out any single one, and deadlock becomes impossible. That is the lever every prevention strategy pulls.

Read them back against the footbridge: the bridge holds one person at a time (mutual exclusion); each person stands their ground while wanting the other's spot (hold and wait); no one can be shoved backwards (no preemption); and each waits on the other, a cycle of length two (circular wait). Remove any one — widen the bridge, make someone give up their spot, allow a shove — and the jam clears.

Seeing the cycle: the resource-allocation graph

The cleanest way to spot a deadlock is to draw it. In a resource-allocation graph we use two kinds of node and two kinds of arrow:

• a circle is a process; a square is a resource;
• an assignment edge points resource → process ("this resource is held by that process");
• a request edge points process → resource ("this process is waiting for that resource").

Step through the graph below. P_1 holds R_1 and wants R_2; P_2 holds R_2 and wants R_1. Watch the last arrow close the loop:

The four arrows form a directed cycle P_1 \to R_2 \to P_2 \to R_1 \to P_1. With one unit of each resource, that cycle is the deadlock — a perfect picture of the circular-wait condition. Detecting deadlock (for single-instance resources) reduces to a plain question you already know how to answer: does this directed graph contain a cycle?

Three ways to deal with it

An operating system has three honest strategies (and one dishonest one we'll get to):

• Prevention — design the system so that one of the four Coffman conditions can never hold. Kill any one pillar and deadlock is structurally impossible.
• Avoidance — allow the conditions in principle, but before granting each request, check that doing so leaves the system in a safe state. Refuse (make the process wait) if it wouldn't. This is the banker's algorithm.
• Detection & recovery — let deadlocks happen, but periodically search the resource-allocation graph for a cycle; when one is found, recover by aborting a process or forcibly preempting (rolling back) a resource.

Each targets a different point on the spectrum from "never risk it" to "clean up afterwards." How you choose depends on how often deadlock would occur and how expensive it is to detect versus to avoid.

How prevention negates each condition

Prevention is delightfully concrete: pick one Coffman pillar and make it structurally impossible.

• Negate mutual exclusion — make resources shareable where you can (read-only files, lock-free data structures). Not always possible: a printer really can only serve one job at a time.
• Negate hold-and-wait — require a process to request all its resources at once, atomically, and hold none while waiting for the rest. (Downside: it must grab everything up front, hurting utilisation.)
• Negate no-preemption — if a process holding some resources requests one it can't get, make it release everything and try again later. Works for state you can save and restore (like CPU registers); useless for a half-printed page.
• Negate circular wait — impose a total ordering on resources and require every process to request them in increasing order (the lock-ordering trick from earlier). No cycle can form on a strictly increasing chain.

Avoidance: the banker's algorithm

Dijkstra's banker's algorithm imagines the OS as a cautious banker. Each customer (process) declares up front the maximum it might ever need. The banker grants a request only if, after granting it, there still exists some order in which every customer can be given the rest of what it needs, finish, and return everything. Such an order is a safe sequence, and a state that has one is a safe state.

The bookkeeping uses four tables, over n processes and resource types:

• Available — units of each resource currently free;
• Max — each process's declared maximum demand;
• Allocation — what each process holds right now;
• Need = Max - Allocation — what it might still ask for.

A worked safety check

Five processes P_0 \ldots P_4, three resource types A, B, C. Currently Available = (3, 3, 2). Here are Max and Allocation, and the Need we get by subtracting cell by cell:

Now the safety algorithm. Keep a running Work vector of what's free, starting at Available. Repeatedly find any unfinished process whose Need ≤ Work (component by component); pretend it runs, finishes, and hands back everything it held — so Work += Allocation. Watch Work grow:

Every process finished, so the state is safe and a safe sequence is \langle P_1, P_3, P_4, P_0, P_2 \rangle. (Others exist — the algorithm just needs to find one.) Had we reached a point where no unfinished process fit within Work, the state would be unsafe, and the banker would have refused the request that led there. Crucially, unsafe is not the same as deadlocked — it means deadlock has become possible, and a cautious banker refuses to go there.

The safety check, in code

Here is the whole safety algorithm on that exact example. It computes Need, grows the Work vector, and reports whether the state is safe together with a safe sequence. Press Run — then try editing available down to [1, 3, 2] and see the verdict flip:

Detection, and the lazy option

If you don't want the up-front cost of avoidance, you can let deadlocks form and hunt them down. Detection runs a cycle-search (for single-instance resources) or a banker-style reduction (for multiple instances) over the current allocation state, on a schedule. When it finds a deadlock, recovery breaks the cycle the only ways it can: abort one or more deadlocked processes, or preempt a resource — roll a process back to an earlier checkpoint and hand its resource to someone else. Both are disruptive, which is why detection is run only as often as deadlocks are expected.