Deadlock Detection and Avoidance

A deadlock is a state in which a set of threads (or processes, or transactions) are each waiting for a resource that another thread in the set holds — none can proceed; the system is stuck. The seminal Coffman, Elphick, and Shoshani 1971 paper “System Deadlocks” identified four necessary conditions for deadlock — mutual exclusion, hold and wait, no preemption, and circular wait — all four of which must hold simultaneously. Strategies for handling deadlock partition into four categories: (1) Detection — let it happen, then find and recover (build a wait-for graph; look for a cycle); (2) Prevention — design the system so one of the four conditions cannot hold (e.g., always acquire locks in a canonical order — breaks circular wait); (3) Avoidance — at runtime, deny resource requests that would lead to an unsafe state, even if the request itself doesn’t deadlock now (Dijkstra’s Banker’s Algorithm); (4) Ignore — the “ostrich algorithm” (Tanenbaum); reboot when it happens. In real systems: OS process scheduling uses detection + recovery (Linux); database transaction managers use detection + transaction-rollback (PostgreSQL, MySQL); application code typically uses prevention via resource hierarchy. Banker’s algorithm is mostly textbook material — it requires knowing each process’s maximum future resource needs upfront, rarely practical.

1. Intuition — A Standoff at the Door

Imagine two people meeting in a narrow corridor. Each is carrying a wide package and needs to pass through, but the corridor is barely wider than one package. Each refuses to step aside until the other passes; neither will pass without the other stepping aside. They stand there indefinitely. Deadlock.

Now scale up: four trucks at a four-way intersection, each waiting for the truck on its right (or left, depending on the country) to clear before proceeding. Each is waiting for one specific other; the wait-for relation forms a cycle of length 4. Nobody moves. Classic deadlock.

The structure is universal in concurrent computing. Each thread holds some resources (locks, file handles, database row locks, semaphore tokens, memory buffers) and is waiting for more. If the waiting forms a directed cycle in the “T1 waits for T2’s resources” graph, no thread can proceed unless someone yields, and nobody is willing.

The deep observation is that deadlock is not an accident — it requires four specific conditions to all hold simultaneously. Remove any one and deadlock becomes impossible. The Coffman et al. 1971 paper made this rigorous; every modern textbook on operating systems carries the four conditions. Once you see them, you see deadlock-prevention everywhere as the strategy of “pick the easiest condition to break and break it.”

2. Tiny Worked Example — Two Threads, Two Locks

Two threads T1 and T2, two mutexes A and B. Each thread needs both mutexes to do its work but acquires them in different orders.

T1:                       T2:
acquire(A)                acquire(B)
acquire(B)                acquire(A)
do work                   do work
release(B)                release(A)
release(A)                release(B)

Possible interleaving:

Step	T1	T2	State
1	`acquire(A)` ✓		T1 holds A
2		`acquire(B)` ✓	T1 holds A, T2 holds B
3	`acquire(B)` blocks		T1 waits for B (held by T2)
4		`acquire(A)` blocks	T2 waits for A (held by T1)
5	(waiting)	(waiting)	Deadlock: cycle T1 → T2 → T1

The wait-for graph at step 5: T1 → T2 → T1. A cycle of length 2. Both threads are blocked forever (until killed externally). All four Coffman conditions hold: A and B are mutually exclusive; T1 holds A while waiting for B (hold and wait); the system can’t take A away from T1 (no preemption); the wait-for cycle exists.

The fix — resource hierarchy / canonical lock order — is to pick a fixed order (say, “always acquire A before B”) and have every thread acquire in that order. Then the wait-for cycle is impossible: a thread holding B cannot be waiting for A, because if it followed the order, it would have acquired A first. This breaks circular wait, eliminating deadlock.

3. The Four Coffman Conditions (Coffman, Elphick, Shoshani 1971)

These four conditions are necessary (all must hold for deadlock to occur) and (collectively for the standard model) sufficient (if all four hold, deadlock is at least possible). Breaking any one makes deadlock impossible.

3.1 Mutual Exclusion

A resource is held in non-shared mode — at most one thread can hold it at a time. Some resources are inherently exclusive (a printer, a file lock, an exclusive mutex); some can be shared (read locks, atomic-counter increments). If all resources were shareable, deadlock would be impossible — multiple threads could hold them simultaneously and never wait.

3.2 Hold and Wait

A thread holds at least one resource and is waiting to acquire additional resources held by other threads. If a thread always acquires all resources it needs in one atomic step (and waits with empty hands until all are available), hold-and-wait cannot occur.

3.3 No Preemption

A resource cannot be forcibly taken from the thread currently holding it; it must be released voluntarily. Some resources are preemptible — CPU time, memory pages can be paged out — for which deadlock is not an issue. For most synchronization primitives (mutexes, file locks), preemption is not allowed, so this condition holds.

3.4 Circular Wait

A directed cycle exists in the wait-for graph: T1 → T2 → ... → Tn → T1. Each Ti is waiting for a resource held by Ti+1, with Tn+1 = T1. Without a cycle, the wait-for graph is a forest, and there’s always a “leaf” thread (waiting for nothing) that will eventually progress, freeing a resource for the next thread, etc.

These four are necessary but interrelated. In particular, if mutual exclusion fails, hold-and-wait can’t form on shared resources; if hold-and-wait fails, circular wait can’t form. They’re four facets of the same underlying structure, and breaking any one breaks the whole.

4. Strategies for Handling Deadlock

4.1 Strategy 1 — Detection and Recovery

Allow deadlocks to happen; detect them; recover.

Detection = build the wait-for graph and search for a cycle. Run periodically (every N seconds), or on demand (when a thread has been blocked for “too long”). Algorithms exist for both single-instance resources (any cycle ⇒ deadlock) and multi-instance resources (cycle is necessary but not sufficient — see Holt 1972’s “Knot” detection).

Recovery = break the deadlock. Options:

Process termination: kill one or more threads in the cycle. “Victim selection” picks the cheapest-to-restart thread (least work done, lowest priority, fewest resources held). Database deadlock detection (PostgreSQL, MySQL InnoDB) does exactly this — one transaction is chosen as victim and rolled back, and the application is expected to retry.
Resource preemption: forcibly take a resource from one thread and give it to another, then later restore. Hard for non-checkpointable threads — most application threads are not designed to handle losing a mutex mid-critical-section.
Rollback: if the system supports checkpoints (databases, transactional memory), roll back to a checkpoint where the deadlock didn’t exist.

Trade-offs: detection is expensive (running a cycle-search periodically), and recovery is disruptive (kills work). But it requires no a-priori knowledge of resource needs and works for arbitrary code. The Linux kernel’s lockdep is a sophisticated runtime detector for kernel deadlocks, used during testing.

4.2 Strategy 2 — Prevention

Design the system so that one of the four conditions cannot hold, removing deadlock by construction.

Break Mutual Exclusion (rare in practice):

Make resources read-shareable when possible. Read-write locks (Reader-Writer Problem) allow concurrent readers, sometimes eliminating the deadlock potential of read-heavy workloads.
Use lock-free data structures (atomics, CAS), eliminating the lock entirely.

Break Hold and Wait:

All-or-nothing acquisition: a thread requests all needed resources at once and either gets all of them atomically or none. (std::lock(mutex1, mutex2, ...) in C++ does deadlock-free multi-lock acquisition; try_lock patterns can simulate it.)
No-resource-held requests: a thread releases all resources before requesting new ones. Requires the request to be fully restartable, which is often impractical.

Break No Preemption:

Try-lock with timeout: if you can’t get a resource within T seconds, give up, release what you hold, and retry. Avoids permanent deadlock but introduces livelock (everyone times out and retries simultaneously, forever).
Priority preemption: a higher-priority thread can take a resource from a lower-priority holder. Used in real-time systems with priority inheritance protocols. Risk: priority inversion (see Mutex vs Semaphore vs Condition Variable §7.10).

Break Circular Wait (the standard, practical choice):

Resource hierarchy / canonical lock order: assign a total order to all resources; every thread acquires resources in that order. Cycles are impossible because any cycle would require some thread to acquire a higher-ordered resource before a lower-ordered one. This is the workhorse strategy in real concurrent programs. See Dining Philosophers §4 for the canonical example.
Linux kernel uses lock-class ordering enforced by lockdep; PostgreSQL uses lock-id ordering; many C++ codebases enforce the rule statically with linters.

Cost of prevention: usually low (a constant per acquire to check the ordering invariant) — much cheaper than detection. Cost: requires engineering discipline (everyone follows the order) and global knowledge (what is the canonical order?). In large codebases this is hard but doable.

4.3 Strategy 3 — Avoidance (Banker’s Algorithm)

A more sophisticated approach: at each resource request, check whether granting it would lead to a safe state — a state from which all threads can eventually complete. If yes, grant; if no, defer the request (block the thread).

This is Dijkstra’s Banker’s Algorithm (EWD 108, 1965), so named because of the analogy with a bank: the bank has limited reserves; clients have credit limits; the bank grants a partial loan only if it can see a sequence of “if I give Alice $X, s h e^{'} l l p a y ba c k$ X+Y; then I have enough for Bob…” — a safe sequence exists.

Inputs:

n processes and m resource types.
Available[m]: vector of currently available units of each resource.
Max[n][m]: maximum demand of each process for each resource (declared up front; this is the controversial requirement).
Allocation[n][m]: currently allocated to each process.
Need[n][m] = Max[n][m] - Allocation[n][m].

Safety algorithm — given a state, determine if it’s safe:

Work = Available
Finish[i] = false for all i
loop:
    find some i such that Finish[i] == false AND Need[i] <= Work
    if found:
        Work += Allocation[i]      # process i can finish; releases its resources
        Finish[i] = true
    else:
        break
return all Finish[i] == true       # if yes, safe; else unsafe

Resource-request algorithm — when process i requests Request[i]:

If Request[i] > Need[i]: error (process exceeded its declared max).
If Request[i] > Available: process must wait.
Pretend to grant: Available -= Request[i]; Allocation[i] += Request[i]; Need[i] -= Request[i].
Run the safety algorithm.
If safe: grant. If unsafe: roll back the pretend-grant; process must wait.

Why it works: Banker’s never enters an unsafe state, hence never enters a deadlocked state (deadlocked ⇒ unsafe). The proof is in Habermann 1969.

Why it’s mostly textbook material:

Requires Max[n][m] declared up front. In real applications, you almost never know the maximum future resource needs of a process — they depend on data, on user input, on dynamic loading.
Computational cost: O(n²m) per request. Acceptable for small n, m, prohibitive for thousands of threads.
Conservative: many requests are denied even though no actual deadlock would have occurred. Throughput suffers.

In practice, Banker’s appears in operating-systems coursework and exam questions, not in production schedulers. Modern OSes use detection or prevention.

4.4 Strategy 4 — Ignore (the Ostrich Algorithm)

Tanenbaum’s term: “stick your head in the sand and pretend deadlocks can’t happen.” Some systems do effectively ignore deadlock — UNIX traditionally has, accepting that file-locking deadlocks crash the offending application. The argument: deadlocks are rare, the cost of detection/prevention is high, and the user can manually kill the offending process when needed.

The ostrich approach is rational when:

Deadlocks are statistically rare for the workload.
Recovery (kill + restart) is cheap.
Detection/prevention overhead would dominate normal operation.

It’s irrational when:

Deadlocks lead to loss of unsaved work.
Deadlocks compound (one stuck thread holds resources that block more threads).
Production reliability is critical.

The right strategy is workload-dependent. Most production systems use a combination — prevention as the primary mechanism (canonical lock order), detection as the fallback (timeout-based rescue), and recovery via process restart for the last-mile cases.

5. Pseudocode — Wait-For Graph Cycle Detection

Detection algorithm: maintain a directed graph where vertices are threads and edges go T1 → T2 whenever T1 is waiting for a resource held by T2. Periodically (or on demand) search for cycles.

class WaitForGraph:
    def __init__(self):
        self.edges = defaultdict(set)        # edges[T] = set of threads T is waiting for
    def add_wait(self, t_waiter, t_holder):
        self.edges[t_waiter].add(t_holder)
    def remove_wait(self, t_waiter, t_holder):
        self.edges[t_waiter].discard(t_holder)
    def detect_cycle(self):
        WHITE, GRAY, BLACK = 0, 1, 2
        color = defaultdict(lambda: WHITE)
        cycle = []
        def dfs(u, path):
            color[u] = GRAY
            for v in self.edges[u]:
                if color[v] == GRAY:
                    cycle.extend(path[path.index(v):] + [v])
                    return True
                if color[v] == WHITE and dfs(v, path + [u]):
                    return True
            color[u] = BLACK
            return False
        for u in list(self.edges.keys()):
            if color[u] == WHITE and dfs(u, []):
                return cycle
        return None

This is exactly Depth-First Search-based cycle detection in a directed graph (see Topological Sort for the related algorithm). For multi-instance resources, the graph requires a more nuanced “knot” detection (Holt 1972) that distinguishes “resource is held by some process in the cycle” from “every instance is held by a process in the cycle.”

6. Python Demonstration — Simulating Deadlock Detection

import threading
import time
from collections import defaultdict
 
# A wait-for graph maintained centrally (illustrative; real systems do it in the OS or DB)
class DeadlockDetector:
    def __init__(self):
        self.lock = threading.Lock()
        self.wait_for = defaultdict(set)         # thread_id -> set of thread_ids waited on
        self.holds   = defaultdict(set)          # thread_id -> set of resources held
        self.held_by = {}                        # resource -> thread_id
 
    def request(self, tid, resource):
        with self.lock:
            holder = self.held_by.get(resource)
            if holder is not None and holder != tid:
                self.wait_for[tid].add(holder)
                cycle = self._detect_cycle()
                if cycle:
                    print(f"DEADLOCK detected involving threads {cycle}")
                    return False
            return True
 
    def acquire(self, tid, resource):
        with self.lock:
            self.held_by[resource] = tid
            self.holds[tid].add(resource)
            self.wait_for[tid].discard(...)      # cleanup waits
 
    def release(self, tid, resource):
        with self.lock:
            self.held_by.pop(resource, None)
            self.holds[tid].discard(resource)
 
    def _detect_cycle(self):
        WHITE, GRAY, BLACK = 0, 1, 2
        color = defaultdict(lambda: WHITE)
        path = []
        def dfs(u):
            color[u] = GRAY
            path.append(u)
            for v in self.wait_for[u]:
                if color[v] == GRAY:
                    return path[path.index(v):]
                if color[v] == WHITE:
                    cycle = dfs(v)
                    if cycle: return cycle
            color[u] = BLACK
            path.pop()
            return None
        for u in list(self.wait_for.keys()):
            if color[u] == WHITE:
                cycle = dfs(u)
                if cycle: return cycle
        return None

This is a centralized detector; in practice, OSes maintain the graph at the kernel level, and databases at the transaction-manager level. Detection is expensive enough that most systems run it only periodically (every ~1 second), accepting that a freshly-formed deadlock takes up to that interval to detect.

7. Python — Banker’s Algorithm

def banker_safe_state(n, m, available, max_demand, allocation):
    """
    Return True if the current allocation is safe (i.e., a finish sequence exists).
    n: number of processes; m: number of resource types
    available[m], max_demand[n][m], allocation[n][m]
    """
    need = [[max_demand[i][j] - allocation[i][j] for j in range(m)] for i in range(n)]
    work = list(available)
    finish = [False] * n
 
    while True:
        progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
                # Process i can complete; it will release its allocation
                for j in range(m):
                    work[j] += allocation[i][j]
                finish[i] = True
                progress = True
        if not progress:
            break
 
    return all(finish)
 
 
def banker_request(n, m, available, max_demand, allocation, process_i, request):
    """
    Decide whether to grant request[m] to process_i.
    Mutates available and allocation if granted.
    """
    need_i = [max_demand[process_i][j] - allocation[process_i][j] for j in range(m)]
    if any(request[j] > need_i[j] for j in range(m)):
        raise ValueError("Process exceeded declared maximum")
    if any(request[j] > available[j] for j in range(m)):
        return False  # not enough resources right now; process must wait
 
    # Pretend to grant
    new_available = [available[j] - request[j] for j in range(m)]
    new_allocation = [list(row) for row in allocation]
    for j in range(m):
        new_allocation[process_i][j] += request[j]
 
    if banker_safe_state(n, m, new_available, max_demand, new_allocation):
        # Commit
        for j in range(m):
            available[j] = new_available[j]
            allocation[process_i][j] = new_allocation[process_i][j]
        return True
    else:
        return False  # would lead to unsafe state; deny
 
 
# Worked example
# 5 processes, 3 resource types (A=10, B=5, C=7)
available = [3, 3, 2]
max_demand = [
    [7, 5, 3],   # P0
    [3, 2, 2],   # P1
    [9, 0, 2],   # P2
    [2, 2, 2],   # P3
    [4, 3, 3],   # P4
]
allocation = [
    [0, 1, 0],   # P0
    [2, 0, 0],   # P1
    [3, 0, 2],   # P2
    [2, 1, 1],   # P3
    [0, 0, 2],   # P4
]
print(banker_safe_state(5, 3, available, max_demand, allocation))
# True; safe sequence exists: P1 → P3 → P0 → P2 → P4 (the textbook example)

The “safe sequence” P1 → P3 → P0 → P2 → P4 means: with current state, P1 can finish first (its Need = [1, 2, 2] ≤ Available = [3, 3, 2]); after P1 finishes, available becomes [5, 3, 2]; then P3 can finish; etc.

8. Real-World Examples

8.1 Linux Kernel `lockdep`

The Linux kernel includes a runtime deadlock detector called lockdep (lock dependency validator). When enabled (CONFIG_PROVE_LOCKING), it tracks every lock acquisition and builds a dependency graph in real time. If a new acquisition would create a cycle, lockdep immediately reports the bug — even if the actual deadlock would only manifest under specific scheduling. Used during kernel development and testing; turned off in production for performance.

This is prevention by static-pattern detection at runtime: rather than waiting for the cycle to actually deadlock, detect that the potential cycle exists and flag the bug. Conceptually similar to a type system catching errors before they execute.

8.2 PostgreSQL Transaction Deadlock Detection

PostgreSQL maintains a wait-for graph of transactions. Periodically (every deadlock_timeout, default 1 second), it runs cycle detection. If a cycle is found, one transaction is chosen as the victim and rolled back with error code 40P01 (deadlock_detected). The victim is typically the transaction with the lowest priority or that has done the least work; the application is expected to catch the error and retry.

This is detection + recovery via transaction abort. The crucial design point: transactions are atomic, so rollback is well-defined. Application threads holding mutexes don’t have rollback, which is why the same approach doesn’t work outside of databases.

8.3 MySQL InnoDB Deadlock Detection

Same approach as PostgreSQL, but more aggressive: InnoDB checks the wait-for graph on every lock acquisition, not periodically, so deadlocks are caught immediately. This is more expensive per request but reduces deadlock-detection latency to near-zero. Applicable because the lock manager is a centralized component with clean access to the graph.

8.4 Java’s `jstack` / Java Mission Control

The JDK includes jstack and JMC, which dump thread stack traces and automatically detect deadlocks among Java mutexes. When a deadlock is detected, the output explicitly says “Found 1 deadlock involving threads X and Y.” Used for post-mortem debugging of hung Java applications. This is offline detection — no runtime overhead, only triggered by an operator inspecting a dump.

8.5 Distributed Locking (Redis, Consul, etcd)

Distributed lock services (Redlock for Redis, Consul sessions, etcd leases) typically prevent permanent deadlock by leases / TTLs: a lock is held for a maximum duration; if the holder doesn’t refresh, the lock auto-releases. This converts what would be a deadlock into a temporary stall of duration ≤ TTL. Trade-off: a slow holder might lose the lock prematurely, causing correctness issues (the famous Martin Kleppmann critique of Redlock).

9. Pitfalls

9.1 Confusing Deadlock with Livelock

Deadlock: threads stuck waiting on each other; nobody is doing anything. Livelock: threads are doing things — repeatedly attempting, retrying, failing — but the system as a whole makes no progress. Two people trying to pass each other in a corridor, both stepping the same direction at the same time, repeatedly, is livelock. Random backoff (each thread waits a random delay before retrying) breaks livelock symmetry.

9.2 Confusing Deadlock with Starvation

Deadlock: a specific cycle is stuck forever. Starvation: a particular thread could run, but is repeatedly passed over by the scheduler. Deadlock involves all-or-nothing for the cycle; starvation is per-thread. See the discussion in Reader-Writer Problem §11.

9.3 The Double-Locked Self-Deadlock

A thread acquires a non-reentrant mutex, then accidentally tries to acquire it again (e.g., method A locks and calls method B, which also locks). The thread blocks waiting for itself. Single-thread deadlock. Fix: use a reentrant mutex (threading.RLock, std::recursive_mutex), or restructure to avoid re-entrance.

9.4 Static Lock Order, Dynamic Acquisition

Picking a global lock order works only if you can name all locks at compile time. For dynamic locks (one per object, allocated at runtime), the order must be defined dynamically — usually by lock identity (memory address, ID). Two locks from the same set must be acquired in identity-order. Java’s IdentityHashMap-based lock-tracking and C++‘s std::lock(m1, m2, ...) (which deadlock-free locks an arbitrary set) both address this.

9.5 Transitively Held Resources

Lock A is held by T1, which is computing some result and waiting for an HTTP response. The HTTP request handler is on T2, which is in a callback that wants to acquire lock A — transitively, through the HTTP layer, T2 is waiting on T1, and T1 is waiting on T2. This kind of deadlock is hard to spot because the wait chain crosses subsystems.

9.6 Distributed Deadlock

Across multiple nodes (databases, microservices), deadlock detection requires global coordination. Approaches:

Edge-chasing (path-pushing): each node forwards its wait-edges to dependent nodes; a cycle is detected when a node receives its own edge.
Probe-based: a probe message walks the wait-for graph; if the probe returns to its sender, deadlock.
Centralized detector: a single coordinator collects wait-edges from all nodes. Single point of failure.

Production distributed systems usually rely on timeouts (lease-based locking) instead of detection, accepting some incorrect aborts.

9.7 Lock-Free Doesn’t Mean Deadlock-Free in Practice

Lock-free algorithms guarantee system-wide progress (some thread always makes progress) but a specific thread can spin forever. This isn’t deadlock in the formal sense (no cycle) but it is a liveness failure. Wait-free algorithms are stronger: every thread makes progress in bounded steps. Confusing lock-free with deadlock-free is common.

9.8 Optimistic Concurrency Control Anomalies

Database systems using OCC (optimistic concurrency control) avoid traditional deadlock by deferring all conflict resolution to commit time. But two concurrent commits can both fail — repeated retries cause livelock in pathological workloads. Not a true deadlock, but the same observable symptom.

9.9 Banker’s “Maximum Demand” Hard to Estimate

The fundamental practicality blocker for Banker’s Algorithm: how do you know in advance that a thread will need at most M mutexes? In typed languages with effect systems (which don’t exist mainstream), this is automatic. In standard languages, it’s manual annotation, error-prone, and usually overestimated to be safe — overestimates make the safety check overly conservative, denying many genuinely-safe requests.

9.10 Detection Without Recovery

Detecting a deadlock and printing a message is not fixing it. The system is still stuck. Without recovery (kill, rollback, restart), detection only tells you what is wrong, not how to proceed. Plan recovery alongside detection.

10. Mermaid Diagram — Wait-For Graph and Cycle Detection

flowchart LR
    subgraph beforeDeadlock["Before deadlock — DAG"]
        T1a((T1)) -->|waits for| T2a((T2))
        T2a -->|waits for| T3a((T3))
        T3a -.idle.-> ne1[no wait]
    end

    subgraph atDeadlock["At deadlock — cycle"]
        T1b((T1)) -->|waits for| T2b((T2))
        T2b -->|waits for| T3b((T3))
        T3b -->|waits for| T1b
    end

    subgraph afterRecovery["After kill T2 — DAG again"]
        T1c((T1)) -.idle.-> ne2[no wait]
        T3c((T3)) -.idle.-> ne3[no wait]
        note["T2 was killed;<br/>resources released;<br/>system progresses"]
    end

    beforeDeadlock --> atDeadlock
    atDeadlock --> afterRecovery

What this diagram shows. Three snapshots of the wait-for graph during a deadlock episode. Initially (left), the graph is a DAG (directed acyclic graph): T1 waits for T2 waits for T3, but T3 itself is waiting for nothing — so T3 will eventually complete, release its resources, T2 will then complete, T1 will then complete. The system makes progress. In the middle, T3 has now requested a resource held by T1, completing the cycle: T1 → T2 → T3 → T1. No leaf in the wait-for graph, no thread can complete, system is stuck. After recovery (right), the deadlock-detection algorithm has chosen T2 as the victim and killed it; T2 releases everything it held; T1 and T3 are now both able to make progress (their waits resolved). The visual takeaway: deadlock = cycle in the wait-for graph; recovery = remove a node from the cycle; detection = run Depth-First Search for cycle on this graph.

11. Common Interview Problems

Problem	Difficulty	Notes
State the four Coffman conditions	Easy	Often a warm-up question
Identify the deadlock in a code snippet	Medium	Two threads, two mutexes, opposite acquisition orders
Fix the deadlock with resource hierarchy	Medium	Standard answer; write the canonical-order code
Implement wait-for-graph cycle detection	Medium-Hard	DFS with three colors
Banker’s Algorithm — given state, is it safe?	Medium	Coursework standard; uncommon in modern interviews
Banker’s Algorithm — should we grant this request?	Medium	Compose safety check with pretend-grant
Distinguish deadlock, livelock, starvation	Conceptual	Common compound question
Design a distributed locking system	System-design	Lease + retry vs traditional locking
Database transaction deadlock	DB-flavored	Detection + rollback victim
Dining Philosophers solutions, each breaking a different condition	Conceptual	Standard teaching

12. Open Questions

Why doesn’t every modern programming language enforce canonical lock order via the type system? Some do (Rust’s borrow checker eliminates many lock-related bugs but doesn’t force an order); most don’t because forcing an order is hard to reason about for users. Annotations like Clang’s -Wthread-safety analyzer come close.
How does deadlock detection scale to thousands of threads? The wait-for graph can have O(n²) edges; cycle detection is O(V+E). For very large n, periodic full-graph search is expensive. Incremental detection (check only the cycle around a newly-added edge) is cheaper but more complex.
What’s the right deadlock model for async / cooperative concurrency (Python asyncio, JavaScript Promises)? There are no preempted resources, but circular awaits do occur. The condition mapping shifts; canonical “lock order” doesn’t have a clear analog.
Are there learned deadlock-prediction techniques (machine-learning over thread behavior to predict deadlocks before they form)? Verify with literature search; this is an active area in OS research circa 2020+.

13. See Also

Dining Philosophers — sibling concurrency teaching problem; canonical illustration of all four conditions
Mutex vs Semaphore vs Condition Variable — primitives whose misuse causes deadlock
Producer-Consumer — sibling synchronization classic; can deadlock if consumer dies
Reader-Writer Problem — sibling problem with starvation, related to liveness analysis
Depth-First Search — used for cycle detection in the wait-for graph
Topological Sort — equivalent formulation: a DAG has a topological order iff no cycle exists
Mutability and Aliasing Bugs — sibling concurrency pitfall
Off-By-One Errors — Survival Guide — sibling pitfalls reference card
Big-O Notation — for cost analysis of detection vs prevention
Hash Table — used to maintain wait-for graph adjacency lists
SWE Interview Preparation MOC

vault

Explorer

Deadlock Detection and Avoidance

Deadlock Detection and Avoidance

1. Intuition — A Standoff at the Door

2. Tiny Worked Example — Two Threads, Two Locks

3. The Four Coffman Conditions (Coffman, Elphick, Shoshani 1971)

3.1 Mutual Exclusion

3.2 Hold and Wait

3.3 No Preemption

3.4 Circular Wait

4. Strategies for Handling Deadlock

4.1 Strategy 1 — Detection and Recovery

4.2 Strategy 2 — Prevention

4.3 Strategy 3 — Avoidance (Banker’s Algorithm)

4.4 Strategy 4 — Ignore (the Ostrich Algorithm)

5. Pseudocode — Wait-For Graph Cycle Detection

6. Python Demonstration — Simulating Deadlock Detection

7. Python — Banker’s Algorithm

8. Real-World Examples

8.1 Linux Kernel lockdep

8.2 PostgreSQL Transaction Deadlock Detection

8.3 MySQL InnoDB Deadlock Detection

8.4 Java’s jstack / Java Mission Control

8.5 Distributed Locking (Redis, Consul, etcd)

9. Pitfalls

9.1 Confusing Deadlock with Livelock

9.2 Confusing Deadlock with Starvation

9.3 The Double-Locked Self-Deadlock

9.4 Static Lock Order, Dynamic Acquisition

9.5 Transitively Held Resources

9.6 Distributed Deadlock

9.7 Lock-Free Doesn’t Mean Deadlock-Free in Practice

9.8 Optimistic Concurrency Control Anomalies

9.9 Banker’s “Maximum Demand” Hard to Estimate

9.10 Detection Without Recovery

10. Mermaid Diagram — Wait-For Graph and Cycle Detection

11. Common Interview Problems

12. Open Questions

13. See Also

Graph View

Table of Contents

Backlinks

8.1 Linux Kernel `lockdep`

8.4 Java’s `jstack` / Java Mission Control