Deadlocks I — Prevention & Avoidance

A deadlock is a standstill among a set of threads or processes where each one is waiting for a resource that another member of the set is holding — and because everyone in the set is waiting, nobody ever releases anything. The wait is circular and self-sustaining, so it never resolves on its own. This is worse than a slow program: a deadlocked thread consumes no CPU and shows no error, so from the outside the system looks alive while a part of it has silently died.

The smallest possible deadlock needs just two threads and two locks. Suppose thread T1 does lock(A) then lock(B), while thread T2 does lock(B) then lock(A). Most of the time this works by luck — one thread finishes both before the other starts. But if the scheduler pauses T1 right after it takes A, and lets T2 take B, then both are trapped: T1 holds A and blocks waiting for B; T2 holds B and blocks waiting for A. Each is politely waiting for the other, and both will wait until the machine is rebooted.

Thread T1                 Thread T2
---------                 ---------
lock(A)      <-- holds A
                          lock(B)   <-- holds B
lock(B)  ... blocks       lock(A) ... blocks
  (waits for T2)            (waits for T1)

Result: T1 holds A wanting B, T2 holds B wanting A.
        Neither can release. Deadlock.

You have already met this in disguise. The dining philosophers deadlock — five philosophers, each picking up the fork on their left and then waiting on the fork to their right — is exactly this pattern scaled up to a ring of five. Every philosopher holds one resource and waits for one held by a neighbour, closing a loop with no way out. Whether it is two mutexes or five forks, the structure is identical, and that structure is what the rest of this chapter learns to name and break.

In 1971, Edward Coffman and colleagues showed that a deadlock can only occur when four conditions hold simultaneously. This is the single most useful fact in the whole topic, because it turns a vague fear into a checklist. If all four are present, deadlock is possible; if you can guarantee that even one of them can never hold, deadlock is impossible. Every prevention strategy in this chapter is simply an attack on one of these four.

1. Mutual exclusion

At least one resource is non-shareable — only one thread may hold it at a time. A mutex or a printer is like this; a read-only constant is not. If a resource can be freely shared, it can never be the object of a deadlock.

2. Hold and wait

A thread that is already holding at least one resource requests additional resources without releasing what it holds. It grips and reaches at the same time — the posture that lets waits chain together.

3. No preemption

A resource cannot be forcibly taken away from the thread holding it; it is only released voluntarily, when that thread is done. Nobody can pry the lock out of a stuck thread’s hands.

4. Circular wait

There is a closed chain of waiting threads — T1 waits for something T2 holds, T2 for something T3 holds, and so on back around to T1. This is the loop that makes the standstill permanent.

Look back at the two-mutex example and you can tick every box. Mutex A and B are mutually exclusive by definition. T1 holds A while waiting for B — hold and wait. Neither thread can be forced to give up its lock — no preemption. And T1 waits on T2 which waits on T1 — a circular wait of length two. All four present, so deadlock is not just possible, it is exactly what happened.

The Coffman conditions tell you deadlock is possible; a resource-allocation graph lets you see whether it has actually happened. It is a directed graph with two kinds of node. Processes are circles, resources are squares, and we draw two kinds of edge between them: a request edge points from a process to a resource it is waiting for, and an assignment edge points from a resource to the process currently holding it.

Process node (circle)

A thread or process that can hold and request resources.

Resource node (square)

A resource type; dots inside it represent individual instances of that resource.

Request edge (P → R)

Process P is blocked, waiting for an instance of resource R.

Assignment edge (R → P)

One instance of resource R is currently allocated to process P.

Now the payoff. When every resource has just one instance, a cycle in this graph means a deadlock — always. Trace the two-mutex example: R1 → P1 (P1 holds A), P1 → R2 (P1 wants B), R2 → P2 (P2 holds B), P2 → R1 (P2 wants A). Follow the arrows and you walk in a circle that never lets you out. That closed loop is the circular-wait condition made visible, and it is a deadlock you can point at.

The rule needs one caveat, which matters in real systems. When a resource type has multiple instances — say a pool of four identical database connections — a cycle is necessary for deadlock but no longer sufficient. A thread waiting in the cycle might still be rescued when some process outside the cycle finishes and hands back an instance. So with multiple instances, a cycle is a warning, not a verdict; you need the fuller analysis we build up to with the Banker’s algorithm. With single-instance resources, though, a cycle is the whole story.

There are exactly four things a system can do about deadlock, and every real OS picks one (or a mix) per resource. They trade off engineering effort, runtime cost, and how much they restrict what programs are allowed to do. It is worth having all four in view before we dive into the two this chapter covers, because the choice between them is a genuine engineering decision, not a matter of one being simply correct.

Prevention

Structurally guarantee that at least one Coffman condition can never hold, at design time. Deadlock becomes impossible by construction. Cost: it constrains how programs may request resources.

Avoidance

Allow the conditions in principle, but examine each resource request at run time and grant it only if the system provably stays in a state from which everyone can still finish. Cost: you must know each process’s maximum needs in advance.

Detection & recovery

Let deadlocks happen, run an algorithm periodically to find the cycle, then recover — by killing a process or forcibly taking a resource back. Cost: the detection scan, and the damage of the recovery. This is the whole of the next chapter.

The ostrich algorithm

Ignore the problem entirely and hope it is rare enough not to matter. If a deadlock does occur, a human notices and reboots. Cost: occasional hangs — traded for zero overhead and zero restriction.

These sit on a spectrum of paranoia. Prevention and avoidance are proactive: they pay a cost on every program or every request to make sure deadlock never occurs. Detection and recovery is reactive: it pays nothing to prevent, but pays to clean up. The ostrich pays nothing at all and simply accepts the risk. Which is right depends entirely on how likely a deadlock is and how expensive one would be — a spreadsheet macro and an air-traffic-control system should not make the same choice.

Deadlock prevention means engineering the system so that one of the four Coffman conditions can never hold. Since all four are required together, killing any single one closes the door permanently. Let us walk each condition and see how you would attack it — and, honestly, what each attack costs, because most of them are impractical and one of them is what you will actually reach for.

Attack mutual exclusion

Make the resource shareable so it never needs exclusive holding. Sometimes possible — read-only data, or spooling print jobs to a queue so no process holds the printer. But many resources (a mutex protecting a mutable structure) are inherently exclusive, so this rarely applies.

Attack hold-and-wait

Require a thread to request every resource it will ever need at once, up front, and grant all or nothing — so it never holds one while waiting for another. Costs: you must know your needs in advance, resources sit idle while held long before use, and starvation looms if the full set is never all free at once.

Attack no-preemption

Allow a resource to be taken back. If a thread holding some locks requests one that is unavailable, make it release everything and retry later. Works for state that can be saved and restored — CPU registers, database transactions that can roll back — but you cannot un-print a page or un-send a byte.

Attack circular wait

Impose a global ordering on all resources and require every thread to acquire them in that increasing order. A cycle needs some thread to acquire a lower-numbered lock after a higher-numbered one — which the rule forbids — so no cycle can ever form.

That last one is the winner in real software, and it deserves its own paragraph because you will use it. It is called lock ordering. You assign every lock a rank — by address, by a documented numbering, by any consistent global rule — and you make it an ironclad convention that locks are always acquired in ascending rank. Go back to our two-mutex deadlock: if both T1 and T2 must take A before B, then T2 can no longer do lock(B) then lock(A). The opposite-order acquisition that created the cycle is simply not allowed to exist, so the deadlock cannot form.

Rule: lock(A) has rank 1, lock(B) has rank 2.
      Always acquire in ascending rank.

Thread T1: lock(A) then lock(B)   -- ranks 1,2  OK
Thread T2: lock(A) then lock(B)   -- ranks 1,2  OK  (was B,A before!)

Now no thread ever holds a rank-2 lock while
requesting a rank-1 lock, so the wait chain
can never bend back on itself. Cycle impossible.

Here is the strategy that surprises students: the most widely deployed approach to deadlock in general-purpose operating systems is to do nothing at all. It is affectionately called the ostrich algorithm — stick your head in the sand and pretend there is no problem. Both Linux and Windows, for the vast majority of their kernel resources, make no attempt to prevent, avoid, or detect deadlock. If one occurs, tough luck.

This sounds irresponsible until you price the alternatives. Prevention constrains how every program may request resources. Avoidance demands that every process declare its maximum needs up front and pays a safety check on every single request. Detection means periodically scanning a graph of every allocation in the system. All three impose a cost on every normal operation — and for a general-purpose OS running billions of ordinary, deadlock-free operations, that is a permanent tax paid to guard against a rare event.

Now weigh the other side. In a well-written system, kernel-level deadlocks are genuinely rare, because kernel developers use prevention by hand — lock ordering — where it matters. And when a deadlock does slip through, the consequence for a desktop or server is usually a hung process or, at worst, a reboot: annoying, but survivable and infrequent. Given rare occurrence and cheap recovery on one side, and a constant tax on the other, ignoring the problem is often the rational engineering choice, not laziness.

Prevention is blunt — it forbids whole patterns of behaviour to make deadlock structurally impossible. Deadlock avoidance is subtler and more permissive. It allows all four conditions in principle, but before granting any resource request, it asks a question: if I say yes to this, will the system still be able to guarantee that every process can eventually finish? If yes, grant it. If not, make the requesting process wait, even though the resource is free right now. Avoidance never lets the system wander into danger.

The key concept is the safe state. A state is safe if there exists at least one ordering of the processes — a safe sequence — in which each process can obtain all the resources it might still need, run to completion, and release everything, with each one’s remaining need met by what is currently available plus what all the earlier processes in the sequence release. If such a sequence exists, everyone can finish, so no deadlock is possible from here.

Safe state

A state from which some safe sequence exists — an order in which every process can finish. Deadlock is impossible from a safe state.

Unsafe state

A state with no guaranteed safe sequence. Deadlock is not certain, but it has become possible; the system can no longer promise everyone finishes.

Safe sequence

An ordering ⟨P1, P2, …⟩ where each Pi’s remaining maximum need can be satisfied by the currently free resources plus everything held by processes earlier in the sequence.

The crucial and often-missed subtlety: unsafe is not the same as deadlocked. An unsafe state is not a deadlock — it is a state from which a deadlock has merely become possible, depending on how future requests fall. Avoidance is conservative on purpose. It refuses to enter unsafe states at all, staying strictly inside the safe region, so it sacrifices some legal, would-have-been-fine allocations in exchange for an absolute guarantee that deadlock can never happen. To make that decision on every request, it needs to know, ahead of time, the maximum resources each process could ever demand.

The Banker’s algorithm, devised by Edsger Dijkstra, is the classic implementation of avoidance. The name captures the idea: a cautious banker never lends out so much cash that they cannot satisfy every customer’s credit line. Each customer declares a maximum they might ever borrow; the banker grants a loan only if, even after granting it, there is a way to eventually satisfy everyone. Swap "customer" for "process" and "cash" for "resource instances" and you have the algorithm exactly.

It works over four data structures. Available is a vector of how many instances of each resource are currently free. Max is a matrix of the maximum each process may ever request. Allocation is what each process currently holds. And Need, computed as Max minus Allocation, is what each process could still ask for. When a process makes a request, the algorithm pretends to grant it, then runs a safety check: does a safe sequence still exist? If yes, the grant stands; if no, it is rolled back and the process waits.

Available

Instances of each resource type currently free and grantable.

Max

The most each process could ever request — declared up front. This is the demanding precondition of the whole method.

Allocation

How much of each resource each process currently holds.

Need = Max − Allocation

What each process might still request before it can finish.

Safety check

Repeatedly find a process whose Need fits within a running Work total (started at Available); "run" it, add its Allocation back to Work, mark it finished. If all finish, the state is safe.

Let us make it concrete with a single resource type — say 12 identical instances of some resource (think 12 tape drives, or 12 connections in a pool) shared by three processes. The table below shows a snapshot and runs the safety check by hand. The whole trick of the safety check is that Work — the pool of what is free — only grows as processes finish and hand their allocation back, so we look for anyone whose remaining Need fits, run them, and repeat.

Resource A: 12 total instances

Process    Max    Allocation    Need (Max-Alloc)
  P0        10         5              5
  P1         4         2              2
  P2         9         2              7
                     -----
        allocated  =   9   ->  Available = 12 - 9 = 3

Safety check  (Work starts at Available = 3):
  Work=3    P1 needs 2 <= 3   -> run, P1 returns 2   Work = 5
  Work=5    P0 needs 5 <= 5   -> run, P0 returns 5   Work = 10
  Work=10   P2 needs 7 <= 10  -> run, P2 returns 2   Work = 12
  All processes finished.  STATE IS SAFE.
  Safe sequence: <P1, P0, P2>

Notice that P0 and P2 could not run first — with only 3 free, neither’s Need is satisfiable at the start. P1 is the key that unlocks the sequence: it needs only 2, finishes, and returns enough to let P0 go, which in turn frees enough for P2. Because such a sequence exists, the banker is happy: this state is safe. Now watch what avoidance does when a new request threatens to break that.

P2 requests 1 more instance of A.
Tentatively grant it:
  P2 Allocation -> 3,  P2 Need -> 6,  Available -> 2

Safety check  (Work starts at 2):
  Work=2    P1 needs 2 <= 2   -> run, P1 returns 2   Work = 4
  Work=4    P0 needs 5 <= 4 ? NO
            P2 needs 6 <= 4 ? NO
  Nobody else can finish. NO safe sequence exists.
  STATE IS UNSAFE  ->  request DENIED, P2 must wait.

That is the whole method in one gesture. The resource was physically available — there were 3 free and P2 asked for just 1 — yet the banker refused, because granting it would leave the system unable to guarantee that everyone finishes. Avoidance trades some immediate, technically-legal allocations for an absolute promise: from a safe state, following the Banker’s algorithm, the system can never deadlock.