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

Updated 1 Nov 20266 min read
Deadlock Detection and Recovery in Operating Systems: Algorithms, Worked Examples and GATE Traps

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:

  1. P1 -> R2 -> P2 becomes P1 -> P2.

  2. P2 -> R3 -> P3 becomes P2 -> P3.

  3. P3 -> R1 -> P1 becomes P3 -> 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.

Two-panel resource-allocation and wait-for graph showing four processes, four single-instance resources, a red P1-P2-P3 cycle, and isolated P4 able to finish.

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.

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.