Deadlock detection and recovery
Deadlock detection and recovery: how an OS finds processes stuck waiting for each other and how it recovers (algorithms, proofs, examples).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Key ideas
Begin with definitions and basic facts from first principles.
Deadlock — A set of two or more processes are in a deadlock state when each process in the set is waiting for an event (usually release of a resource) that only another process in the set can cause. (Assumes processes do not spontaneously produce required resources.)
The four Coffman necessary conditions for deadlock (all must hold simultaneously):
- Mutual exclusion — at least one resource must be non-sharable (only one process can use it at a time).
- Hold and wait — a process holds at least one resource and is waiting to acquire additional resources.
- No preemption — a resource cannot be forcibly removed from a process; it is released only voluntarily by the holder.
- Circular wait — there exists a set {P0, P1, …, Pk} of processes such that P0 waits for a resource held by P1, P1 waits for a resource held by P2, …, Pk waits for a resource held by P0. These are necessary conditions: if deadlock exists, all four hold. (They are not individually sufficient.)
Resource-allocation graph (RAG) — a directed bipartite graph with process nodes (Pi) and resource nodes (Rj). Draw an arrow from Pi to Rj if Pi has requested an instance of Rj (request edge). Draw an arrow from Rj to Pi if a particular instance of Rj is allocated to Pi (assignment edge). For resources with multiple instances, label Rj with its instance count (k) or represent k identical unit nodes.
- Exact drawing instructions for exam diagrams: draw circles labelled P0, P1, … for processes; draw squares or boxes labelled R0, R1, … for resources. For each assignment edge label the arrow Rj → Pi with the number of instances allocated (or draw that many unit nodes). For each request edge Pi → Rj draw a single arrow and label if the request is for more than one unit.
Single-instance vs multi-instance rules:
- For single-instance resources (each Rj has at most one instance): a cycle in the RAG is both necessary and sufficient for deadlock. In an exam diagram, a cycle appears as alternating Pi → Rj → Pk → ... → Pi.
- For multiple-instance resources: a cycle in the RAG is necessary but not sufficient for deadlock. A cycle may exist but resources might still be allocated so that at least one process can finish.
Wait-for graph (WFG) — derived graph with only process nodes. There is an edge Pi → Pj if Pi is waiting for a resource currently held by Pj. The WFG simplifies cycle checks for single-instance resource types: any cycle in the WFG implies deadlock, and absence of a cycle implies no deadlock. For multiple-instance resource types, simple WFG cycle detection is not sufficient; use the matrix-based detection algorithm.
Deadlock detection algorithms:
- Single-instance: detect cycles in RAG or WFG. Cycle detection can be done by depth-first search (DFS) on the directed graph — standard graph cycle detection.
- Multiple-instances (vector/matrix method): maintain three structures: Available (vector), Allocation (n × m matrix), Request (n × m matrix). Algorithm (often called the deadlock-detection algorithm):
- Initialize Work = Available. Set Finish[i] = true for all i with Allocation[i] = 0; set Finish[i] = false for all other i.
- If there exists a process i with Finish[i] = false and Request[i] ≤ Work (vector comparison), then set Work = Work + Allocation[i], Finish[i] = true, and repeat.
- If no such process exists, the processes with Finish[i] = false are deadlocked. In practice, an OS runs the detection algorithm periodically or when a request cannot be immediately granted; the frequency trades off overhead (about O(n^2 m) per run, for n processes and m resource types) versus time-to-detect.
- Correctness sketch: If Request[i] ≤ Work then i can finish with current available resources; when it finishes it releases its Allocation to Work, enabling other processes; repeated marking is like simulating safe completions. If a process cannot be marked, there is no sequence of completions starting from Available that allows it to finish — therefore it participates in a deadlock set.
Recovery methods (when detection finds deadlock):
- Process aborts: abort one or more processes (all the way or partially rollback to a safe checkpoint) until deadlock breaks. Choose victim(s) by cost (priority, restart cost, resources used, runtime).
- Resource preemption: take resources from some processes and give to others; must avoid livelock and must handle rollback. Preemption requires checkpointing or ability to restart work, and is only feasible for preemptible resources (e.g., you cannot preempt a printer mid-job).
- Rollback and checkpoint: roll back some processes to earlier check-pointed states so they hold fewer resources.
- Combined policies and heuristics are common; always mention starvation prevention (increase victim cost over time so same process is not repeatedly chosen).
Formulas
Total = Available + Σ Allocation — Total is the vector of total instances per resource type; Available is currently free instances; Allocation is sum of columns of the allocation matrix. Units: instances of resource j (count, dimensionless), applies when accounting resources.
Request_i ≤ Available — vector comparison meaning for every resource j, Request_i[j] ≤ Available[j]. Applies in the detection algorithm when deciding if process i can complete.
Work_0 = Available — initial Work vector in the multiple-instance detection algorithm; units: resource instances.
Work_{k+1} = Work_k + Allocation[i] when process i finishes and releases its allocated resources. Units: resource instances.
(There are no physical SI units here; resource counts are integer instance counts.)
Worked examples
Example 1 — single-instance RAG cycle (diagram + conclusion) Question (theory diagram): Draw the RAG and show if deadlock exists. Data: Processes P0, P1, P2. Resources R0, R1, R2 — single instance each. Allocations: R0 → P0, R1 → P1, R2 → P2. Requests: P0 → R1 (P0 waits for R1), P1 → R2, P2 → R0. Steps (exam model answer):
- Draw three circles for P0, P1, P2. Draw three squares for R0, R1, R2.
- Draw assignment edges: R0 → P0, R1 → P1, R2 → P2 (label each arrow "allocated").
- Draw request edges: P0 → R1, P1 → R2, P2 → R0.
- The graph contains cycle P0 → R1 → P1 → R2 → P2 → R0 → P0. Because resources are single-instance, a cycle is sufficient for deadlock. Answer: The three processes P0, P1 and P2 are deadlocked. Bold final: Deadlock: {P0, P1, P2}.
Example 2 — multi-instance detection algorithm (matrix method) Question (numerical): Use the detection algorithm to find deadlocked processes. Data (4 processes, 3 resource types with instances):
- Total = [3, 3, 2] (resource R0 has 3 instances, R1 has 3, R2 has 2)
- Allocation matrix (rows P0..P3): P0: [0, 1, 0] P1: [2, 0, 0] P2: [0, 0, 1] P3: [1, 0, 1]
- Request (current outstanding additional requests) matrix: P0: [0, 1, 0] P1: [1, 0, 0] P2: [0, 0, 0] P3: [0, 1, 0] Steps:
- Compute Available = Total − Σ Allocation column-wise = [3−(0+2+0+1), 3−(1+0+0+0), 2−(0+0+1+1)] = [0, 2, 0].
- Set Work = Available = [0,2,0]; Finish[i]=false for all.
- Find a process with Finish=false and Request ≤ Work.
- P0 Request [0,1,0] ≤ [0,2,0] → yes. Mark Finish[0]=true, Work = Work + Allocation[0] = [0,2,0] + [0,1,0] = [0,3,0].
- Continue: P2 Request [0,0,0] ≤ Work → mark Finish[2]=true, Work = [0,3,0] + Allocation[2] ([0,0,1]) = [0,3,1].
- P1 Request [1,0,0] ≤ Work ([0,3,1])? No (1 > 0 in R0). P3 Request [0,1,0] ≤ Work → mark Finish[3]=true, Work = [0,3,1] + Allocation[3] ([1,0,1]) = [1,3,2].
- Now P1 Request [1,0,0] ≤ Work [1,3,2] → mark Finish[1]=true; Work = Work + Allocation[1] = [1,3,2] + [2,0,0] = [3,3,2].
- All Finish[i] are true → no deadlock. Answer: No deadlock (all processes can complete in the order P0, P2, P3, P1). (Show the stepwise Work updates as above in your answer.)
(If the algorithm finishes with some Finish[i]=false, those processes are deadlocked.)
Common mistakes
- Running the Banker's algorithm (safety test) instead of the deadlock detection algorithm; they are related but used for different goals (avoidance vs detection).
- During matrix detection, using Allocation instead of Request or mixing up Available and Work, and confusing the Request matrix with Banker's Need matrix.
- Not stating assumptions (e.g., resources are indivisible units, processes do not create resources).
For your exam
Kinds of questions you will see:
- Definitions: define deadlock and the four Coffman conditions (short answer).
- Diagrams: draw a RAG / WFG and state whether a deadlock exists; show the cycle and list deadlocked processes.
- Algorithms and proofs: give the multiple-instance deadlock-detection algorithm and argue its correctness (explain Work/Finish invariant).
- Numericals: given Total, Allocation and Request matrices, run the detection algorithm step-by-step and list deadlocked processes (or show none).
- Recovery discussion: short notes comparing abort, preemption, rollback; give criteria for selecting victim.
What a full-marks answer includes:
- Precise definitions with bold terms (deadlock, mutual exclusion, hold-and-wait, no-preemption, circular-wait).
- Correct diagram conventions and explicit labels (P and R nodes, arrow directions, instance counts if multi-instance).
- For algorithms: formal steps (initialize Work, Finish; find Request ≤ Work; mark and release; conclude), and a short correctness justification.
- For numericals: show every vector/matrix computation (Available, Work updates) and final decision.
Quick check
- State the four conditions necessary for deadlock.
- Is a cycle in a resource-allocation graph always sufficient to conclude deadlock? Explain briefly.
- In the multiple-instance deadlock-detection algorithm, what do you do when you find a process whose Request ≤ Work? Answers: 1) Mutual exclusion, Hold-and-wait, No preemption, Circular wait. 2) No — only sufficient for single-instance resources; for multiple instances a cycle is necessary but not always sufficient. 3) Mark the process Finish=true and set Work = Work + Allocation[that process] (simulate it finishing and releasing resources).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?