Deadlock Modeling &
System-Level Handling

T_save locks the document, then asks for the log. T_flush locks the log, then asks for the document. If both get their first lock before either asks for the second, neither request can ever be granted. This isn't a bug in either thread's logic — each one, read alone, is completely correct. The problem only exists in how the two combine.

Two cooks, one knife, one cutting board

Imagine two cooks sharing a kitchen with exactly one knife and one cutting board. Cook A grabs the knife, Cook B grabs the board. Cook A now needs the board; Cook B now needs the knife. Both are perfectly willing to share — they'll hand over what they're holding the instant they're done with it — but neither will ever be done, because neither can start without the thing the other is holding. This is a deadlock: a set of threads, each waiting for a resource held by another thread in the same set, with no possible sequence of events that lets any of them proceed.

Modeling: the four conditions and the graph

Coffman, Elphick, and Shoshani proved in 1971 that all four of the following must hold simultaneously for a deadlock to exist. Break any one, and deadlock becomes structurally impossible — not just unlikely.

A resource-allocation graph (RAG) makes circular wait visible directly: processes and resources are nodes, an edge from a resource to a process means "held by," and an edge from a process to a resource means "wants." A cycle in this graph is the circular-wait condition, drawn.

Figure 1 · the cycle, drawn

Prevention: make one condition structurally impossible

Prevention attacks one of the four conditions so deadlock literally cannot arise, at some cost in flexibility or efficiency.

Applied to the spine: declare "document lock always before log lock," system-wide. T_save already follows this. T_flush is rewritten to acquire the document lock first too, even though it uses the log lock first logically — the acquisition order is what matters, not the order of use. With both threads obeying the same order, the cycle in Figure 1 can never form: whichever thread gets the document lock first is guaranteed to be able to get the log lock too, because the other thread can't have skipped ahead to grab it out of order.

Avoidance: allow the conditions, refuse unsafe requests

Prevention forecloses a condition permanently, everywhere. Avoidance is more surgical: allow all four conditions to exist in general, but before granting any single request, check whether granting it could still lead somewhere safe. Dijkstra's Banker's algorithm does exactly this, provided every thread declares its maximum possible need for each resource type up front.

A state is safe if there's some order to finish every thread one at a time, where each thread's remaining Need can be met from Available plus whatever earlier-finishing threads have released. A request is granted only if the resulting state is still safe — otherwise the requester waits, even though the resources it's asking for happen to be free right now.

Worked example: three resource pools, four residents

WriteWell's process now tracks three shared pools: network connections (9 total), disk I/O buffers (6 total), and worker-thread slots (7 total).

Available right now (Total − sum of Allocation): R1=3, R2=2, R3=3.

Running the safety algorithm: T_flush's need (2,2,2) fits in Available (3,2,3), so it can finish first, releasing (2,0,1) back — Available grows to (5,2,4). From there, B_sync (4,1,2) fits, then P_backup (2,2,1), then T_save (4,1,1) last. Safe sequence: T_flush → B_sync → P_backup → T_save. The state is safe.

The second request looks tiny — one more disk buffer — and would still be well within T_save's own declared Need. It's refused anyway, because granting it leaves not one single thread able to finish with what remains. Nothing has deadlocked yet at the moment of the request; the Banker's algorithm's whole job is refusing to walk into a state where deadlock becomes inevitable, before it happens.

Figure 2 · try your own request

Practice 4.1

1. Which single Coffman condition does "always acquire locks in the same global order" attack, and why does breaking just that one condition prevent deadlock even though the other three still hold?
   Show solution

   Circular wait. Mutual exclusion, hold-and-wait, and no-preemption can all still be true, but a global order means it's never possible for thread A to hold what thread B wants while thread B holds what thread A wants — whichever resource comes first in the order, some thread will always be able to get it uncontested, breaking any potential cycle before it can close.

2. Variation. If T_save's Need were (4,1,1) but Available were only (3,1,3) with nothing else pending, could T_save finish right now?
   Show solution

   No — Need (4,1,1) is not ≤ Available (3,1,3) in the first component (4>3). T_save must wait, regardless of what any other thread is doing, until enough R1 becomes available.

3. Interpretation. A system uses the Banker's algorithm and never deadlocks. Does that mean deadlock was impossible for this workload regardless of allocation policy?
   Show solution

   No — it means the avoidance policy successfully steered around every unsafe state it was offered. The same threads, with a naive first-come allocator instead, could easily deadlock. Avoidance doesn't mean deadlock was never possible; it means every request that would have led somewhere unsafe was refused.

4. Synthesis. Connect prevention's "eliminate hold-and-wait" strategy back to Chapter 3's bounded buffer: would requiring T_save and T_flush to acquire all three semaphores at once (instead of one at a time) actually help here?
   Show solution

   It would eliminate hold-and-wait for this specific interaction (no thread would ever hold one semaphore while waiting for another), but at the same cost noted in the prevention table: T_save would hold mutex for its entire operation instead of just the few lines that touch the buffer, blocking unrelated access far longer than necessary. It solves the deadlock at the cost of a large chunk of Chapter 3's own concurrency benefit.

Section 4.1's approaches both cost something before a deadlock ever threatens: prevention gives up flexibility permanently, avoidance needs advance knowledge of every thread's maximum need. A third philosophy pays nothing upfront: let the four conditions hold freely, let deadlocks actually happen, and run a smoke detector.

Detection: collapse the graph, look for a cycle

Take Figure 1's resource-allocation graph and collapse each resource node away, replacing "process wants a resource held by another process" with a direct edge between the two processes. This wait-for graph makes the check almost trivial: T_save waits for T_flush; T_flush waits for T_save. A 2-node cycle, found by the same kind of cycle-detection a compiler uses to catch circular imports. For single-instance resources (true of both locks here), a cycle in the wait-for graph is exactly a deadlock — found after the fact, rather than refused in advance the way Section 4.1's Banker's algorithm does.

Recovery: now that you've found it, what do you do?

The trade-off: how often do you even look?

Running the detection algorithm isn't free, and the choice of when to run it is its own balancing act, structurally identical to trade-offs already seen twice in this book: Chapter 1's context-switch-overhead curve and Chapter 2's scheduling quantum.

Practice 4.2

1. In the wait-for graph for the spine deadlock, how many nodes and how many edges does the cycle have?
   Show solution

   Two nodes (T_save, T_flush) and two edges (each waiting for the other) — the smallest possible cycle. Collapsing the two resource nodes out of Figure 1's four-node RAG leaves exactly this.

2. Variation. If recovery kills only T_flush, does T_save immediately proceed?
   Show solution

   Yes. Killing T_flush releases the log lock it was holding; T_save's pending request for that lock can now be granted, breaking the cycle with a single termination rather than requiring both threads to be killed.

3. Interpretation. A system runs deadlock detection once every 30 seconds. A deadlock forms 2 seconds after a check. How long do the affected threads sit stuck before recovery even begins?
   Show solution

   Up to 28 seconds — the deadlock isn't found until the next scheduled check, roughly 30 seconds after the previous one, minus the 2 seconds that had already elapsed. This is exactly the fixed-timer policy's accuracy cost from the table above, made concrete.

4. Synthesis. Explain why resource preemption's victim-selection problem is a direct preview of Section 4.4, before you've even read it.
   Show solution

   If victim selection always favours the same criteria (say, "always preempt whichever thread holds the fewest resources"), one unlucky thread matching that profile repeatedly could be rolled back every single time a deadlock involving it is detected, never actually completing — the system keeps making progress overall, just never for that one thread. That is precisely Section 4.3's definition of starvation, arrived at from the recovery side rather than the scheduling side.

Both look like "a thread that never gets what it's waiting for." They are not the same failure, they don't have the same fix, and conflating them is a reliable way to lose marks on exactly this kind of question.

Where the two meet: allocation policy is the shared cause

Chapter 2 already showed this trade-off once, from the scheduling side: plain Priority scheduling can starve a low-priority thread indefinitely if higher-priority threads keep arriving, and the fix was aging — gradually raising priority the longer a thread waits. Resource allocation has the identical tension. A resource-granting policy based on priority, or on whichever request looks "safest" to grant (Section 4.1's Banker's algorithm doesn't rule this out), can systematically favour some threads over others. Nothing about that is a deadlock — the system keeps running, resources keep getting granted — but a consistently-deprioritised thread can wait indefinitely all the same.

Strict FCFS resource queuing is the opposite choice: grant requests in arrival order, full stop. This makes starvation structurally impossible (Chapter 2's Round Robin argument applies unchanged: bounded position in a queue is a bounded wait) at the cost of the flexibility priority-based or safety-based allocation offered — an urgent request can still be stuck behind a pile of older, less urgent ones.

Practice 4.3

1. A monitoring dashboard shows one thread that hasn't run in ten minutes, while every other thread on the system is actively making progress. Deadlock or starvation?
   Show solution

   Starvation. Deadlock requires that no thread in the affected set can progress; here, everything else is fine, which rules out deadlock by definition regardless of how long the one thread has waited.

2. Variation. Would switching that system's resource-granting policy from priority-based to strict FCFS fix the problem, and what would it cost?
   Show solution

   Yes — FCFS guarantees a bounded wait, eliminating this kind of starvation structurally. The cost is the same one Chapter 2 identified for Round Robin: every request is now served in arrival order regardless of urgency, so a genuinely time-critical request can be stuck behind a long queue of routine ones that arrived first.

3. Interpretation. Does using the Banker's algorithm (Section 4.1) guarantee no thread will starve?
   Show solution

   No. Banker's algorithm guarantees the system never enters an unsafe state, which prevents deadlock — it says nothing about whether one particular thread's requests happen to keep landing in the "would be unsafe" category while others' don't. Avoidance and starvation-freedom are separate guarantees; a system can have one without the other.

4. Synthesis. Explain, in terms of the Coffman conditions, why starvation doesn't need any of the four to hold.
   Show solution

   The Coffman conditions describe a structural configuration that makes progress impossible. Starvation doesn't require impossibility — it only requires that a policy keeps choosing not to grant a particular thread's request, even though granting it would be entirely possible and would not violate mutual exclusion, hold-and-wait, no-preemption, or circular wait in any way. It's a fairness failure, not a structural one.

Starvation, briefly revisited

Section 4.3 defined it: a thread indefinitely denied a resource while the rest of the system keeps moving. The fix is the same one Chapter 2 already used for Priority scheduling: aging — gradually raise a waiting thread's priority (or its position in a resource queue) the longer it waits, so it eventually outranks everything else and is guaranteed to get through.

Livelock: busy, active, and still stuck

Deadlock's threads are passive — blocked, using no CPU, waiting for something that will never come. Livelock is the active twin: threads keep changing state in direct response to each other, consuming real CPU time, and still make no forward progress. Two people in a hallway who both step left to let the other pass, then both step right for the same reason, forever, are livelocked — neither is standing still, and neither is getting anywhere.

Worked example: a deadlock "fix" that trades one bug for another

Suppose T_save and T_flush try to avoid Section 4.1's deadlock without imposing a lock order: each grabs its first lock, tries the second with a short timeout, and if that fails, releases what it's holding and retries after a fixed delay.

No thread is ever blocked for more than an instant, no cycle ever sits still long enough for Section 4.2's detector to even catch it — and neither thread ever finishes an autosave. The timeout-and-backoff fix genuinely solved deadlock (nothing waits forever) while introducing livelock (nothing finishes, either) in its place.

All three, side by side

Practice 4.4

1. Two threads retry a failed lock acquisition using the exact same fixed 100ms delay, forever. Deadlock, starvation, or livelock?
   Show solution

   Livelock — both threads are actively running (acquiring, failing, releasing, waiting, retrying) rather than blocked, and neither ever completes despite the constant activity.

2. Variation. If only T_save retries with a fixed delay while T_flush retries with a randomised one, is livelock still likely?
   Show solution

   Much less likely. Livelock in this example depends on both threads' retries landing at the same instant, round after round; if even one side's timing varies randomly, their attempts will drift apart within a few rounds and one will eventually succeed while the other is still waiting.

3. Interpretation. A support ticket says "the server's CPU has been at 95% for an hour, but no requests are completing." Which of this chapter's three failures does that best match, and why not the other two?
   Show solution

   Livelock. High, sustained CPU usage rules out deadlock (whose stuck threads are blocked, not running) and points away from simple starvation (which wouldn't typically drive CPU usage up across the board, only deny progress to specific threads while others complete normally) — active CPU use combined with zero completions is livelock's signature.

4. Synthesis. Explain why aging (Section 4.3's starvation fix) would do nothing to solve the livelock in the worked example above.
   Show solution

   Aging works by eventually giving a waiting thread top priority so a scheduler or allocator is forced to favour it. In the livelock example, both threads already have equal standing and neither is being systematically deprioritised — the problem is purely timing symmetry between two equally-privileged threads, which raising one's priority over time doesn't address at all. Aging fixes an unfairness problem; livelock here is a synchronisation problem.