Deadlock Prevention, Avoidance, and Detection

A deadlock is a state in which a set of processes are each waiting for a resource held by another process in the same set, so that no process can ever proceed. Formally, deadlock is possible only when four conditions hold simultaneously: mutual exclusion (resources are non-shareable), hold-and-wait (a process holds resources while requesting more), no preemption (a resource cannot be forcibly taken from its holder), and circular wait (a cycle of processes each waiting on the next). These are necessary conditions — deadlock cannot occur without all four — but together, in the presence of a cycle, they are also sufficient. This is the exact fact every strategy below exploits. The three families of strategy differ in when they act and how much information they require. Prevention acts at design time: the system is engineered so that at least one Coffman condition can never arise, regardless of process behavior. Avoidance acts at request time: the system knows, in advance, the maximum resources each process might ever need, and uses that knowledge to simulate the future before granting any request, refusing requests that would lead to an unsafe state. Detection and recovery acts after the fact: requests are granted greedily with no look-ahead, and periodically (or on suspicion of stall) the system runs a graph algorithm to check whether a deadlock has actually formed, then intervenes. A fourth stance — ignore it (the "ostrich algorithm") — is common in general-purpose operating systems like a plain Unix kernel, where deadlocks are rare enough in practice that the cost of prevention/avoidance/detection outweighs the cost of an occasional reboot. This is a legitimate engineering tradeoff, not a failure to understand the problem; it is why deadlock handling is emphasized far more in database systems and real-time/embedded kernels, where correctness guarantees matter more than average-case throughput.

Prevention: negate one Coffman condition

Each of the four conditions can be attacked directly.

Attack mutual exclusion. Make resources shareable where possible (e.g., read-only files, spooling for printers so processes never wait on the physical device itself). This is limited — some resources (a write lock, a CPU core) are inherently exclusive — but wherever it applies it eliminates deadlock on that resource entirely.

Attack hold-and-wait. Require a process to request all resources it will ever need before execution begins, or require it to release everything it holds before requesting more. Either rule structurally prevents a process from holding some resources while blocking on others.

Attack no preemption. If a process holding resources requests another that is unavailable, forcibly preempt (take away) its currently held resources, or preempt from other waiting processes. The state is later restored, or the process is rolled back. This works well for resources whose state is easy to save and restore (CPU registers, memory pages) and poorly for resources that are not (a partially written file, a printer mid-job).

Attack circular wait. Impose a total (or partial) ordering on all resource types, and require every process to request resources only in strictly increasing order of this ranking. This is by far the most widely used prevention technique in real systems, because it is cheap and composable. ```pseudocode // Resource ordering (attacks circular wait) // F: ResourceType -> Integer (a fixed total order, chosen once for the whole system) function request(process P, resource R): if R.rank <= P.highest_held_rank: // Would create a request pointing "backward" in the order error("must request in increasing rank order") acquire(R) P.highest_held_rank = R.rank // Correctness sketch: // Suppose a cycle P1 -> P2 -> ... -> Pk -> P1 existed, where Pi -> Pi+1 // means "Pi holds a resource that Pi+1 is waiting for." // Each edge Pi -> Pi+1 implies rank(resource held by Pi) < rank(resource requested by Pi+1) // which Pi+1 must hold before requesting further resources of higher rank, ultimately // requiring rank(held by Pi+1) < rank(requested from Pi+2) ... and so on around the cycle. // Following the cycle all the way around forces // rank_1 < rank_2 < ... < rank_k < rank_1 // a strict cycle of real numbers, which is impossible. Hence no cycle, hence no deadlock. ``` The proof above is the essential reasoning: a total order on resource acquisition forbids a cycle in the wait-for relation because cycles would require ranks to increase strictly around a loop, which is impossible for real numbers. This is why resource ordering is the workhorse technique in lock-heavy code (e.g., always lock the object with the smaller memory address first).

Avoidance: simulate before granting

Avoidance is more permissive than prevention: it does not forbid hold-and-wait or circular structure outright. Instead, each process declares in advance its maximum claim for each resource type, and the system dynamically checks, before granting any request, whether granting it could ever lead to a state from which no sequence of future allocations can satisfy every process. Such a bad state is called unsafe; a state from which some ordering of process completions is guaranteed to exist is called safe. ```pseudocode // Safety check core idea (generalized; specialized fully in the Banker's Algorithm) function isSafe(allocation, available, maxClaim): work = copy(available) finish = [false] n while true: progressed = false for each process Pi with finish[Pi] == false: need_i = maxClaim[Pi] - allocation[Pi] if need_i <= work: // component-wise work = work + allocation[Pi] // simulate Pi finishing, releasing all it holds finish[Pi] = true progressed = true if all(finish): return true // safe: this completion order exists if not progressed: return false // unsafe: no process could finish with current 'work' ``` Before actually granting any request, the system tentatively grants it, runs `isSafe`, and rolls back the tentative grant if the result is unsafe — the request is instead deferred until it would* be safe. This is exactly the mechanism used in the Banker's Algorithm, which specializes this general safety check to multiple resource types with integer counts, and is the natural next topic after mastering this idea.

Detection and recovery: catch it after it happens

Detection abandons look-ahead. Requests are granted whenever resources are free, with no safety check. Periodically (or when a process seems to be waiting too long) the system builds a graph and searches for a cycle. For single-instance resource types (each resource type has exactly one unit — one lock, one file handle), build a wait-for graph: an edge `Pi -> Pj` means `Pi` is waiting for a resource currently held by `Pj`. Deadlock exists exactly when this graph has a cycle. ```pseudocode // Deadlock detection, single-instance resources function detectDeadlock(waitForGraph): visited = {}, inStack = {} for each node P in waitForGraph: if P not in visited: if dfs(P, visited, inStack, waitForGraph): return true // cycle found => deadlock return false function dfs(P, visited, inStack, graph): visited[P] = true inStack[P] = true for each neighbor Q of P in graph: if Q in inStack: return true // back edge => cycle if Q not in visited: if dfs(Q, visited, inStack, graph): return true inStack[P] = false return false ``` For multiple-instance resource types, the wait-for graph is insufficient (a cycle can exist without deadlock, if enough spare instances exist to eventually satisfy everyone). Instead run an algorithm structurally identical to the safety check above, but using each process's actual current request instead of its maximum claim: ```pseudocode // Deadlock detection, multiple-instance resources function detect(allocation, request, available): work = copy(available) finish = [false] * n for each process Pi: finish[Pi] = (allocation[Pi] == 0) // processes holding nothing can't be stuck while true: progressed = false for each process Pi with finish[Pi] == false: if request[Pi] <= work: work = work + allocation[Pi] finish[Pi] = true progressed = true if not progressed: break deadlocked = [Pi for Pi where finish[Pi] == false] return deadlocked // empty list means no deadlock ``` Once deadlocked processes are identified, recovery proceeds by process termination (kill all deadlocked processes at once, or kill them one at a time, re-running detection after each kill until the cycle is broken) or by resource preemption (forcibly take a resource from one process, roll it back to a safe checkpoint, and give the resource to another), being careful to avoid starvation by not always picking the same victim.

Prevention (resource ordering). Each `request` call does O(1) work (a comparison and an update). No global search is ever needed at runtime, because the correctness argument is a static invariant proven once, at design time, over the fixed total order. This is the cheapest of all three strategies at runtime, but it is the least flexible: it requires all resource types to be known and ranked in advance, and it can force processes to acquire resources earlier than needed, hurting concurrency (a form of artificial hold-and-wait even while structurally preventing cyclic hold-and-wait).

Avoidance (safety checking). With $n$ processes and $m$ resource types, one `isSafe` call is $O(n^2 m)$ in the worst case: the outer `while` loop runs at most $n$ times (each iteration finishes at least one process, or the loop terminates), and each iteration scans all $n$ processes comparing vectors of length $m$. Since a safety check is run on every resource request, the amortized cost dominates system throughput far more than prevention's O(1) check. Correctness follows directly from the definition of a safe state: `isSafe` returns true exactly when a completion ordering exists, because the simulation greedily finds some valid order if one exists — if some process's need is satisfiable, granting it and adding its resources back to `work` only increases what is available for the rest, so greedily satisfying any eligible process is always a safe choice (an exchange argument: any valid completion order can be reordered to defer no eligible process without breaking validity).

Detection (cycle finding). Building and searching the wait-for graph for a cycle is $O(V + E)$ using depth-first search, where $V$ is the number of processes and $E$ the number of wait-for edges — standard graph cycle detection. The multiple-instance detection algorithm has the same $O(n^2 m)$ shape as the safety check, since it is structurally the same greedy simulation, this time against actual requests rather than maximum claims. Correctness: the algorithm finds a set of processes that can never be satisfied because at every step it only marks a process "finished" when its exact current request is satisfiable from `work`; any process left unmarked when no further progress is possible is, by definition, permanently blocked given the current allocation, because `work` only grows (never shrinks) across iterations, so if it could not satisfy a process now, it never will without external intervention.

Honest tradeoffs. Prevention costs concurrency (over-conservative acquisition) for free runtime checks. Avoidance costs runtime CPU (repeated $O(n^2 m)$ checks) and requires each process to declare a maximum claim in advance — information that is often unavailable or overestimated, again hurting concurrency. Detection costs nothing on the common path but requires a recovery mechanism (rollback, checkpoint, or kill) that can be expensive or lossy, and the frequency of running detection is itself a tuning knob: too rare and processes stall a long time undetected, too frequent and detection overhead dominates.

Consider a system with three resource types, A (10 instances), B (5 instances), C (7 instances), and three processes with the following current allocation and outstanding request (not maximum claim — this is a detection scenario, not avoidance):

Total allocated: A = 0+2+3 = 5, B = 1+0+0 = 1, C = 0+0+3 = 3. Available = Total − Allocated = (10−5, 5−1, 7−3) = (5, 4, 4). Run `detect`:

• Initialize `work = (5,4,4)`. `finish[P0] = false` (holds B), but its request is (0,0,0) ≤ work trivially — actually mark eligibility by request, not allocation: P0's allocation is nonzero, but that does not block finishing.
• Check P0: request (0,0,0) ≤ (5,4,4)? Yes. Finish P0, `work += allocation[P0] = (0,1,0)` → `work = (5,5,4)`.
• Check P1: request (2,0,2) ≤ (5,5,4)? Yes. Finish P1, `work += (2,0,0)` → `work = (7,5,4)`.
• Check P2: request (0,0,0) ≤ (7,5,4)? Yes. Finish P2, `work += (3,0,3)` → `work = (10,5,7)`.
• All finished. `deadlocked = []` — no deadlock, despite P1 holding resources and requesting more.

Now suppose P2's request changes to (0, 0, 1) — it now also wants one more unit of C — while everything else is unchanged, and additionally P0's allocation is revised to (0, 1, 0) with request (0,0,0) as before, but Available is recomputed with one less spare C: Available = (5, 4, 3).

• Check P0: request (0,0,0) ≤ (5,4,3)? Yes. Finish. `work = (5,5,3)`.
• Check P1: request (2,0,2) ≤ (5,5,3)? No (needs 2 units of C, only 3 available but P1 also needs the 2 A's fine — wait: 2 ≤ 3 in C is true). Recheck carefully: (2,0,2) ≤ (5,5,3) is true component-wise. Finish P1. `work += (2,0,0)` → `work = (7,5,3)`.
• Check P2: request (0,0,1) ≤ (7,5,3)? Yes. Finish. `work += (3,0,3)` → `work=(10,5,6)`.
• Still no deadlock.

To actually force deadlock in this small system, shrink availability further: suppose instead Available starts at (0, 0, 0) because all instances are allocated, and P1's request is (2,0,2) while no other process can proceed. Then `work=(0,0,0)`; P0's request (0,0,0) ≤ (0,0,0) — P0 finishes, releasing (0,1,0), `work=(0,1,0)`; P1's request (2,0,2) ≤ (0,1,0)? No. P2's request (0,0,0) ≤ (0,1,0)? Yes, P2 finishes releasing (3,0,3), `work=(3,1,3)`. Now recheck P1: (2,0,2) ≤ (3,1,3)? Yes — P1 finishes too. Still no deadlock: this illustrates that with only three processes and modest requests, a genuine deadlock needs a request that no release can ever satisfy, e.g., if P1 requested (2,0,2) but total C instances were only 3 and all 3 were permanently held by P1 and P2 together with none releasable because P2's request itself depends on a resource only P1 holds — a true circular dependency, confirming why the algorithm's "no progress possible" branch, not merely a numeric shortfall, is the actual deadlock signature.

The theory of deadlock was formalized as operating systems began supporting true multiprogramming, when multiple jobs competing for tape drives, memory, and card readers made cyclic waits a real operational hazard rather than a theoretical curiosity. The formal statement of the four necessary conditions is credited to Edward G. Coffman Jr., whose 1971 survey with Elphick and Shoshani crystallized decades of scattered operating-system folklore into a rigorous framework still taught today.

Relational database engines run continuous or periodic deadlock detection on their internal lock managers, aborting the "cheapest" transaction (by rollback cost or age) when a cycle is found — this is why an application can receive a serialization/deadlock error and must retry the transaction. Kernel-level lock ordering, using techniques identical to the resource-ordering prevention scheme above, is enforced in production operating system kernels (Linux's lockdep subsystem dynamically verifies that no code path violates a global lock acquisition order, catching potential deadlocks even when they have not yet occurred). Distributed systems extend detection across machines with edge-chasing or path-pushing protocols, since no single node can see the whole wait-for graph. Real-time and embedded systems, where an unresolvable freeze can be safety-critical, more often lean on prevention (e.g., the priority ceiling protocol, an extension of resource ordering combined with priority inheritance) because it offers deadlock-freedom as a static, provable guarantee rather than a probabilistic runtime check. Understanding these three strategies — and the safety-state reasoning that underlies avoidance — is exactly the prerequisite for the Banker's Algorithm, the most detailed and historically important instance of the avoidance approach.

Ask the tutor: How exactly does the Banker's Algorithm's request-handling protocol use this safety check to decide whether to grant or defer a single incoming resource request?