Deadlock Detection and Recovery in Operating Systems: Algorithms, Worked Examples and GATE Traps
Learn when deadlock detection applies, trace single-instance and multiple-instance examples, and verify that a recovery choice really frees the system.
KnowledgeGate Team
Exam prep & CS education

Prevention changes the allocation rules, and avoidance refuses requests that would make the state unsafe. Detection takes a different risk: it allows normal allocation, then checks whether processes are already deadlocked. A wait-for graph, a multiple-instance matrix algorithm, and a recovery check show whether the deadlock exists and whether the chosen action breaks it.
Deadlock detection comes after the system accepts the risk
The detection policy has a clear order. The system grants requests under its normal rules, runs a detection routine periodically or when symptoms justify it, identifies the exact deadlocked set, and then recovers. Detection is reactive. Unlike prevention, it does not break a necessary deadlock condition; unlike avoidance, it does not keep every allocation in a safe state; unlike ignoring deadlocks, it actively searches for them.
There is a trade-off in how often detection runs. Very frequent checks add computation overhead. Infrequent checks may leave more processes blocked and more resources tied up before the problem is found. No single interval suits every system because the right choice depends on workload and recovery cost.
For the full map of Coffman conditions, handling choices and Banker's safety check, start with Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples. Detection uses a narrower data set: current Request rather than Max, followed by an exact stuck set and a recovery proof.
One instance per resource: build the wait-for graph
Begin with a resource-allocation graph. If Pi requests the only instance of Rk and Pj holds it, the chain Pi -> Rk -> Pj becomes the wait-for edge Pi -> Pj. Transfer every such dependency, then remove the resource nodes.
The scope matters: when every resource type has exactly one instance, a directed cycle in the wait-for graph is both necessary and sufficient for deadlock. With multiple instances per resource type, a cycle in a resource-allocation graph is not sufficient. Use the matrix algorithm instead.
Worked example 1: locate the deadlocked processes from a cycle
Take four single-instance resources. The allocation edges are R1 -> P1, R2 -> P2, R3 -> P3 and R4 -> P4. The outstanding request edges are P1 -> R2, P2 -> R3 and P3 -> R1. Process P4 has no outstanding request.
Reduce each dependency:
P1 -> R2 -> P2becomesP1 -> P2.P2 -> R3 -> P3becomesP2 -> P3.P3 -> R1 -> P1becomesP3 -> P1.
The result contains the cycle P1 -> P2 -> P3 -> P1. Therefore the deadlocked set is exactly {P1, P2, P3}. P4 is not deadlocked. It can finish and release R4, but R4 does not appear in the cycle, so that release cannot resolve this deadlock.
The Deadlock in Operating Systems: Four Conditions and Worked Resource-Allocation Graphs guide uses the three-process ring to establish Coffman conditions and the single-instance cycle rule. Adding P4 changes the task: reduce the graph to a wait-for graph and report the exact deadlocked set without including an unrelated process.

Multiple instances: run the detection matrix, not Banker's safety test
For multiple instances, Available is the vector of resources free now. Allocation[i] is what process Pi currently holds, while Request[i] is its current outstanding request. Request is not Max - Allocation.
Set Work = Available. In general, initialise Finish[i] as false for a process holding resources and true for one holding none. Every process below holds at least one resource, so Finish = [false, false, false]. Repeatedly find an unfinished Pi for which Request[i] <= Work component by component. Simulate its completion with Work = Work + Allocation[i], then mark it finished. When no row qualifies, unfinished resource-holding processes form the deadlocked set.
Here the resource types are A, B and C. Total is [2, 2, 1], and Available is [0, 0, 0].
Process | Allocation A B C | Current Request A B C |
|---|---|---|
P0 | 0 0 1 | 0 0 0 |
P1 | 1 0 0 | 0 1 0 |
P2 | 1 2 0 | 1 0 0 |
First check conservation. Allocation sums to [0+1+1, 0+0+2, 1+0+0] = [2, 2, 1]. Adding Available [0, 0, 0] reproduces Total [2, 2, 1].
At Work = [0, 0, 0], only P0 qualifies because [0, 0, 0] <= [0, 0, 0]. P0 finishes and releases Allocation [0, 0, 1], so Work becomes [0, 0, 1] and Finish becomes [true, false, false]. P1 still needs one B, but Work has zero B. P2 still needs one A, but Work has zero A. No further row qualifies, so the exact deadlocked set is {P1, P2}.
This is not Banker's safety test. The Banker's Algorithm worked guide uses remaining Need to avoid an unsafe allocation. Detection uses requests that processes are already waiting on.
![Matrix-and-flow figure showing Allocation and Request rows, Work changing from [0,0,0] to [0,0,1], and P1 and P2 blocked.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784729226003_1fghbl.jpg)
Recovery: choose a victim, then prove the cycle is broken
Recovery has two main routes. Process termination may abort every deadlocked process together, or abort one victim at a time and rerun detection. Resource preemption takes a safely preemptible resource from a victim, rolls that process back to a checkpoint, and restarts it later. Without rollback support, preemption can corrupt work. An ageing or rollback-count rule is also needed so that the same process is not repeatedly chosen and starved.
Apply termination to the matrix example. P0 has already finished, so current Work is [0, 0, 1]. If P2 is aborted, its Allocation [1, 2, 0] is released:
[0, 0, 1] + [1, 2, 0] = [1, 2, 1].
P1's Request [0, 1, 0] now fits. If that B is allocated temporarily, free resources become [1, 1, 1]; P1 then holds [1, 1, 0] and releases both units on completion, restoring [2, 2, 1]. Equivalently, the detection update adds P1's original Allocation to Work: [1, 2, 1] + [1, 0, 0] = [2, 2, 1]. The deadlock is broken. Aborting P1 would release one A, allowing P2 to continue, so either victim works in this particular state.
Victim selection is a policy choice, not a universal formula.
Process | Priority | Progress | Allocated instances |
|---|---|---|---|
P1 | 8/10 | 70% | 1 |
P2 | 3/10 | 25% | 3 |
A policy that protects high-priority, nearly completed work would choose P2. Another workload may weigh held resources, remaining time, checkpoint cost, interactive impact and previous rollbacks differently.
How exam questions test detection, and the traps that cost marks
Three common GATE-style shapes are: convert a resource-allocation graph and report the exact deadlocked set; execute Work and Finish passes on matrices; or judge statements that compare prevention, avoidance, detection and recovery. Once the method is clear, the GATE Test Series can turn it into timed Operating Systems practice.
Wrong shortcut | Correct rule |
|---|---|
Unsafe means deadlocked | Unsafe means no guaranteed safe sequence; it need not be deadlocked now |
Detection Request is Banker's Need | Request is what the process is currently waiting for |
Any cycle proves deadlock | A cycle is decisive only when each resource type has one instance |
Available means Total | Available contains only resources free now |
Add Request after simulated completion | Add the qualifying process's Allocation to Work |
Every blocked process is deadlocked | A blocked process holding no resources may wait without joining the resource-holding deadlock set |
Use a 20-second audit: decide whether the graph or matrix rule applies, copy Available exactly, compare every vector component, release Allocation only after a row qualifies, and report every unfinished process rather than only the first cycle or blocked row you notice.
Short version and the next practice step
Detection asks whether deadlock exists now. A wait-for cycle is decisive only for single-instance resources. With multiple instances, repeatedly finish satisfiable rows and label the remaining set. Recovery must release enough resources while preventing repeated victim selection from causing starvation.
Redraw the P1-P2-P3 cycle from memory, rerun the P0-P1-P2 matrix without looking, then explain why aborting P2 produces Work [1, 2, 1]. For the wider Operating Systems sequence, browse CS Fundamentals for the next topic.
Keep learning
Deadlock Prevention in Operating Systems: Conditions, Policies and Worked Examples
Learn how each deadlock-prevention policy breaks a Coffman condition. Worked printer, buffer, allocation and resource-ordering traces show the guarantee and its cost.
Deadlock in Operating Systems: Four Conditions and Worked Resource-Allocation Graphs
Learn why a cycle proves deadlock only for single-instance resource types, then trace a three-process deadlock and a multiple-instance escape sequence.
Deadlock in Operating Systems: Four Conditions, Handling Methods and a Worked Banker's Algorithm
Build deadlock reasoning from resource-allocation graphs to safe-state checks. The five-process Banker's example also tests one safe and one unsafe request.
Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples
Learn to diagnose deadlocks, read resource-allocation graphs, compute Need, verify a Banker's safe sequence, and separate prevention from recovery.





