Deadlock: Definition and Conditions

A deadlock is a situation in which every member of a set of processes (or threads) is blocked, waiting for an event — typically release of a resource — that only another member of the same set can cause. Because every member is blocked, no one can ever trigger the needed event, and the entire set is stuck permanently. This is distinct from a process merely waiting: waiting is normal and temporary, while deadlock is a structural impossibility of progress. Deadlock analysis concerns reusable resources: resources like locks, memory, CPUs, or file handles that a process acquires, uses, and eventually releases for reuse (as opposed to consumable resources like messages, which are produced and consumed once). A process interacting with a reusable resource follows a lifecycle: request the resource, use it, then release it. Deadlock arises from the interaction of multiple processes each following this lifecycle over multiple resources, where the order of acquisition creates a cyclic dependency. In 1971, E. G. Coffman, M. J. Elphick, and A. Shoshani identified four conditions that must all hold simultaneously for deadlock to be possible. These are individually necessary and jointly sufficient — meaning a deadlock cannot exist unless all four hold, and if all four hold along a cycle of waiting processes, deadlock exists. They give us a precise vocabulary for classifying and preventing deadlocks, foreshadowing the whole family of techniques in Deadlock Prevention and Avoidance.

The four Coffman conditions

1. Mutual Exclusion — At least one resource must be held in a non-shareable mode: only one process can use it at a time. (Read-only, shareable resources cannot participate in a deadlock cycle, since a process never needs to wait to acquire them.) 2. Hold and Wait — A process must be holding at least one resource while simultaneously waiting to acquire additional resources currently held by other processes. It does not release what it already has while it waits. 3. No Preemption — Resources cannot be forcibly taken away from a process. A resource can only be released voluntarily by the process holding it, after it has finished using it. 4. Circular Wait — There must exist a set of waiting processes $\{P_0, P_1, \dots, P_n\}$ such that $P_0$ waits for a resource held by $P_1$, $P_1$ waits for a resource held by $P_2$, ..., and $P_n$ waits for a resource held by $P_0$. These four conditions are not independent design choices you can mix and match arbitrarily — they are a derivation: circular wait cannot occur without hold-and-wait (a process in the cycle must be holding something while waiting), hold-and-wait is meaningless without mutual exclusion (if resources could be shared freely, there would be nothing to "wait" for), and the whole cycle would resolve itself if preemption were allowed (the system could just yank a resource from one process to break the cycle). This is why eliminating any single one of the four is a valid deadlock-prevention strategy, foreshadowed here and developed fully under Deadlock Prevention and Avoidance.

The resource-allocation graph (RAG)

A resource-allocation graph is a directed graph $G = (V, E)$ used to represent the exact state of resource requests and allocations at an instant in time.

• $V = P \cup R$, where $P = \{P_1, \ldots, P_n\}$ is the set of processes and $R = \{R_1, \ldots, R_m\}$ is the set of resource types.
• A request edge $P_i \rightarrow R_j$ means process $P_i$ has requested an instance of resource $R_j$ and is waiting.
• An assignment edge $R_j \rightarrow P_i$ means an instance of resource $R_j$ has been allocated to $P_i$.
• Each resource type $R_j$ is drawn with a number of dots equal to its instance count.

Given this graph, two structural facts govern deadlock:

• If the graph contains no cycle, there is no deadlock. (Necessity of a cycle.)
• If every resource type in the graph has exactly one instance, then a cycle is both necessary and sufficient for deadlock.
• If some resource type has multiple instances, a cycle is necessary but not sufficient — the cycle may be broken by another process outside the cycle eventually releasing a resource that satisfies a pending request.

Cycle detection algorithm

Detecting deadlock (under the single-instance-per-type simplification, or more generally checking the necessary condition) reduces to cycle detection in a directed graph, solvable by depth-first search in linear time. ``` function HAS_CYCLE(Graph G): color[v] ← WHITE for all v in V(G) # unvisited for each vertex v in V(G): if color[v] == WHITE: if DFS_VISIT(v): return true # cycle found return false function DFS_VISIT(v): color[v] ← GRAY # v is on the current recursion stack for each edge (v, u) in E(G): if color[u] == GRAY: return true # back edge -> cycle if color[u] == WHITE: if DFS_VISIT(u): return true color[v] ← BLACK # done with v, remove from stack return false ``` For the multi-instance case, a cycle alone is inconclusive; full deadlock detection requires a more general algorithm (structurally similar to the Banker's Algorithm's safety check) that tries to find a sequence of processes that can all finish given available resources — this is developed under later deadlock-detection material, but the graph model here is exactly what that algorithm consumes as input. ``` function MULTI_INSTANCE_DEADLOCK_CHECK(n processes, m resource types):

# Available[j] = free instances of resource R_j

# Allocation[i][j] = instances of R_j held by P_i

# Request[i][j] = instances of R_j currently requested by P_i Work ← copy of Available Finish[i] ← false for all i

# A process with zero current allocation trivially cannot be deadlocked for i in 1..n: if Allocation[i] is all zeros: Finish[i] ← true changed ← true while changed: changed ← false for i in 1..n: if not Finish[i] and Request[i] <= Work: # elementwise Work ← Work + Allocation[i] Finish[i] ← true changed ← true deadlocked ← { P_i : Finish[i] == false } return deadlocked ```

Time complexity of cycle detection. DFS-based cycle detection visits every vertex once and traverses every edge once, giving $O(|V| + |E|)$ time, where $|V| = |P| + |R|$ and $|E|$ is the number of request/assignment edges. This is optimal: any correct algorithm must at least inspect every edge once, since omitting an edge could hide a cycle.

Space complexity. $O(|V|)$ for the color array and the recursion stack in the worst case (a graph that is one long path/cycle), plus $O(|V| + |E|)$ for the adjacency-list representation of the graph itself.

Correctness of DFS cycle detection. The invariant is: a vertex is colored GRAY exactly while it is an ancestor of the current DFS call on the recursion stack, and BLACK once it and all its descendants are fully explored. A back edge — an edge from the current vertex to a GRAY vertex — exists if and only if there is a path from that GRAY ancestor down to the current vertex and an edge back up to it, which is precisely a cycle. Standard graph theory (via DFS forest classification of tree/back/forward/cross edges) proves: a directed graph has a cycle iff a DFS forest of it contains a back edge. Hence `HAS_CYCLE` is correct.

Correctness of "cycle $\Rightarrow$ deadlock" (single instance case). Suppose the RAG has a cycle $P_1 \to R_1 \to P_2 \to R_2 \to \cdots \to P_k \to R_k \to P_1$ and every $R_i$ has exactly one instance. Each $R_i$ is already allocated to $P_{i+1}$ (that's why $R_i \to P_{i+1}$ is an edge), so $P_i$'s request for $R_i$ can never be satisfied unless $P_{i+1}$ releases it — but $P_{i+1}$ is itself blocked waiting on $R_{i+1}$, held by $P_{i+2}$, and so on around the cycle. No process in the cycle can proceed, so none can release anything: this is exactly deadlock. The single-instance assumption is essential — it guarantees the resource $P_i$ needs is entirely consumed by the very process blocking it, with no alternate instance available.

Why a cycle is not sufficient with multiple instances. If $R_j$ has, say, 3 instances, a request edge $P_i \to R_j$ can be satisfied by any of the 3 instances, including one held by a process outside the cycle. That outside process may finish and release its instance, breaking the deadlock even though the cycle persists in the graph. Hence the multi-instance detection algorithm above must simulate whether some execution order lets all processes finish (the `Work`/`Finish` simulation), not merely check for a cycle.

Honesty about tradeoffs. Cycle detection tells you a deadlock is possible or, in the single-instance case, definite; it does not tell you when it will occur, nor does it prevent it. Building a full RAG and re-checking it on every request is straightforward but can be costly if done naively on every single operation in a busy system — real systems trade off between checking eagerly (avoidance, higher runtime cost, discussed in the Banker's Algorithm) and checking periodically or only when suspicion is triggered (detection, cheaper but allows deadlocks to persist for a while).

Consider three processes $P_1, P_2, P_3$ and three single-instance resources $R_1, R_2, R_3$ (e.g., three distinct locks in a database engine), with the following sequence of events:

Tracing `HAS_CYCLE` at step 6, starting DFS from $P_1$: 1. Color $P_1$ GRAY. Follow edge $P_1 \to R_2$. 2. Color $R_2$ GRAY. Follow edge $R_2 \to P_2$. 3. Color $P_2$ GRAY. Follow edge $P_2 \to R_3$. 4. Color $R_3$ GRAY. Follow edge $R_3 \to P_3$. 5. Color $P_3$ GRAY. Follow edge $P_3 \to R_1$. 6. Color $R_1$ GRAY. Follow edge $R_1 \to P_1$. 7. $P_1$ is GRAY (already on the stack) $\Rightarrow$ back edge detected $\Rightarrow$ `HAS_CYCLE` returns true. Checking the four Coffman conditions confirms this is genuine deadlock, not just a cycle in a diagram:

• Mutual exclusion: yes, each $R_i$ is a single, non-shareable instance (e.g., an exclusive database lock).
• Hold and wait: yes, e.g., $P_1$ holds $R_1$ while waiting for $R_2$.
• No preemption: yes, assume the system never revokes a lock from a running transaction.
• Circular wait: yes, exactly the cycle traced above.

All four hold, the cycle is confirmed by DFS in $O(|V|+|E|) = O(6 + 6) = O(12)$ work, and since every resource has a single instance, the cycle is the deadlock — $P_1, P_2, P_3$ will wait forever. This is structurally identical to the classic circular lock-ordering bug: $\text{Thread 1: lock}(A)\to\text{lock}(B)$ while $\text{Thread 2: lock}(B)\to\text{lock}(A)$, the two-process special case of the same cycle. Now contrast with a multi-instance twist: suppose $R_1$ actually has 2 instances, one held by $P_1$ and a second held by some $P_4$ outside the cycle. The RAG still shows the same cycle among $P_1, P_2, P_3$, but $P_3$'s request for $R_1$ can be satisfied the moment $P_4$ finishes and releases its instance — no deadlock actually occurs, even though `HAS_CYCLE` still reports true. This is exactly why the multi-instance simulation algorithm, not bare cycle detection, is required in general.

Deadlock reasoning underlies the design of virtually every multi-threaded and multi-process system. Database management systems (PostgreSQL, MySQL, Oracle) maintain internal wait-for graphs, a variant of the resource-allocation graph restricted to processes, and periodically run cycle detection to identify and abort a victim transaction. Operating-system kernels apply strict lock ordering conventions across subsystems (e.g., always acquire the scheduler lock before the memory-manager lock) specifically to eliminate the circular-wait condition by construction. Distributed systems (e.g., distributed lock managers in Google's Chubby or Apache ZooKeeper-based coordination) generalize the RAG across machines, where detecting cycles is harder because no single node sees the whole graph, motivating specialized distributed deadlock-detection protocols. Compilers and static analyzers for concurrent code (e.g., Rust's borrow checker influences, or tools like ThreadSanitizer's lock-order analyzers) attempt to statically rule out circular-wait patterns before deployment. All of this machinery — prevention strategies that eliminate one Coffman condition, avoidance strategies like the Banker's Algorithm that never allow an unsafe state, and detection strategies that periodically scan the RAG — builds directly on the definitions and graph model developed here, alongside the related but distinct hazards of Starvation and Livelock.

Ask the tutor: How does the multi-instance deadlock-detection algorithm's Work/Finish simulation differ in intent from the Banker's Algorithm's safety check?