6. Deadlocks
Chapter 5 solved the race condition by making threads wait for each other, and in doing so created a new failure mode: a set of threads can each hold something the others need, so every one of them waits forever. This chapter defines that state precisely — the resource model, the four conditions that must hold simultaneously, and the graph notation that makes it visible — then works through the three strategies available: forbid it structurally, avoid it dynamically with advance knowledge, or allow it and recover afterwards. Deadlock deserves its own chapter because it is the failure that produces no exception, no log entry, and no CPU usage: the system simply stops responding while looking perfectly healthy.
<a id="61-deadlock-characterization"></a>
6.1 Deadlock Characterization
This section builds the vocabulary: what counts as a resource, the four conditions that together create deadlock, the graph notation that turns the question into cycle detection, and how deadlock differs from the two failures it is routinely confused with.
System Model of Resources
Theory
Before we can prove anything about deadlock, we need a model of the system that is simple enough to reason about but faithful enough to be useful. The standard model is deliberately austere.
A system consists of a finite number of resource types R1, R2, ..., Rm. Each type Ri has Wi identical instances. A resource is anything a process must obtain exclusively before it can proceed: CPU cores, memory frames, mutexes, semaphores, open-file slots, database rows, printers, network ports, IPC channels.
The word "identical" carries the weight of the whole model. Two instances belong to the same type only if a process that asks for one is equally satisfied by either. If a program requests "printer 3 specifically, because it holds the letterhead paper", then printer 3 is its own resource type with one instance. Getting this classification wrong is the most common modelling error: it makes the analysis say a system is safe when it is not.
Every process uses a resource through the same three-phase protocol:
- Request. The process asks the OS (or a library) for the resource. If it is unavailable, the process blocks until it is. This is the only phase in which a process can be delayed.
- Use. The process operates on the resource. The OS is not involved.
- Release. The process returns the resource so others may have it.
Two orthogonal classifications of resources matter for the rest of the chapter:
| Axis | Categories | Examples | Relevance to deadlock |
|---|---|---|---|
| Lifetime | Reusable — a fixed number of instances, returned after use | mutexes, memory frames, printers, disk blocks | The classic model; count is conserved |
| Consumable — created by a producer, destroyed by a consumer; no fixed count | messages, signals, interrupts, buffer entries | Deadlock still possible (mutual receive) but no fixed inventory to reason about | |
| Revocability | Preemptable — can be taken away and restored later without harm | CPU (save registers), physical memory (swap the page out) | Never a deadlock cause: the OS can always break the wait |
| Non-preemptable — taking it away corrupts the work in progress | mutex, printer mid-page, tape drive, an uncommitted DB row | The dangerous kind; the entire chapter is about these |
With this model, deadlock has an exact definition:
A set of processes is deadlocked when every process in the set is waiting for an event that can only be caused by another process in the same set.
The self-referential structure is the essence of it. This is not "slow" and not "unlucky"; no amount of waiting helps, because everyone who could produce the awaited event is themselves blocked. The set is closed, and no outside activity can open it.
Analogy: a single-lane bridge that is too narrow for cars to pass. If a car enters from each end and both refuse to reverse, they are deadlocked. Note the ingredients already: the bridge cannot be shared (mutual exclusion), each car occupies the half it entered while wanting the other half (hold and wait), no one can be lifted off (no preemption), and each waits for the other (circular wait).
Example
A SYSTEM STATE IN THE STANDARD MODEL
Resource types Instances
----------------------------- ------------------------------
R1 = mutex "accounts_lock" W1 = 1 [#]
R2 = printers W2 = 2 [#][ ]
R3 = tape drives W3 = 3 [#][#][ ]
R4 = DB connections (pool) W4 = 5 [#][#][#][ ][ ]
[#] = allocated [ ] = available
Available vector = (0, 1, 1, 2)
THE THREE-PHASE PROTOCOL, AND WHERE TIME IS SPENT
request ---> [ may BLOCK here, possibly forever ]
|
v
use ---> [ bounded by the process's own work ]
|
v
release ---> [ must execute on EVERY exit path,
including exceptions and early returns ]
Deadlock lives entirely in phase 1. A process that never reaches
phase 3 (leaked lock) causes the same symptom by a different route.
/* The three-phase protocol, made explicit. Every resource obeys it,
whether the "OS" involved is the kernel, a library, or a database. */
sem_t tape_drives; /* R3: 3 identical instances */
pthread_mutex_t accounts_lock; /* R1: 1 instance (a binary case) */
void archive_accounts(void) {
sem_wait(&tape_drives); /* REQUEST: blocks while 0 free */
pthread_mutex_lock(&accounts_lock); /* REQUEST: second resource type */
write_archive(); /* USE: OS uninvolved */
pthread_mutex_unlock(&accounts_lock);/* RELEASE, reverse order */
sem_post(&tape_drives); /* RELEASE: increments the count */
}
# A minimal simulation of the model: types, instances, and the
# available vector that every algorithm in this chapter operates on.
class ResourceSystem:
def __init__(self, total):
self.total = list(total) # W vector: instances per type
self.available = list(total) # currently unallocated
self.allocation = {} # process -> vector held
def request(self, pid, req):
held = self.allocation.setdefault(pid, [0] * len(self.total))
# A request is granted ONLY if every component fits. Partial
# grants are what turn a request into "hold and wait".
if all(r <= a for r, a in zip(req, self.available)):
self.available = [a - r for a, r in zip(self.available, req)]
self.allocation[pid] = [h + r for h, r in zip(held, req)]
return True
return False # caller BLOCKS -- deadlock risk
def release(self, pid, rel):
held = self.allocation[pid]
self.allocation[pid] = [h - r for h, r in zip(held, rel)]
self.available = [a + r for a, r in zip(self.available, rel)]
sys_ = ResourceSystem(total=[1, 2, 3, 5])
print(sys_.request("P1", [1, 1, 1, 3])) # True -> available (0,1,2,2)
print(sys_.request("P2", [1, 0, 0, 0])) # False -> P2 blocks on R1
Key takeaways
- The model is resource types with identical instances; two things are the same type only if a requester is indifferent between them.
- Every use follows request, use, release, and only the request phase can block.
- Non-preemptable resources are the ones that cause deadlock; preemptable ones can always be reclaimed.
- Deadlock: every process in a set waits for an event only another member of that set can cause — a closed, self-sustaining cycle of waiting.
🧪 Practice
- Classify each as preemptable or non-preemptable, and justify: CPU registers, a
pthread_mutex_t, a page of physical memory, a partially written CD-R, a TCP port, an uncommitted database row.- A print server has three identical printers, but one has a colour cartridge. Model this as resource types twice: once treating all three as one type, once correctly. Give a request sequence where the first model wrongly predicts success.
- Interview-style: "A thread returns early from a function while holding a lock. Is that a deadlock?" Hint: compare the definition (a waiting set whose members can only be freed by each other) against what is actually happening to the other threads, and ask whether any process in your candidate set is itself waiting.
Necessary Conditions
Theory
In 1971 E. G. Coffman and colleagues identified four conditions that must all hold simultaneously for deadlock to be possible. This is the single most useful result in the chapter, because it converts a vague worry into a checklist — and, more importantly, into a design tool: break any one condition and deadlock becomes structurally impossible.
1. Mutual exclusion. At least one resource is held in a non-shareable mode. If a resource can be used by any number of processes at once, no one ever waits for it, so it can never appear in a waiting cycle. Read-only files satisfy this; a mutex does not.
2. Hold and wait. A process holds at least one resource while requesting another. If processes acquired everything they need in one atomic step, or held nothing while requesting, a blocked process would be blocking with empty hands and could not contribute to a cycle.
3. No preemption. Resources cannot be forcibly taken from a process; they are released only voluntarily, by the holder, after it finishes. If the system could revoke a resource, it could always break a cycle by choice.
4. Circular wait. There exists a set of waiting processes {P0, P1, ..., Pn} such that P0 waits for a resource held by P1, P1 for one held by P2, ..., and Pn for one held by P0.
The logical status of these is worth being precise about, because exams and interviews probe exactly here:
- The four conditions are necessary: no deadlock without all four.
- They are not individually sufficient: circular wait alone does not imply deadlock when resource types have multiple instances (see the next topic).
- Circular wait is not independent of the others — it is closer to a consequence of the first three under contention. It is listed separately because it is the condition that is easiest to attack in real code.
Analogy: a four-way intersection with no signals and a rule that you never reverse. Each car occupies its quadrant (mutual exclusion), holds it while waiting for the next (hold and wait), cannot be lifted out (no preemption), and each waits on the car to its left (circular wait). Remove any one — make quadrants shareable, require cars to claim all four before entering, allow a tow truck, or install a "yield to the right" rule that breaks the symmetry — and the gridlock cannot form.
Example
ALL FOUR CONDITIONS IN ONE TRACE
Thread A Thread B
------------------------------ ------------------------------
lock(mutex_X) ok .
. lock(mutex_Y) ok
lock(mutex_Y) BLOCKS .
. lock(mutex_X) BLOCKS
. .
[ waits forever ] [ waits forever ]
Condition check:
1. mutual exclusion YES mutex_X and mutex_Y are exclusive
2. hold and wait YES A holds X while requesting Y
3. no preemption YES nothing can take X away from A
4. circular wait YES A -> Y(held by B) -> X(held by A)
Neither thread consumes CPU. `top` shows 0%. Nothing is logged.
This is why deadlock is diagnosed by stack dumps, not by monitoring.
| Condition | Holds when... | Attack (Section 6.2) | Practical cost of the attack |
|---|---|---|---|
| Mutual exclusion | Resource is exclusive | Make it shareable: immutable data, read-only files, spooling, lock-free structures | Often impossible; some resources are exclusive by nature |
| Hold and wait | Acquire while holding | Take all resources atomically, or release everything before requesting more | Low utilisation; long waits; starvation |
| No preemption | Only the holder releases | Allow revocation: trylock + release-all, or transaction rollback | Needs saveable state; wasted work |
| Circular wait | Cyclic waiting chain exists | Impose a global order on resource types; acquire only in increasing order | Cheap and effective; requires discipline across the whole codebase |
public class FourConditions {
private final Object X = new Object();
private final Object Y = new Object();
// Deadlocks under contention: satisfies all four conditions.
public void threadA() {
synchronized (X) { // 1: exclusive 3: not preemptable
work();
synchronized (Y) { // 2: holds X while requesting Y
work(); // 4: with threadB, closes the cycle
}
}
}
public void threadB() {
synchronized (Y) { // opposite order -- the whole bug
work();
synchronized (X) {
work();
}
}
}
// Cannot deadlock: circular wait is broken by a consistent global order
// (X before Y, always, everywhere). The other three still hold.
public void safeA() { synchronized (X) { synchronized (Y) { work(); } } }
public void safeB() { synchronized (X) { synchronized (Y) { work(); } } }
private void work() { }
}
Key takeaways
- Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait, all at once.
- The conditions are necessary, not individually sufficient; with multi-instance resources even circular wait is not sufficient.
- Every prevention technique in existence is an attack on exactly one of the four.
- In practice, breaking circular wait via a global lock ordering is the cheapest and most widely used attack.
🧪 Practice
- For each scenario, name the condition that is absent: (a) a read-only configuration file read by 50 threads; (b) a thread that calls
trylockand releases all its locks on failure; (c) a program in which every thread acquires locks in ascending address order.- Write a three-thread, three-mutex program that deadlocks only when the interleaving is exactly right, then fix it by ordering alone. Explain why the fix does not reduce concurrency.
- Interview-style: "Which of the four conditions is the easiest to eliminate in a large existing codebase, and why?" Hint: think about which attack can be applied file-by-file without changing the program's resource requirements or its utilisation.
Resource Allocation Graphs
Theory
The four conditions are a checklist, but checking "does a circular wait exist?" by reading code does not scale. The resource allocation graph (RAG) turns the question into a graph problem the machine can answer.
The graph is directed and bipartite, with two kinds of vertex:
- A process vertex, drawn as a circle:
P1, P2, ... - A resource type vertex, drawn as a rectangle containing one dot per instance:
R1, R2, ...
and two kinds of edge:
- A request edge
Pi -> Rj: processPihas asked for an instance ofRjand is blocked waiting. - An assignment edge
Rj -> Pi: one instance ofRjis currently held byPi. The edge starts at a specific dot inside the rectangle.
When a blocked request is finally granted, its request edge is simply reversed into an assignment edge; when the resource is released, the edge is deleted. The graph is thus a live picture of the system's waiting structure.
The central theorem:
- If the graph contains no cycle, then no process is deadlocked. This holds unconditionally.
- If the graph contains a cycle:
- and every resource type has exactly one instance, the processes on the cycle are deadlocked. Cycle is necessary and sufficient.
- and some type has several instances, deadlock may exist. The cycle is necessary but not sufficient, because a process outside the cycle may hold the instance that eventually satisfies someone on it.
That second case is the subtlety worth internalising. A cycle means "everyone on this ring is waiting on the ring", but with several instances of a type, the ring can be broken from outside: some process not on the cycle releases an instance, one waiter is satisfied, and the cycle dissolves. With single instances there is no outside supply, so the ring is fatal.
Analogy: a cycle of people each waiting for a book. If the library owns one copy of each title, the wait is hopeless. If it owns three copies of one title, a fourth reader who is not part of the ring may return their copy and rescue everyone.
Example
CASE 1 -- CYCLE WITH SINGLE INSTANCES: DEADLOCK
+----------+ +----------+
| R1 | assignment | R2 |
| [*]----+--------------> (P1) | [*] |
+----------+ | +----------+
^ | request |
| request v | assignment
| +----+ |
+---------------------| |<---------+
(P2)
Edges: R1 -> P1 (P1 holds R1)
P1 -> R2 (P1 wants R2)
R2 -> P2 (P2 holds R2)
P2 -> R1 (P2 wants R1)
Cycle: P1 -> R2 -> P2 -> R1 -> P1
Single instance per type => P1 and P2 ARE DEADLOCKED.
CASE 2 -- CYCLE WITH MULTIPLE INSTANCES: NO DEADLOCK
R1 has TWO instances: R1 = [*][*]
R1.a -> P1 (P1 holds one instance of R1)
R1.b -> P3 (P3 holds the other)
P1 -> R2 (P1 waits for R2)
R2 -> P2 (P2 holds R2)
P2 -> R1 (P2 waits for R1)
Cycle: P1 -> R2 -> P2 -> R1 -> P1 <- a cycle EXISTS
But P3 is NOT on the cycle. When P3 releases its R1 instance,
P2 is satisfied, finishes, releases R2, and P1 proceeds.
CYCLE PRESENT, DEADLOCK ABSENT. This is why cycle detection is
only sufficient in the single-instance case.
# Building a resource allocation graph and testing it for a cycle.
# For single-instance resource types this IS the deadlock detector.
from collections import defaultdict
class RAG:
def __init__(self):
self.edges = defaultdict(set) # node -> set of successors
def request(self, p, r): # Pi -> Rj (blocked request)
self.edges[p].add(r)
def assign(self, r, p): # Rj -> Pi (held)
self.edges[r].add(p)
def grant(self, p, r): # blocked request becomes a holding
self.edges[p].discard(r) # reverse the edge in place
self.edges[r].add(p)
def find_cycle(self):
WHITE, GREY, BLACK = 0, 1, 2 # classic DFS colouring
colour = defaultdict(int)
stack = []
def dfs(u):
colour[u] = GREY # GREY = on the current DFS path
stack.append(u)
for v in self.edges[u]:
if colour[v] == GREY: # back edge to the path -> cycle
return stack[stack.index(v):] + [v]
if colour[v] == WHITE:
found = dfs(v)
if found:
return found
colour[u] = BLACK # fully explored, cannot start a cycle
stack.pop()
return None
for node in list(self.edges):
if colour[node] == WHITE:
cycle = dfs(node)
if cycle:
return cycle
return None
g = RAG()
g.assign("R1", "P1") # P1 holds R1
g.request("P1", "R2") # P1 waits for R2
g.assign("R2", "P2") # P2 holds R2
g.request("P2", "R1") # P2 waits for R1
print(g.find_cycle()) # ['R1', 'P1', 'R2', 'P2', 'R1'] -> deadlocked
Key takeaways
- A RAG has process and resource vertices, request edges
P -> R, and assignment edgesR -> P. - No cycle always means no deadlock; this direction needs no assumptions.
- With one instance per type, a cycle means deadlock; with several instances it only means deadlock is possible.
- Detection therefore reduces to depth-first cycle search,
O(V + E), on the single-instance graph.
🧪 Practice
- Draw the RAG for:
P1holdsR1,P2holdsR2andR3,P1requestsR2,P3requestsR1. Is there a cycle? Is there a deadlock?- Extend the
RAGclass with arelease(r, p)method, then produce a trace where a cycle appears and later dissolves without any process being aborted. What must be true about instance counts?- Interview-style: "Your monitoring detects a cycle in the resource graph of a system whose semaphores have counts greater than one. Do you page the on-call engineer?" Hint: state what a cycle proves and what it does not, and name the extra check you would run before escalating.
Deadlock vs Starvation vs Livelock
Theory
Three distinct failures are routinely reported as "the system is hung". They have different causes, different symptoms, and completely different fixes, so distinguishing them is the first diagnostic step.
Deadlock is a state: a set of processes is permanently blocked, each waiting for the others. It is stable — once entered, no execution can leave it without outside intervention. The processes consume no CPU. Progress is zero and will remain zero.
Starvation (indefinite postponement) is a scheduling outcome: a process is runnable and would make progress if selected, but the selection policy keeps choosing others. Nothing is structurally impossible; the process is simply always second in line. A low-priority thread under strict priority scheduling, or a writer under a reader-preferring readers-writers lock, starves. The system as a whole is making progress — just not for the victim. The fix is a policy fix: ageing, FIFO fairness, ticket locks (Chapter 4 and Chapter 5).
Livelock is futile activity: processes are running, changing state, and consuming CPU, but no one advances. The classic form is a trylock-and-retry loop where every contender releases and retries in perfect synchrony, colliding again each round. Livelock also arises in receive-livelock, where a server spends all its time in interrupt handlers accepting packets it never has time to process.
The corridor analogy captures all three. Two people meet head-on in a narrow corridor. If both stop and refuse to move, that is deadlock. If both keep stepping to the same side, over and over, that is livelock — motion without progress. If one of them stands still while a stream of higher-priority people flows past for hours, that is starvation.
Example
| Deadlock | Livelock | Starvation | |
|---|---|---|---|
| Process state | Blocked | Running | Runnable, not scheduled |
| CPU usage | Zero | High (often 100%) | Zero for the victim |
| Progress | None, permanently | None, though state changes | None for the victim; system progresses |
| Recovery on its own | Never | Possible, by luck | Possible, if load drops |
| Root cause | Circular wait on resources | Symmetric retry with no tie-break | Unfair selection policy |
| Typical fix | Lock ordering, detection + abort | Randomised backoff, priority tie-break | Ageing, FIFO queueing |
| Diagnosis tool | Thread dump, jstack, pstack | CPU profiler, retry counters | Latency percentiles, wait-time histograms |
THE CORRIDOR
DEADLOCK LIVELOCK STARVATION
--------- -------- ----------
A --><-- B A --> <-- B A --> ..........
(both frozen) A steps left ..........<-- crowd
B steps left ..........<-- crowd
CPU: 0% A steps right (A still waiting)
Forever B steps right
... forever, at 100% CPU CPU: 0% for A
import threading, time, random
lock_a, lock_b = threading.Lock(), threading.Lock()
def livelock_worker(first, second, name):
"""Polite retry with NO randomness: both threads back off in lockstep,
collide again, and repeat. Busy, and permanently unproductive."""
while True:
first.acquire()
if second.acquire(blocking=False): # try the second lock
print(f"{name} got both")
second.release(); first.release()
return
first.release() # be polite: give up and retry
# time.sleep(random.uniform(0, 0.01)) # <- the missing tie-break
def fixed_worker(first, second, name):
"""Randomised backoff breaks the symmetry: the two threads' retry
instants diverge, so one wins on some round. Same code otherwise."""
while True:
first.acquire()
if second.acquire(blocking=False):
second.release(); first.release()
return
first.release()
time.sleep(random.uniform(0, 0.01)) # asymmetry, cheaply bought
Key takeaways
- Deadlock is a permanent blocked state; livelock is permanent futile motion; starvation is unfair selection.
- CPU usage separates them at a glance: deadlock 0%, livelock high, starvation 0% for one victim while the system runs.
- Deadlock never resolves itself; livelock and starvation can, given luck or a load change.
- The fixes are unrelated: ordering or detection for deadlock, randomised backoff for livelock, ageing or FIFO for starvation.
🧪 Practice
- For each observation, name the failure: (a) all 200 worker threads sit in
park()and CPU is idle; (b) CPU pinned at 100%, a retry counter climbing by millions per second, throughput zero; (c) throughput normal, but one client's p99 latency is 40 seconds.- Modify
livelock_workerso it deadlocks instead of livelocking. Which single line changes, and which Coffman condition does that restore?- Interview-style: "Ethernet's exponential backoff is often cited as a livelock fix. What exactly does the randomness buy you?" Hint: think about what two colliding senders have in common at the moment of collision, and what must differ for one of them to win.
<a id="62-prevention-and-avoidance"></a>
6.2 Prevention and Avoidance
The two proactive strategies differ in what they know. Prevention knows nothing about the future and guarantees safety structurally, by making one Coffman condition impossible. Avoidance requires processes to declare their maximum needs in advance and uses that knowledge to refuse individual requests that could lead to trouble.
Breaking the Necessary Conditions
Theory
Deadlock prevention is the direct application of the Coffman result: if all four conditions are necessary, then denying any one of them makes deadlock impossible — not unlikely, impossible. The engineering question is which condition is cheapest to deny, because each attack has a price.
Attacking mutual exclusion. Make resources shareable so no one ever waits. This works only where the resource permits it: read-only data, immutable objects, spooled printers (processes write to a spool file, and only the daemon touches the device), and lock-free data structures built from compare-and-swap (Chapter 5). It fails for the resources that matter most — a mutex is exclusive by definition. Generally the least applicable attack, but where it applies it is free.
Attacking hold and wait. Two protocols exist:
- All-or-nothing acquisition: a process requests every resource it will need in a single atomic operation, before it starts. It never blocks while holding anything.
- Release before request: a process holding resources must release them all before it may request anything new.
Both work, and both are expensive. A job that needs a tape drive for its last two seconds must hold it for its entire hour-long run (poor utilisation), and a process that repeatedly loses the atomic acquisition race can starve.
Attacking no preemption. Allow resources to be taken back. The usual protocol: if a process holding resources requests one that is unavailable, it releases everything it holds, and restarts once it can obtain the whole set again. In code this appears as trylock with release-and-retry; in databases it appears as transaction rollback. It requires state that can be saved and restored, which is exactly why it works for CPU registers and database transactions but not for a half-printed page.
Attacking circular wait. Define a total order F over resource types, and require every process to acquire in strictly increasing order of F. The proof is short and worth remembering: if a cycle existed, following it around would require F(R1) < F(R2) < ... < F(Rn) < F(R1), so F(R1) < F(R1), a contradiction. This is the attack used in real systems — the Linux kernel documents lock ordering per subsystem, and lockdep verifies it at runtime — because it costs nothing at run time and does not reduce concurrency. Its price is discipline: every acquisition site in the codebase must obey the same order, including inside callbacks and library code.
Analogy for ordering: a one-way system in a city centre. Cars are not restricted in where they go, and no intersection is closed; they simply cannot traverse a loop in the wrong direction, so gridlock cycles cannot form.
Example
THE FOUR ATTACKS, AND WHAT EACH COSTS
Condition denied Mechanism Price
---------------- --------------------------- -----------------------
mutual exclusion immutable data, spooling, rarely applicable
lock-free structures
hold and wait acquire ALL up front, or utilisation collapses;
release-all-before-request starvation possible
no preemption trylock + release-all, wasted work; needs
transaction rollback restorable state
circular wait global order over lock discipline across the
types; acquire ascending whole codebase <-- USE THIS
WHY ORDERING WORKS (proof in one line)
Suppose P1 -> P2 -> ... -> Pn -> P1 is a wait cycle.
Each edge means: holder of R_i is requesting R_(i+1), so F(R_i) < F(R_(i+1)).
Chaining around the cycle: F(R_1) < F(R_1). Contradiction.
/* ATTACK 4: circular wait, via a total order on lock ADDRESSES.
Works even when the set of locks is dynamic, as with per-object locks. */
void lock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
if (a == b) { /* same object: lock once */
pthread_mutex_lock(a);
return;
}
/* The order is arbitrary but GLOBAL and STABLE -- that is all it needs. */
pthread_mutex_t *first = (a < b) ? a : b;
pthread_mutex_t *second = (a < b) ? b : a;
pthread_mutex_lock(first);
pthread_mutex_lock(second);
}
/* ATTACK 3: no preemption, via trylock and full release.
Note the randomised backoff: without it this livelocks (Section 6.1). */
int lock_two_backoff(pthread_mutex_t *a, pthread_mutex_t *b) {
for (int attempt = 0; attempt < MAX_RETRY; attempt++) {
pthread_mutex_lock(a);
if (pthread_mutex_trylock(b) == 0)
return 0; /* got both */
pthread_mutex_unlock(a); /* hold NOTHING while retrying */
usleep(rand() % (100 << attempt)); /* exponential + random */
}
return -1; /* caller must handle failure */
}
import threading
# ATTACK 2: hold and wait, via atomic all-or-nothing acquisition.
# The process is never blocked while holding anything.
class ResourceSet:
def __init__(self, locks):
self.locks = sorted(locks, key=id) # ordering also applied, belt and braces
self.gate = threading.Lock() # serialises the acquisition attempt
def acquire_all(self):
with self.gate: # only one acquirer at a time
taken = []
for lk in self.locks:
if not lk.acquire(blocking=False):
for t in taken: # all-or-nothing: undo everything
t.release()
return False
taken.append(lk)
return True
def release_all(self):
for lk in reversed(self.locks):
lk.release()
Key takeaways
- Prevention denies one Coffman condition by construction, making deadlock impossible rather than improbable.
- Denying mutual exclusion is usually infeasible; denying hold and wait wrecks utilisation; denying preemption needs restorable state.
- A global acquisition order is the practical attack: zero run-time cost, no loss of concurrency, enforced by convention and tools like
lockdep. trylockplus release-and-retry must include randomised backoff, or deadlock is merely traded for livelock.
🧪 Practice
- A bank transfer locks two accounts. Implement the ordering attack using account IDs, and explain what goes wrong if two accounts can share an ID.
- Show why "acquire all resources up front" can starve a process that needs many resources, while one needing few never starves. Which scheduling idea from Chapter 4 fixes this?
- Interview-style: "You added
trylockwith release-and-retry and now the service burns 100% CPU without completing requests. What happened?" Hint: consider what two symmetric threads do at exactly the same instant after each releases, and what is missing between the release and the next attempt.
Safe and Unsafe States
Theory
Prevention is blunt: it constrains every program all the time, whether or not any risk exists. Avoidance is the alternative — grant requests one at a time, but only when granting cannot possibly lead to deadlock. To do that, the system needs one extra piece of information that prevention does not require: each process must declare, in advance, the maximum number of instances of each resource type it will ever need.
With that declaration, define:
A state is safe if there exists an ordering of all processes
<P1, P2, ..., Pn>— a safe sequence — such that for eachPi, the resourcesPimay still request can be satisfied by the currently available resources plus everything held by allPjwithj < i.
Read that operationally: the system can name at least one order in which it could run every process to completion, one after another, if it had to. P1 can finish with what is free right now. When it finishes it returns everything it held, so P2 can finish, and so on. Existence of that sequence is the guarantee.
The three-way relationship is the crux:
- Every safe state is deadlock-free. The safe sequence is an explicit escape plan.
- An unsafe state is not necessarily deadlocked, and might never deadlock — processes might simply not make their worst-case requests.
- But from an unsafe state, the system can no longer guarantee anything: some sequence of legal requests leads to deadlock, and the OS has lost the ability to prevent it.
Avoidance therefore keeps the system in safe states permanently. The cost is conservatism: it will refuse requests that would in fact have been fine, so utilisation is lower than it could be. This is a deliberate trade of throughput for a guarantee.
Analogy: a bank with 12 million in cash and three customers whose approved credit limits total 22 million. The bank is safe as long as, at every moment, it can name an order in which it could fully fund each customer in turn from cash on hand plus repayments from those funded earlier. It is not lending recklessly by exceeding total cash; it is only refusing the specific loan that would leave it unable to name such an order. Hence the name of the algorithm in the last topic.
Example
THE CLASSIC 12-TAPE-DRIVE EXAMPLE
Total drives: 12
Process Max need Holds now Still may request
------- -------- --------- -----------------
P0 10 5 5
P1 4 2 2
P2 9 2 7
Allocated = 9, Available = 3
IS THIS SAFE? Try to build a safe sequence:
P1 may request 2 more; 3 available -> P1 can finish.
On finishing, P1 returns all 4 it holds -> available = 3 + 4 = 7
P0 may request 5 more; 7 available -> P0 can finish.
P0 returns all 10 it holds -> available = 7 - 5 + 10 = 12
P2 may request 7 more; 12 available -> P2 can finish
SAFE SEQUENCE: <P1, P0, P2> => STATE IS SAFE
NOW: P2 REQUESTS ONE MORE DRIVE. Available would drop to 2, P2 holds 3.
Process Max Holds May request
P0 10 5 5
P1 4 2 2
P2 9 3 6
Available = 2
P1 may request 2; 2 available -> P1 finishes, returns 4 -> available = 4
P0 needs 5 > 4 -> cannot guarantee
P2 needs 6 > 4 -> cannot guarantee
NO SAFE SEQUENCE EXISTS => STATE IS UNSAFE => REQUEST DENIED
Note: the unsafe state is NOT deadlocked. If P0 and P2 happen never to
ask for their maximum, everything completes. Avoidance refuses anyway,
because it can no longer PROVE that it will.
THE THREE REGIONS
+-------------------------------------------------------+
| ALL STATES |
| +-----------------------------------------------+ |
| | UNSAFE (no guarantee; deadlock reachable) | |
| | +---------------------------------+ | |
| | | DEADLOCK (already stuck) | | |
| | +---------------------------------+ | |
| +-----------------------------------------------+ |
| +-----------------------------------------------+ |
| | SAFE <- avoidance keeps the system in here | |
| +-----------------------------------------------+ |
+-------------------------------------------------------+
safe => no deadlock unsafe => deadlock POSSIBLE, not certain
def is_safe(available, allocation, max_need):
"""Return (safe?, safe_sequence). This is the core of avoidance:
can we name an order in which every process could finish?"""
n, m = len(allocation), len(available)
need = [[max_need[i][j] - allocation[i][j] for j in range(m)]
for i in range(n)]
work = list(available) # resources we could hand out
finish = [False] * n
sequence = []
progress = True
while progress:
progress = False
for i in range(n):
# A process qualifies if its REMAINING need fits in `work`.
if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
# Assume it runs to completion and returns everything.
work = [work[j] + allocation[i][j] for j in range(m)]
finish[i] = True
sequence.append(i)
progress = True # restart the scan: more may now qualify
return all(finish), sequence
# The 12-drive example, one resource type.
print(is_safe([3], [[5], [2], [2]], [[10], [4], [9]])) # (True, [1, 0, 2])
print(is_safe([2], [[5], [2], [3]], [[10], [4], [9]])) # (False, [1])
Key takeaways
- Avoidance requires each process to declare its maximum resource need in advance.
- A state is safe if some sequence lets every process finish using free resources plus what earlier processes return.
- Safe implies no deadlock; unsafe does not imply deadlock, only that deadlock can no longer be ruled out.
- Avoidance sacrifices utilisation for a guarantee: it denies requests that would probably have been harmless.
🧪 Practice
- With 12 drives and the table above, is the state safe if
P0holds 6,P1holds 2,P2holds 2? Show the sequence or show that none exists.- Construct a state that is unsafe but from which no deadlock ever actually occurs. Explain what assumption avoidance makes that reality did not.
- Interview-style: "Why does avoidance need maximum-need declarations while prevention does not?" Hint: compare what each strategy has to predict — one reasons about the future of a specific request, the other about the shape of the code.
Resource Allocation Graph Algorithm
Theory
When every resource type has exactly one instance, avoidance does not need the full numeric machinery of the next topic. The resource allocation graph from Section 6.1 can be extended into a decision procedure directly.
Add a third edge type: the claim edge Pi --> Rj, drawn dashed. It means "Pi may request Rj at some point in the future". All claim edges for a process must be present in the graph before that process begins execution — this is exactly the advance-declaration requirement of avoidance, expressed graphically. (A process may add claim edges later only if it currently holds no resources.)
Edges then move through a small lifecycle:
claim (dashed) --request--> request (solid) --grant--> assignment (reversed)
^ |
+---------------------- release -----------------------------+
The rule is one sentence: grant a request only if converting the request edge into an assignment edge leaves the graph free of cycles — counting claim edges as if they were request edges. If a cycle would appear, the requester waits, even though the resource is free.
Treating claim edges as real requests is what makes this avoidance rather than detection. The algorithm reasons about what could happen, not merely what has happened. That conservatism is the same one seen in safe states: some denied requests would have been fine.
Cost is a cycle check per request, O(n^2) in the number of processes. The severe limitation is the single-instance assumption: the moment a resource type has two instances, a cycle stops implying deadlock (Section 6.1) and this algorithm becomes both wrong and unusable. That is precisely the gap the Banker's algorithm fills.
Example
STATE: P1 holds R1. P2 claims both R1 and R2. R2 is free.
----> assignment / request (solid)
....> claim (dashed, future possibility)
+------+ +------+
| R1 |----------> (P1) | R2 |
+------+ assignment . +------+
^ . ^
. . claim .
. claim ..........>| (P1 may want R2 later)
. .
(P2) ..........................>+
claim
P2 NOW REQUESTS R2. R2 is FREE -- but simulate the grant:
R1 -> P1 (assignment, actual)
P1 ..> R2 (claim, treated as a request)
R2 -> P2 (assignment, the grant we are testing)
P2 ..> R1 (claim, treated as a request)
Cycle: P1 -> R2 -> P2 -> R1 -> P1 <- CYCLE FOUND
DECISION: DENY. P2 waits even though R2 sits idle.
Had we granted it and P1 then requested R2, both would be stuck.
# Avoidance for single-instance resource types, on top of the RAG.
# Reuses find_cycle() from Section 6.1.
class AvoidanceRAG(RAG):
def __init__(self):
super().__init__()
self.claims = defaultdict(set) # p -> resources it MAY request
def declare(self, p, resources):
"""All claims must be registered before the process starts."""
self.claims[p] |= set(resources)
def can_grant(self, p, r):
# 1. Tentatively convert the request into an assignment.
self.edges[r].add(p)
# 2. Overlay every claim edge as if it were a real request.
overlay = [(q, s) for q, cs in self.claims.items()
for s in cs if s not in self.edges.get(q, ())]
for q, s in overlay:
self.edges[q].add(s)
cycle = self.find_cycle() # 3. Test the hypothetical graph
for q, s in overlay: # 4. Undo the overlay ...
self.edges[q].discard(s)
if cycle:
self.edges[r].discard(p) # ... and undo the grant if unsafe
return cycle is None # True -> grant, False -> block
Key takeaways
- Claim edges (dashed) express "may request later" and must all be declared before a process runs.
- A request is granted only if the resulting graph, with claims counted as requests, stays acyclic.
- The algorithm may deny a request for a resource that is currently free — that conservatism is the point.
- It applies only when every resource type has exactly one instance; otherwise use the Banker's algorithm.
🧪 Practice
- Draw the graph for three processes and three single-instance resources where a request must be denied even though two of the three resources are free.
- Explain why the algorithm forbids adding claim edges while a process holds resources. What could go wrong otherwise?
- Interview-style: "Why can't you just run cycle detection on the ordinary graph and grant anything that keeps it acyclic?" Hint: an acyclic graph now says nothing about the graph after the next legal request; ask which edges the claim overlay is standing in for.
Banker's Algorithm
Theory
The Banker's algorithm, due to Dijkstra, is avoidance generalised to resource types with multiple instances. The name comes from the analogy in the safe-states topic: a banker who has approved credit lines exceeding cash on hand, and who will only disburse a withdrawal if, afterwards, they can still name an order in which every customer could be fully funded.
Four data structures, for n processes and m resource types:
| Name | Shape | Meaning |
|---|---|---|
Available | vector [m] | Instances of each type currently free |
Max | matrix [n][m] | Maximum each process may ever demand (declared up front) |
Allocation | matrix [n][m] | Instances each process currently holds |
Need | matrix [n][m] | Max - Allocation: what each process may still request |
The algorithm has two parts.
Safety algorithm — is the current state safe? Set Work = Available and Finish[i] = false for all i. Repeatedly find an i with Finish[i] == false and Need[i] <= Work; if found, set Work = Work + Allocation[i], Finish[i] = true, and repeat. If every Finish[i] ends true, the state is safe and the order in which processes were selected is a safe sequence. Complexity O(m * n^2).
Resource-request algorithm — should request Request[i] from process Pi be granted?
- If
Request[i] > Need[i], the process has exceeded its declared maximum: an error, not a scheduling decision. - If
Request[i] > Available,Pimust wait — the resources are simply not there. - Otherwise, pretend to grant it:
Available -= Request[i],Allocation[i] += Request[i],Need[i] -= Request[i]. Run the safety algorithm on this hypothetical state. If safe, make the grant real. If unsafe, roll back all three updates and blockPi.
Step 3 is the whole idea, and it is why the algorithm is expensive: every single request costs a full safety check.
That cost, together with three structural assumptions, is why the Banker's algorithm is taught universally and deployed almost nowhere: processes rarely know their maximum needs in advance, the number of processes and resource types is not fixed in a general-purpose OS, and processes cannot be assumed to return resources promptly. It survives in narrow settings where all three hold — some real-time and embedded systems with a static task set, and some resource managers with declared quotas.
Example
FIVE PROCESSES, THREE RESOURCE TYPES: A=10, B=5, C=7
Allocation Max Need = Max - Allocation
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Allocated total = (7, 2, 5) Available = (10,5,7) - (7,2,5) = (3, 3, 2)
SAFETY CHECK Work = (3,3,2)
P0? Need (7,4,3) > Work -- skip
P1? Need (1,2,2) <= (3,3,2) RUN -> Work = (3,3,2)+(2,0,0) = (5,3,2)
P2? Need (6,0,0) > (5,3,2) -- skip
P3? Need (0,1,1) <= (5,3,2) RUN -> Work = (5,3,2)+(2,1,1) = (7,4,3)
P4? Need (4,3,1) <= (7,4,3) RUN -> Work = (7,4,3)+(0,0,2) = (7,4,5)
P2? Need (6,0,0) <= (7,4,5) RUN -> Work = (7,4,5)+(3,0,2) = (10,4,7)
P0? Need (7,4,3) <= (10,4,7) RUN -> Work = (10,5,7)
All finished. SAFE SEQUENCE = <P1, P3, P4, P2, P0>
REQUEST 1: P1 requests (1, 0, 2)
(1,0,2) <= Need P1 (1,2,2) ok
(1,0,2) <= Available (3,3,2) ok
Pretend: Available=(2,3,0) Alloc P1=(3,0,2) Need P1=(0,2,0)
Safety: <P1, P3, P4, P0, P2> exists -> SAFE -> GRANT
REQUEST 2: P4 requests (3, 3, 0) [from the ORIGINAL state]
(3,3,0) <= Need P4 (4,3,1) ok
(3,3,0) <= Available (3,3,2) ok -- the resources ARE there
Pretend: Available=(0,0,2) Alloc P4=(3,3,2) Need P4=(1,0,1)
Safety: P0 (7,4,3) no; P1 (1,2,2) no; P2 (6,0,0) no;
P3 (0,1,1) no; P4 (1,0,1) no -> nobody can run
UNSAFE -> DENY, P4 blocks despite resources being free
REQUEST 3: P0 requests (0, 2, 0) [from the state after REQUEST 1]
Available (2,3,0); pretend -> Available (2,1,0), Need P0 = (7,2,3)
Safety: P0 no; P1 (0,2,0) needs B=2 > 1 no; P2 no;
P3 (0,1,1) needs C=1 > 0 no; P4 no
UNSAFE -> DENY
def banker_request(pid, request, available, allocation, need):
"""Return True and mutate state if the request is safe; else leave
state untouched and return False (the caller blocks)."""
m = len(available)
# Step 1: exceeding the declared maximum is a programming error.
if any(request[j] > need[pid][j] for j in range(m)):
raise ValueError("request exceeds declared maximum need")
# Step 2: not enough resources exist right now -- plain unavailability.
if any(request[j] > available[j] for j in range(m)):
return False
# Step 3: PRETEND to grant, then test.
for j in range(m):
available[j] -= request[j]
allocation[pid][j] += request[j]
need[pid][j] -= request[j]
max_need = [[allocation[i][j] + need[i][j] for j in range(m)]
for i in range(len(allocation))]
safe, sequence = is_safe(available, allocation, max_need) # from 6.2
if not safe: # roll the hypothetical grant back
for j in range(m):
available[j] += request[j]
allocation[pid][j] -= request[j]
need[pid][j] += request[j]
return False
return True
available = [3, 3, 2]
allocation = [[0,1,0], [2,0,0], [3,0,2], [2,1,1], [0,0,2]]
need = [[7,4,3], [1,2,2], [6,0,0], [0,1,1], [4,3,1]]
print(banker_request(1, [1, 0, 2], available, allocation, need)) # True (safe)
print(banker_request(4, [3, 3, 0], available, allocation, need)) # False (unsafe)
Key takeaways
- The Banker's algorithm extends avoidance to multi-instance resource types using
Available,Max,Allocation, andNeed. - A request is granted only if the hypothetical post-grant state is safe; otherwise the state is rolled back and the process blocks.
- Safety costs
O(m * n^2)per request, so the algorithm is charged on every allocation, not periodically. - It assumes declared maxima, a fixed process and resource population, and prompt release — assumptions general-purpose operating systems cannot make.
🧪 Practice
- From the original table, evaluate
P0requesting(0, 0, 2)— only two instances of C, and two are free. Run the safety check and give the verdict.- Modify
banker_requestto return the safe sequence it found, and explain what an operator could do with that sequence during an incident.- Interview-style: "Databases manage thousands of concurrent transactions and millions of lockable rows. Why don't they run the Banker's algorithm?" Hint: put concrete numbers into
O(m * n^2)per request, and ask whether a transaction can state up front which rows it will touch.
<a id="63-detection-and-recovery"></a>
6.3 Detection and Recovery
The third strategy is to allow deadlock to happen, notice it, and undo it. This section covers the algorithms that notice, the graph that makes noticing cheap, and the two ways to undo: kill something, or take something back.
Detection Algorithms
Theory
Prevention constrains every program forever; avoidance charges a safety check to every request. Both pay continuously to eliminate a rare event. Detection takes the opposite bet: let deadlock occur, pay nothing in the common case, and pay the recovery cost only when it actually happens.
This is what most real systems do — and the most common variant is to do nothing at all, the so-called ostrich algorithm. Linux, Windows, and macOS do not detect deadlocks among ordinary user processes. If your program deadlocks, it hangs, and the user kills it. The justification is economic: deadlocks are rare in correct programs, other bugs are far more common, and the machinery would cost every program something. Databases, by contrast, run detection continuously, because in a database deadlock is routine — it emerges from the interleaving of independently written transactions, not from a bug — and it can be recovered from cleanly by aborting one transaction.
Two detection algorithms exist, matching the two cases from Section 6.1.
Single instance per resource type. Maintain a wait-for graph (next topic) and search for a cycle. Cost is O(V + E) per run with a depth-first search.
Multiple instances. Use an algorithm structurally identical to the Banker's safety check, with one crucial substitution: instead of Need (what a process may eventually request), use Request (what it is actually blocked on right now). Detection is about the present, not the worst case; that single change is the entire difference between avoidance and detection.
Work = Available; Finish[i] = (Allocation[i] == 0)
repeat:
find i with Finish[i] == false and Request[i] <= Work
if found: Work += Allocation[i]; Finish[i] = true
until no such i
Any process with Finish[i] == false is DEADLOCKED.
Initialising Finish[i] = true for processes holding nothing is a small but important detail: a process with no allocation cannot be part of a deadlock cycle, because nobody is waiting on it.
The remaining question is how often to run it. There is a genuine trade-off:
- Run it on every blocked request: detection is immediate and you know exactly which request closed the cycle, but the cost is high on a busy system.
- Run it periodically (say every minute) or when CPU utilisation drops below a threshold (a strong hint that everyone is blocked): cheap, but deadlocks persist for up to one interval, and by the time you look, several processes may be tangled, making the victim harder to choose.
Example
MULTI-INSTANCE DETECTION. A=7, B=2, C=6. All instances allocated.
Allocation Request Available = (0, 0, 0)
A B C A B C
P0 0 1 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
RUN 1: Work = (0,0,0)
P0 Request (0,0,0) <= Work RUN -> Work = (0,0,0)+(0,1,0) = (0,1,0)
P2 Request (0,0,0) <= Work RUN -> Work = (0,1,0)+(3,0,3) = (3,1,3)
P1 Request (2,0,2) <= (3,1,3) RUN -> Work = (5,1,3)
P3 Request (1,0,0) <= (5,1,3) RUN -> Work = (7,2,4)
P4 Request (0,0,2) <= (7,2,4) RUN -> Work = (7,2,6)
Finish = all true -> NO DEADLOCK
(Note it is not even close: the system survives on P0 and P2 releasing.)
RUN 2: P2 now also requests one C. Request P2 = (0, 0, 1)
Work = (0,0,0)
P0 Request (0,0,0) <= Work RUN -> Work = (0,1,0)
P1 (2,0,2) > (0,1,0) no
P2 (0,0,1) > (0,1,0) no <- C is exhausted
P3 (1,0,0) > (0,1,0) no
P4 (0,0,2) > (0,1,0) no
No further progress.
DEADLOCKED SET = { P1, P2, P3, P4 }
One extra request for a single instance of C moved the system from
comfortably safe to a four-process deadlock. Detection tells you WHICH
four; it does not tell you which to kill.
def detect_deadlock(available, allocation, request):
"""Present-tense variant of the safety algorithm: uses Request
(what processes are blocked on NOW), not Need (worst case)."""
n, m = len(allocation), len(available)
work = list(available)
# A process holding nothing cannot be part of a cycle: nobody waits on it.
finish = [all(allocation[i][j] == 0 for j in range(m)) for i in range(n)]
progress = True
while progress:
progress = False
for i in range(n):
if not finish[i] and all(request[i][j] <= work[j] for j in range(m)):
work = [work[j] + allocation[i][j] for j in range(m)]
finish[i] = True
progress = True
return [i for i in range(n) if not finish[i]] # the deadlocked set
alloc = [[0,1,0], [2,0,0], [3,0,3], [2,1,1], [0,0,2]]
req1 = [[0,0,0], [2,0,2], [0,0,0], [1,0,0], [0,0,2]]
req2 = [[0,0,0], [2,0,2], [0,0,1], [1,0,0], [0,0,2]] # P2 asks for one C
print(detect_deadlock([0,0,0], alloc, req1)) # [] -> no deadlock
print(detect_deadlock([0,0,0], alloc, req2)) # [1, 2, 3, 4] -> deadlocked
Key takeaways
- Detection pays nothing in the common case and pays recovery costs only when deadlock actually occurs.
- General-purpose operating systems mostly use the ostrich algorithm; databases detect continuously because deadlock there is routine and cheaply recoverable.
- The multi-instance detector is the Banker's safety algorithm with
Requestsubstituted forNeed— present state instead of worst case. - Detection frequency trades CPU cost against how long a deadlock persists and how many processes get tangled before you look.
🧪 Practice
- Re-run
detect_deadlockwithAvailable = (0, 1, 0)and the second request matrix. Does the deadlock disappear? Explain in terms of the algorithm's first pass.- Explain precisely why
Finish[i]is initialised to true for processes with zero allocation, and construct a state where initialising it to false would report a false deadlock.- Interview-style: "Your OS runs deadlock detection once a minute. What is the argument for running it whenever CPU utilisation falls below 40% instead?" Hint: think about what the CPU is doing while a large set of processes is blocked, and what a fixed interval costs on a system that never deadlocks.
Wait-For Graphs
Theory
The full resource allocation graph carries information detection does not need. If every resource type has one instance, the resource vertices can be collapsed away entirely, leaving a wait-for graph: vertices are processes only, and an edge Pi -> Pj means "Pi is waiting for a resource currently held by Pj".
The collapse rule is mechanical: whenever the RAG contains Pi -> Rk and Rk -> Pj, the wait-for graph contains Pi -> Pj, and Rk disappears. The theorem carries over unchanged — a deadlock exists if and only if the wait-for graph contains a cycle — but the graph is roughly half the size and cycle detection runs on process count alone.
This is the representation real systems actually build:
- MySQL/InnoDB maintains a wait-for graph of transactions and runs detection on every lock wait, aborting the transaction judged cheapest to roll back (error 1213, "Deadlock found when trying to get lock").
- PostgreSQL does not check on every wait — it waits
deadlock_timeout(1 second by default) first, on the theory that most waits resolve on their own, and only then builds the graph. - The JVM exposes
ThreadMXBean.findDeadlockedThreads(), which does exactly this over monitor andLockownership;jstackprints the resulting cycle. - The Linux kernel's
lockdepgoes further: rather than detecting actual cycles, it records the order in which lock classes are acquired and reports a potential deadlock the first time any thread acquires two locks in an order inconsistent with a previously observed one — catching the bug without needing the bad interleaving to occur.
In a distributed system the graph is not held anywhere, and building it is the hard part. Systems use edge-chasing: a blocked process sends a probe message along its wait-for edges, and if a probe returns to its originator, a cycle exists. Because the graph is assembled from snapshots taken at different times, distributed detectors can report phantom deadlocks — cycles that had already dissolved by the time the probe completed.
Example
COLLAPSING THE RESOURCE GRAPH
RESOURCE ALLOCATION GRAPH WAIT-FOR GRAPH
(processes and resources) (processes only)
(P1) --> [R1] --> (P2) (P1) -----> (P2)
^ | ^ |
| v | v
[R3] <-- (P3) <-- [R2] (P3) <--------+
| ^
+--------+ Cycle: P1 -> P2 -> P3 -> P1
=> DEADLOCK
Rule: Pi -> Rk and Rk -> Pj collapses to Pi -> Pj
Valid ONLY for single-instance resource types.
WHAT A JVM THREAD DUMP OF THIS LOOKS LIKE
Found one Java-level deadlock:
=============================
"worker-1":
waiting to lock monitor 0x00007f8b (object 0x000000076ab, a Account),
which is held by "worker-2"
"worker-2":
waiting to lock monitor 0x00007f9c (object 0x000000076cd, a Account),
which is held by "worker-1"
The dump IS the wait-for graph, printed one edge per stanza.
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
import java.util.concurrent.TimeUnit;
/** A watchdog that runs wait-for-graph detection inside a live JVM.
* This is exactly the periodic-detection policy from the previous topic. */
public class DeadlockWatchdog implements Runnable {
private final ThreadMXBean bean = ManagementFactory.getThreadMXBean();
@Override public void run() {
while (!Thread.currentThread().isInterrupted()) {
// Covers both synchronized monitors and java.util.concurrent Locks.
long[] ids = bean.findDeadlockedThreads(); // null when none
if (ids != null) {
// Depth 20 gives enough stack to identify the offending
// acquisition sites, without dumping the whole JVM.
ThreadInfo[] infos = bean.getThreadInfo(ids, 20);
for (ThreadInfo info : infos) {
System.err.printf("DEADLOCK: %s is blocked on %s held by %s%n",
info.getThreadName(),
info.getLockName(), // the resource vertex
info.getLockOwnerName()); // the outgoing edge
}
// The JVM cannot break the cycle for you: no preemption of
// monitors exists. Recovery must be a policy decision.
}
try { TimeUnit.SECONDS.sleep(10); } // detection interval
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}
}
}
-- The database equivalent: InnoDB keeps the wait-for graph itself.
-- After a deadlock, the losing transaction receives error 1213 and
-- the engine records the cycle it found:
SHOW ENGINE INNODB STATUS; -- see the LATEST DETECTED DEADLOCK section
-- PostgreSQL waits before looking, on the assumption most waits resolve:
SHOW deadlock_timeout; -- '1s' by default
Key takeaways
- The wait-for graph removes resource vertices:
Pi -> PjmeansPiwaits for somethingPjholds. - A cycle in it is necessary and sufficient for deadlock, but only when each resource type has one instance.
- Real detectors are wait-for graphs: InnoDB checks on every wait, PostgreSQL after a timeout, the JVM on demand via
ThreadMXBean. lockdepdetects inconsistent lock ordering rather than actual cycles, so it finds latent deadlocks that never occurred.- Distributed detection uses probe messages and can report phantom deadlocks from inconsistent snapshots.
🧪 Practice
- Convert this RAG to a wait-for graph and decide whether a deadlock exists:
P1 -> R1,R1 -> P2,P2 -> R2,R2 -> P3,P3 -> R3,R3 -> P1.- Reproduce a two-thread deadlock in Java and capture it with
jstack. Identify, from the dump alone, the two acquisition sites and the ordering rule that would have prevented it.- Interview-style: "Why does PostgreSQL wait a full second before running detection, while InnoDB checks immediately?" Hint: weigh the cost of building a graph against the probability that a given lock wait is a genuine cycle rather than ordinary contention, and consider each engine's typical transaction length.
Process Termination Strategies
Theory
Detection identifies the deadlocked set; recovery must break it. The blunt option is to destroy a process, thereby forcing the release of everything it holds. Two policies exist.
Abort all deadlocked processes. Guaranteed to break the cycle, guaranteed expensive. Every process in the set loses all its work, including processes that would have finished in milliseconds. Used when the state is so tangled that reasoning about individual victims is not worth the delay, or when correctness demands a clean slate.
Abort one process at a time. Kill one victim, re-run detection, and repeat until the cycle is gone. Much less work is destroyed, but detection runs after every kill, and the choice of victim is now a real decision.
Victim selection weighs several factors, and no single one dominates:
| Factor | Prefer to kill the process that... | Why |
|---|---|---|
| Progress made | has run the shortest time | Least work discarded |
| Work remaining | has the longest still to go | Least sunk investment lost |
| Resources held | holds the most, or the most contended | One kill frees the most, likely ending the deadlock in one step |
| Resources still needed | needs the most more | Least likely to complete soon anyway |
| Priority | has the lowest priority | Policy from Chapter 4 carries over |
| Interactivity | is a batch job, not interactive | An aborted interactive session is a visible failure |
| Restart cost | can be restarted safely | Idempotent work costs almost nothing to redo |
| Rollback count | has been killed fewest times | Prevents starvation-by-repeated-abort |
The last row deserves emphasis. If victim selection depends only on cost, the same cheap process is chosen every time, is rolled back, retries, deadlocks again, and is killed again — it never completes. This is starvation produced by the recovery mechanism itself. The standard fix is to include the number of previous rollbacks in the cost function, so a repeatedly victimised process eventually becomes the expensive choice.
The harder problem is that termination is not always safe. Killing a process mid-update leaves whatever it was modifying in an inconsistent state: a half-written file, a partially rebalanced tree in shared memory, a device left in a mode nobody expects. Databases can terminate freely precisely because every transaction is already wrapped in a rollback mechanism — the state is restorable by construction. Ordinary processes holding a mutex over shared memory are not.
Example
COST-BASED VICTIM SELECTION IN THE DEADLOCKED SET {P1, P2, P3, P4}
Process Runtime Locks held Rows changed Priority Prior aborts Cost
------- ------- ---------- ------------ -------- ------------ ----
P1 0.2 s 2 15 low 0 18
P2 45.0 s 1 90 000 high 0 91 000
P3 1.1 s 4 300 normal 3 3 400
P4 0.4 s 1 40 normal 0 46
Cost ~ work_done + locks_held * w1 + prior_aborts * BIG_PENALTY
Naive choice: P1 (cheapest).
With the rollback penalty, P3 stays protected despite being cheap-ish
on raw work -- it has already been sacrificed three times.
Chosen victim: P1 -> release its 2 locks -> RE-RUN DETECTION
if a cycle remains, choose again.
ABORT_PENALTY = 10_000 # dominates raw cost: prevents starvation
def choose_victim(deadlocked, stats):
"""Lowest cost wins. The rollback count is inside the cost function,
not applied afterwards, so it competes fairly with the other terms."""
def cost(pid):
s = stats[pid]
return (s["cpu_seconds"] * 100 # work that would be discarded
+ s["rows_modified"] # rollback effort
+ s["locks_held"] * 5 # small bonus for freeing many
- s["priority"] * 50 # high priority -> costlier to kill
+ s["prior_aborts"] * ABORT_PENALTY) # anti-starvation
return min(deadlocked, key=cost)
def recover(deadlocked_set, stats, detect):
"""Abort ONE AT A TIME, re-detecting after each kill: often the first
victim frees enough resources to dissolve the whole cycle."""
killed = []
while deadlocked_set:
victim = choose_victim(deadlocked_set, stats)
abort(victim) # releases everything it holds
stats[victim]["prior_aborts"] += 1 # remembered for NEXT time
killed.append(victim)
deadlocked_set = detect() # re-run; may already be empty
return killed
# The application-side contract: a victim must be prepared to be killed.
import time, random
import psycopg2
def transfer_with_retry(conn, src, dst, amount, max_attempts=5):
for attempt in range(max_attempts):
try:
with conn: # commit on success, rollback on error
with conn.cursor() as cur:
cur.execute("UPDATE accounts SET bal = bal - %s WHERE id = %s",
(amount, src))
cur.execute("UPDATE accounts SET bal = bal + %s WHERE id = %s",
(amount, dst))
return True
except psycopg2.errors.DeadlockDetected:
# We were the victim. The database already rolled us back, so the
# state is consistent; retrying is safe. Backoff avoids re-colliding.
time.sleep(random.uniform(0, 0.05 * (2 ** attempt)))
raise RuntimeError("transfer failed after repeated deadlocks")
Key takeaways
- Aborting all deadlocked processes always works and always destroys the most work; aborting one at a time requires re-running detection after each kill.
- Victim selection balances work done, resources held, priority, interactivity, and restart cost.
- Prior rollback count must be part of the cost function, or recovery itself starves the cheapest process.
- Termination is only safe where state is restorable, which is why databases recover cleanly and processes holding raw mutexes do not.
- Any client of a deadlock-detecting system must treat "you were the victim" as a normal outcome and retry with backoff.
🧪 Practice
- Given the table above, compute the cost for each process with and without the rollback penalty. Which victim does each choice select, and what happens on the next deadlock?
- Explain why aborting one process at a time requires re-running detection, and give a state where killing one process resolves two separate cycles.
- Interview-style: "A retail service gets deadlock victim errors under load. The team wants to retry automatically. What must be true of the transaction for that to be correct?" Hint: consider what the database guarantees about the aborted transaction's effects, and what happens if the transaction also sent an email or charged a card.
Resource Preemption and Rollback
Theory
The alternative to killing a process is to take a resource away from it and give it to someone else, leaving the victim alive but set back. This is deadlock recovery by attacking the no preemption condition after the fact rather than before it.
Three problems must be solved together, and none of them can be skipped.
1. Selecting a victim. The same cost calculus as termination, but now applied per resource rather than per process: which resource, held by whom, breaks the cycle at least cost?
2. Rollback. A process that loses a resource mid-use cannot simply continue — it was relying on that resource. It must be rolled back to a state where it did not hold it. Two options:
- Total rollback: abort and restart from the beginning. Simple, and no state needs to be recorded, but it discards everything.
- Partial rollback: return to a checkpoint taken before the resource was acquired, and resume from there. Cheaper per incident, but the system must checkpoint periodically, which costs time and storage even when no deadlock ever occurs.
3. Starvation. If the victim is always chosen by cost, the cheapest process is preempted repeatedly and never completes. The remedy is the one from the previous topic: include the rollback count in the cost so a process cannot be victimised indefinitely.
Databases implement exactly this, and they solve the starvation problem elegantly with timestamp ordering. Each transaction gets a timestamp when it starts; older timestamps mean higher priority. Two well-known schemes decide what happens when transaction T wants a lock held by U:
| Scheme | If T is older than U | If T is younger than U | Property |
|---|---|---|---|
| Wait-die (non-preemptive) | T waits | T dies (aborts and retries with its original timestamp) | Older transactions wait; younger ones abort |
| Wound-wait (preemptive) | T wounds U — U is aborted, T proceeds | T waits | Older transactions preempt; younger ones wait |
Both are deadlock-free by construction: waiting only ever flows in one direction with respect to timestamp order, so a cycle would require a transaction to be both older and younger than itself. And because an aborted transaction keeps its original timestamp on retry, it grows older relative to everyone else and eventually becomes the one that cannot be aborted. Starvation is impossible. Google Spanner and CockroachDB use wound-wait variants for precisely this reason.
Analogy: recovering a shared meeting room. Termination is telling the occupants to abandon their project entirely. Preemption with total rollback is telling them to leave and start their meeting over from scratch tomorrow. Preemption with partial rollback is telling them to leave, but their notes on the whiteboard are photographed first, so they resume from where they were. Checkpointing is the cost of keeping a camera in every room, paid whether or not anyone is ever evicted.
Example
PARTIAL ROLLBACK TO A CHECKPOINT
Process P2's timeline:
start ckpt A acquire R1 ckpt B acquire R2
|------------|---------------|--------------|--------------|-----> DEADLOCK
^ ^
| |
Roll back to ckpt B: P2 gives up R2 only, keeps R1, resumes
from B. Work lost = everything after ckpt B.
Roll back to ckpt A: P2 gives up BOTH R1 and R2.
Work lost = everything after ckpt A. Needed only if
releasing R2 alone does not break the cycle.
Total rollback: P2 restarts from `start`. No checkpoints required,
maximum work lost.
The system chooses the SHALLOWEST rollback that breaks the cycle.
WAIT-DIE vs WOUND-WAIT (T requests a lock held by U)
T older than U T younger than U
---------------------- ----------------------
wait-die T WAITS T DIES (retry, same ts)
wound-wait T WOUNDS U (U aborts) T WAITS
Why neither can cycle:
wait-die -- every wait edge points from an OLDER to a YOUNGER
transaction. A cycle would need ts(T) < ts(T).
wound-wait -- every wait edge points from a YOUNGER to an OLDER one.
Same contradiction, opposite direction.
Why neither starves:
An aborted transaction retries with its ORIGINAL timestamp, so it
becomes progressively older, and eventually no one may abort it.
class Transaction:
def __init__(self, tid, timestamp):
self.tid = tid
self.timestamp = timestamp # assigned ONCE; preserved across retries
self.checkpoints = [] # (label, restorable state)
def checkpoint(self, label, state):
self.checkpoints.append((label, dict(state)))
def rollback_to(self, label):
"""Partial rollback: discard everything after `label` and resume."""
while self.checkpoints and self.checkpoints[-1][0] != label:
self.checkpoints.pop()
return self.checkpoints[-1][1] if self.checkpoints else None
def wound_wait(requester, holder, lock_manager):
"""Preemptive scheme. Older transactions never wait for younger ones,
so wait edges always point young -> old and cannot form a cycle."""
if requester.timestamp < holder.timestamp: # requester is OLDER
lock_manager.abort(holder) # WOUND: preempt the holder
lock_manager.grant(requester) # holder retries later,
return "wounded" # keeping its timestamp
else: # requester is YOUNGER
lock_manager.block(requester, on=holder) # WAIT: safe direction
return "waiting"
def wait_die(requester, holder, lock_manager):
"""Non-preemptive counterpart: nobody is ever forcibly aborted while
holding a lock; the younger requester aborts itself instead."""
if requester.timestamp < holder.timestamp: # requester is OLDER
lock_manager.block(requester, on=holder) # WAIT
return "waiting"
else: # requester is YOUNGER
lock_manager.abort(requester) # DIE: abort and retry
return "died" # with the SAME timestamp
Key takeaways
- Preemption recovers by taking a resource back rather than destroying the process, but the victim must be rolled back to a state consistent with not holding it.
- Total rollback needs no bookkeeping and discards everything; partial rollback needs checkpoints, paid for continuously, and discards less.
- The system should choose the shallowest rollback that breaks the cycle.
- Starvation must be handled explicitly: count prior rollbacks, or preserve timestamps across retries as databases do.
- Wait-die and wound-wait are deadlock-free by construction because every wait edge points consistently in timestamp order, and they are starvation-free because aborted transactions keep their original timestamp.
🧪 Practice
- Three transactions with timestamps
T1=10,T2=20,T3=30contend for the same row in the orderT2holds it, thenT1requests, thenT3requests. Trace the outcome under wait-die and under wound-wait.- A system checkpoints every 500 ms and deadlocks roughly once an hour. Estimate the total checkpointing overhead per deadlock avoided, and argue for or against total rollback instead.
- Interview-style: "Wound-wait aborts more transactions than wait-die under some workloads, yet Spanner chose it. What does it buy?" Hint: compare which transaction gets aborted in each scheme — the one holding locks or the one requesting them — and think about long-running transactions that have already done a lot of work.
<a id="7-memory-management"></a>