Deadlocks II — Detection & Recovery

Prevention and avoidance both pay a permanent price to guarantee deadlock never occurs. Prevention structurally forbids one of the four conditions — maybe you must grab all your locks at once, or always take them in a fixed global order — and that constrains how every piece of code is allowed to behave. Avoidance is gentler at design time but heavier at run time: before granting any request it runs a safety check (the banker’s algorithm from last chapter) to make sure the system stays in a safe state. Either way, code that would never have deadlocked still pays the bill.

Detection and recovery flips the economics. You grant resources freely, with no safety check and no ordering rules, and accept that a deadlock might occasionally form. Periodically — or when things look stuck — you run a detection algorithm that asks a single question: is there a set of processes all waiting on each other right now? If yes, you invoke recovery to break the cycle. If no, you paid almost nothing. The common case runs at full speed; you only spend effort when a deadlock genuinely exists.

Detection

An algorithm that examines the current allocation and wait state and reports whether a deadlock exists (and which processes are involved).

Recovery

The action taken once a deadlock is found — abort processes or preempt resources — to break the cycle and let the survivors proceed.

The core bet

Deadlocks are rare enough that paying full recovery cost occasionally beats paying a small prevention or avoidance tax on every single request.

When is this the right bet? When resource needs cannot be declared in advance, avoidance is simply off the table — the banker’s algorithm needs each process’s maximum claim, and a general-purpose database or OS has no idea what a future transaction will touch. When deadlocks are rare, the recovery cost is amortised over so many deadlock-free operations that it disappears into the noise. And when the common path is performance-critical, you do not want a safety check on the hot path slowing down the 99.99% of requests that were never in danger.

Last chapter you drew resource-allocation graphs with two kinds of node — processes and resources — and two kinds of edge: an assignment edge from a resource to the process holding it, and a request edge from a process to a resource it wants. For detection we can simplify. When every resource type has exactly one instance, the resources are just middlemen, and we can collapse them out to get a wait-for graph: a graph of processes only, where an edge Pi → Pj means “Pi is waiting for a resource that Pj currently holds.”

The reduction is mechanical. For each pair of edges Pi → R (a request) and R → Pj (an assignment), draw a single edge Pi → Pj and delete the resource node R. You are literally short-circuiting through the resource: Pi wants what Pj is sitting on. Do this for every resource and you are left with a lean process-to-process graph that encodes exactly who is blocked on whom.

Now detection is a classic graph problem. A deadlock exists if and only if the wait-for graph contains a cycle. A cycle P1 → P2 → P3 → P1 means P1 waits on P2, which waits on P3, which waits back on P1 — a closed loop where no one can move because everyone is waiting for the next one around the ring. Finding it is just cycle detection, which any depth-first search can do in time proportional to the number of nodes plus edges.

Edges (Pi -> Pj means "Pi waits for a resource Pj holds"):
  P1 -> P2      P1 holds R1, wants R2 (held by P2)
  P2 -> P3      P2 holds R2, wants R3 (held by P3)
  P3 -> P1      P3 holds R3, wants R1 (held by P1)

DFS from P1:  visit P1 -> P2 -> P3 -> P1  (back-edge!)
  P1 already on the current path  =>  CYCLE FOUND
  Deadlocked set = { P1, P2, P3 }

The genuinely interesting engineering question is not how to detect a cycle but how often to look. Detection is not free — you must freeze or snapshot the wait state and run the search — so there is a real trade-off. Run it on every single resource request and you catch deadlocks the instant they form, but you have quietly reinvented an expensive per-request tax, exactly the thing detection was meant to avoid. Run it rarely — say once a minute — and it is cheap, but processes may sit dead for up to a minute before anyone notices, and more of them may pile into the tangle meanwhile.

• ▸On every request: catches deadlocks immediately, but the detection cost creeps back toward an avoidance-style per-request tax.
• ▸On a fixed timer (every N seconds): cheap and simple, but deadlocked processes waste time being stuck between scans.
• ▸Only when it might matter: run detection when a request has to block, or when CPU utilisation drops suspiciously (a hint that many processes are stuck waiting rather than running) — a common practical compromise.

The wait-for graph works beautifully when each resource is unique — one printer, one specific lock. But many resources come in interchangeable copies: a pool of ten database connections, four identical tape drives, a semaphore initialised to a count of five. With multiple instances, a cycle in the graph no longer guarantees deadlock — a process in the cycle might still be satisfiable by a free copy held by nobody in the loop. We need a counting approach instead of a pure graph one.

The detection algorithm here is a close relative of the banker’s algorithm, with one crucial difference in spirit. The banker’s algorithm was cautious — it worked from each process’s declared maximum future claim to decide whether to grant a request. The detection algorithm is not predicting the future at all; it works from what processes are actually requesting right now, and asks whether the requests already outstanding can possibly all be satisfied in some order.

Available

A vector: how many free instances of each resource type currently exist, held by no one.

Allocation

A matrix: how many instances of each resource type each process currently holds.

Request

A matrix: how many more instances of each type each process is currently waiting for (its outstanding, unsatisfied request).

The idea is a simulated “best case” sweep. Start with Work = Available and pretend no one has finished. Look for any process whose current Request can be met from Work — that process could, if we gave it what it asks, run to completion. Optimistically assume it does: add its Allocation back into Work (it releases everything it held) and mark it finished. Repeat, and each freed process may release enough to unblock the next. If you can eventually finish every process this way, there is no deadlock. Whatever processes remain unfinishable — none of them can have their request met even after all the others release — are precisely the deadlocked set.

The intuition is worth holding onto: a deadlock is a group of processes whose requests can never be satisfied no matter what order the rest of the system runs in. The sweep is just a systematic way of checking “can everyone finish in some order?” — and the leftovers are the ones stuck in a knot that no amount of waiting will loosen.

Detection tells you a deadlock exists and who is in it. Recovery is the unpleasant part: the cycle cannot break itself, so something has to give up ground. There is no painless option — every recovery strategy destroys work someone had already done. The whole art is losing the least.

The bluntest tool is process termination. The nuclear version aborts every process in the deadlocked set at once: guaranteed to break the cycle, instantly, but it also throws away all the partial work of processes that might have needed only one more grant to finish. The surgical version aborts one process at a time — kill a single victim, hand its resources to the others, then re-run detection to see if the deadlock is already gone. It usually destroys far less work, but each abort means another detection pass, so it is slower and more complex.

The subtler tool is resource preemption: instead of killing a process, take a resource away from it and give it to someone else in the cycle. That only works if the resource’s state can be safely saved and restored — you roll the victim back to a checkpoint, a previously saved consistent state, let the others proceed, and later re-run the victim from that checkpoint as if the interruption never happened. This is exactly how databases recover: a transaction’s changes are undone (rolled back) and it can be retried from the start. Preemption is impossible for resources with no clean rollback — you cannot half-un-print a page or un-send a network packet.

Whichever tool you use, you must choose a victim, and cost is the deciding factor. You want to abort or preempt whoever hurts least: the process that has done the least work so far, holds the fewest resources, is lowest priority, or can be rolled back most cheaply. A transaction that has run for two milliseconds is a far better victim than one that has been churning for ten minutes.

Process termination

Break the cycle by aborting processes — all of them at once (fast, wasteful) or one at a time with re-detection (slow, thrifty).

Resource preemption

Take a resource from a victim and reassign it, rolling the victim back to a saved checkpoint; only possible when state can be safely restored.

Victim selection

Choosing who pays, by cost: least work done, fewest resources held, lowest priority, cheapest rollback.

Rollback count

A per-process tally of prior rollbacks folded into victim cost so the same process is not starved by being chosen repeatedly.

Deadlock is the famous failure mode, but two relatives cause just as much production grief and are easier to miss. Both share deadlock’s outcome — a process that never makes progress — but neither is a deadlock, and your deadlock detector will not catch them, because in a deadlock every involved process is blocked, sitting still, and these two are not.

Livelock is the sneaky one: the processes are not stuck, they are extremely busy — they just never accomplish anything. The classic picture is two people meeting in a narrow corridor. Each politely steps aside to let the other pass; they step the same way, block again, both apologise and step back the other way, block again, and repeat forever. Nobody is frozen — there is frantic activity — but there is zero net progress. In code this shows up when two threads detect a conflict, both back off, both retry, and their retries stay perfectly synchronised so they keep colliding.

The cure for livelock is to break the symmetry that keeps the participants in lockstep. Randomised backoff is the standard trick: instead of retrying after a fixed delay, each party waits a random amount of time, so the odds of colliding again shrink with every round. This is exactly the exponential-backoff-with-jitter you have seen in network protocols and API client libraries — the same disease, the same medicine.

Starvation is different again: a process is denied a resource indefinitely not because of a cycle but because the system’s policy keeps favouring others. A low-priority thread on a busy machine may never get the CPU if higher-priority threads keep arriving. A writer may wait forever behind an endless stream of readers. Nothing is deadlocked — the resource is being granted constantly, just never to this one unlucky process. The fix is fairness: aging (gradually boosting the priority of anyone who has waited too long) or FIFO ordering so that waiting eventually guarantees a turn.

Deadlock

Processes are blocked, each waiting on a resource another holds; no one is running. A cycle, detectable in the wait-for graph.

Livelock

Processes are running and reacting to each other but make no progress — e.g. mutual retry/backoff in lockstep. No process is blocked.

Starvation

One process is perpetually passed over by the scheduling or granting policy while others proceed. Not a cycle, but a fairness failure.

Here is where all of this stops being theory. The single most common place a working engineer meets deadlock is a database. Relational databases lock rows to keep transactions isolated, and the moment two transactions grab the same rows in opposite orders, you have the textbook cycle: transaction T1 locks row A then reaches for row B; transaction T2 has already locked row B and now reaches for row A. Each waits on a lock the other holds — a deadlock, exactly the wait-for cycle from earlier in this chapter, playing out inside your production database.

The database handles it with precisely the strategy of this chapter: detect and recover. A background deadlock detector runs the wait-for-graph check, finds the cycle, picks a victim transaction (usually the one cheaper to roll back), aborts it, rolls back its changes, and lets the other transaction proceed. The victim’s application gets an error. This is why detection-and-recovery is worth learning properly — it is the algorithm running under your ORM every single day.

ERROR:  deadlock detected
DETAIL:  Process 18244 waits for ShareLock on transaction 9931;
         blocked by process 18251.
         Process 18251 waits for ShareLock on transaction 9930;
         blocked by process 18244.
HINT:  See server log for query details.
CONTEXT:  while updating tuple (0,14) in relation "accounts"

-- Process 18244 waits on 18251, and 18251 waits on 18244:
-- a two-node cycle. Postgres aborts one of them so the other
-- can commit. Your transaction is rolled back with SQLSTATE 40P01.

Because the database can kill your transaction through no fault of its logic, robust application code treats a deadlock error as a transient, retryable failure rather than a bug. You catch the specific deadlock error code (SQLSTATE 40P01 in Postgres, error 1213 in MySQL/InnoDB), wait a short randomised moment — the jitter that also cures livelock — and simply run the whole transaction again. On retry the contending transaction has usually finished, the rows are free, and the second attempt sails through.

• ▸Catch the deadlock error specifically — do not lump it in with permanent failures like a constraint violation.
• ▸Retry the entire transaction from the beginning; a rolled-back transaction has no partial state to salvage.
• ▸Add randomised backoff between attempts so two retrying transactions do not immediately re-collide (livelock avoidance).
• ▸Cap the retries, and reduce deadlocks at the source by acquiring locks in a consistent global order — deadlock prevention, applied at the application layer.

One frontier is genuinely harder: distributed deadlock, where the waiting processes span different machines. No single node can see the whole wait-for graph, so building it means shipping and merging state across the network — expensive and always slightly stale. Many distributed systems therefore give up on exact detection and fall back to a crude but robust proxy: timeouts. If a transaction waits longer than some threshold, assume it is deadlocked and abort it. It is imperfect — it sometimes kills a transaction that was merely slow, not deadlocked — but it needs no global graph and it always eventually breaks a real deadlock.

That closes Part C. We have gone from a single shared variable and a race condition all the way to database transactions deadlocking and recovering under load — the full concurrency story. Next we turn to the other great illusion the OS maintains: memory. Part D opens the world of virtual memory, address spaces, and paging — how every process is fooled into thinking it owns a vast, private, contiguous block of RAM. And later, in the database capstone, these two threads braid together: the locking you just studied and the memory and durability machinery ahead are exactly what a database is built from.