Deadlock: Causes, Detection & Prevention

Building an Operating System Kernel: Concurrency, I/O & Synchronization

Chapter 4 · Deadlock: Causes, Detection & Prevention

Chapters 2 and 3 fixed every race condition by making processes wait for each other correctly. This chapter finds the failure mode that creates: two processes can wait for each other so correctly, and so permanently, that neither ever moves again. It reproduces a real deadlock, detects it with the exact same wait-for-graph technique Building a Database Engine used for its own real, measured deadlock, and recovers from it.

Finding 1: A Real, Reproduced Circular-Wait Deadlock

Two processes, two resources, opposite acquisition order — the classic setup:

programs[p1.pid] = [('ACQUIRE', 'A'), ('ACQUIRE', 'B'), ('RELEASE', 'B'), ('RELEASE', 'A')]
programs[p2.pid] = [('ACQUIRE', 'B'), ('ACQUIRE', 'A'), ('RELEASE', 'A'), ('RELEASE', 'B')]
    

Verified directly — 2000 real turns, zero progress, permanently

P1 acquires A, gets preempted, and is now stuck retrying its own ACQUIRE B forever. P2 acquires B, gets preempted, and is stuck retrying ACQUIRE A forever. After 2000 real scheduled turns, both processes are exactly where they started — resource A still held by P1, resource B still held by P2, neither ever advancing a single step. This isn't contention that resolves eventually — it's a permanent, structural circular wait.

Finding 2: A Real Wait-For-Graph Correctly Detects the Cycle

def build_wait_for_graph(dk):
    # edge P -> Q means: P is waiting for a resource Q currently holds
    graph = {}
    for pid, wanted in dk.waiting_for.items():
        holder = dk.resources[wanted].held_by
        if holder is not None and holder != pid:
            graph.setdefault(pid, set()).add(holder)
    return graph
    

Verified directly — built from live kernel state, correctly finds the exact cycle

Reusing the exact wait-for-graph technique from Building a Database Engine's own Transactions & Concurrency Chapter 5 — applied here to real OS-level resources instead of database row locks. The graph built from Finding 1's own live state: {P1: {P2}, P2: {P1}}. A real DFS cycle detector correctly identifies both PIDs as deadlocked.

Finding 3: Ordinary Contention Is Correctly Not Flagged

Verified directly — three processes competing for one resource, no cycle, no deadlock

Three processes all want the same single resource, one after another. Real contention — but every one of them eventually gets it and finishes. No cycle ever forms, because nobody is ever waiting for something held by a process that is, in turn, waiting for them. The detector correctly stays silent: contention alone is not deadlock.

Finding 4: Real Recovery — Abort a Cycle Member, Force-Release Its Resources

Verified directly — the survivor completes its entire remaining program

Reusing Finding 1's own live deadlocked state: one process (P1) is aborted, and every resource it currently holds is forcibly released. Resource A becomes free — P2's own pending ACQUIRE A finally succeeds, and P2 completes its entire remaining program in a handful of real steps. The system was never actually broken; it was permanently stuck — and recovery correctly distinguishes and resolves that.

Where This Connects

This chapter's finding	What it connects to
The wait-for-graph and cycle detection	Building a Database Engine's own Transactions & Concurrency Chapter 5 — the identical technique, applied to a genuinely different kind of resource
Two mutexes, acquired in opposite order	Chapter 2's own `Mutex` — reused directly, extended only with a `held_by` field the detector needs
Deadlock as a permanent, structural failure	Course 1 Chapter 9's own indefinite starvation finding — both are real, measured "this genuinely never resolves," not a rare or probabilistic outcome
Preventing the cycle from ever forming	Exercise 2's own consistent-acquisition-order rule — a real alternative to detect-and-recover, closing off the failure mode structurally instead

Hands-On Exercises

Exercise 1

Build a real 3-process deadlock: process 1 holds X and wants Y, process 2 holds Y and wants Z, process 3 holds Z and wants X. Confirm it's permanent, and confirm the exact same cycle-detection code from Finding 2 correctly identifies all three processes with no changes.

📄 View solution

Exercise 2

Rerun Finding 1's exact scenario, but change both processes to acquire resources in the same order (A then B for both). Confirm the deadlock no longer occurs at all, and explain why this counts as real deadlock prevention rather than detection-and-recovery.

📄 View solution

Exercise 3

Reproduce Finding 1's own deadlock alongside a third, uninvolved bystander process. Deliberately abort the bystander instead of a real cycle member, and confirm the deadlock is completely unaffected. Explain why.

📄 View solution

Chapter 4 Quick Reference

OwnedMutex: Chapter 2's own Mutex, extended with a real held_by PID — the one fact a wait-for-graph needs
Verified Finding 1: two processes acquiring two resources in opposite order deadlock permanently — 2000 real turns, zero progress
Verified Finding 2: a real wait-for-graph, built from live kernel state, correctly detects the exact cycle via DFS
Verified Finding 3: ordinary contention for a single shared resource never forms a cycle, and is correctly left undetected
Verified Finding 4: forcibly releasing a real cycle member's own resources breaks the deadlock and lets the survivor complete
Golden rule: deadlock isn't broken code — it's correct code, correctly waiting, forever; detection needs to see the whole graph, not any single process in isolation
Next chapter: Inter-Process Communication: Pipes & Message Queues