Deadlock Detection and Recovery

Analogy categoryAnalogies

Introduction

When prevention and avoidance are too costly or impractical — for example, because maximum resource claims are unknown in advance — an operating system can instead allow deadlocks to occur and deal with them reactively. This strategy has two parts: a detection algorithm that periodically checks whether the system is currently deadlocked, and a recovery procedure that breaks the deadlock once found, typically by terminating processes or preempting resources.

🏏

Cricket analogy: When it's too costly to know every touring team's future ground requests in advance, a board can instead let scheduling conflicts happen and react - periodically checking the fixture list for gridlock and then reassigning grounds or rescheduling matches once a genuine clash is found.

Explanation

For systems with only single-instance resource types, detection reduces to finding a cycle in the resource-allocation graph (equivalently called a wait-for graph once resource nodes are collapsed out) — a cycle indicates deadlock among the processes involved. For systems with multiple instances of each resource type, a more general Detection Algorithm is used: structurally identical to the Banker's Algorithm's safety check, but using Allocation and Request matrices instead of Allocation and Need, and without the requirement that processes declare a Max in advance. If the algorithm cannot mark all processes as finished, the unfinished processes are deadlocked. The OS runs this detection algorithm periodically, or when a resource request appears to be waiting unusually long, or when CPU utilization drops (a hint that many processes may be blocked).

🏏

Cricket analogy: For single-set equipment like one match ball, spotting a scheduling deadlock is just finding a cycle in who's-waiting-on-whom among teams; for multi-item resources like several practice nets, a more general check runs like a Banker's Algorithm safety pass but using actual current requests instead of pre-declared maximums, run periodically or when utilization of the grounds drops suspiciously.

Example — Detection Algorithm

Processes: P0, P1, P2      Resource types: A, B, C
Available = [0, 0, 0]

           Allocation        Request
          A   B   C        A   B   C
P0        0   1   0        0   0   0
P1        2   0   0        2   0   2
P2        3   0   3        0   0   0

Detection algorithm (Work = Available, Finish[i] = (Allocation[i]==0) initially):

Step 1: Work = [0,0,0]
        P0: Allocation != 0, so Finish[P0] = false initially.
            Request[0] = [0,0,0] <= Work[0,0,0]? yes
            Work = Work + Allocation[0] = [0,1,0]; Finish[P0] = true

Step 2: P1: Request[1] = [2,0,2] <= Work[0,1,0]? no (2 > 0 in col A, 2 > 0 in col C)
            P1 stays unfinished (blocked)

Step 3: P2: Request[2] = [0,0,0] <= Work[0,1,0]? yes
            Work = Work + Allocation[2] = [3,1,3]; Finish[P2] = true

Step 4: Re-check P1: Request[1] = [2,0,2] <= Work[3,1,3]? yes
            Work = Work + Allocation[1] = [5,1,3]; Finish[P1] = true

All processes eventually finish => NO deadlock in this instance.
(If, instead, P1's Request could never be satisfied because the only
remaining Allocation belonged to another equally-blocked process, the
algorithm would terminate with Finish[P1]=false, flagging P1 as deadlocked.)

Analysis

This walkthrough shows that having pending requests does not automatically mean deadlock; the algorithm must actually check whether resources can eventually be freed to satisfy each blocked process. Once real deadlock is confirmed (some Finish[i] remains false), recovery has two main approaches. Process termination: either abort all deadlocked processes at once (simple but wastes all their work), or abort one deadlocked process at a time, re-running detection after each abort, choosing victims by criteria like lowest priority, least CPU time consumed, or fewest resources held. Resource preemption: forcibly take a resource from one process and give it to another, which requires selecting a victim, rolling the victim process back to a safe checkpoint, and guarding against starvation (the same process should not be repeatedly chosen as the preemption victim).

🏏

Cricket analogy: Having several pending ground requests doesn't automatically mean the season is gridlocked - the scheduler must check whether grounds can eventually free up; once real gridlock is confirmed, recovery means either scrapping all conflicting fixtures at once or canceling matches one at a time by criteria like lowest league priority, re-checking after each cancellation.

Key Takeaways

For single-instance resources, deadlock detection is equivalent to cycle detection in the resource-allocation/wait-for graph.
For multi-instance resources, a Banker's-style Detection Algorithm using Allocation and Request matrices identifies deadlocked processes as those that remain unfinished.
Recovery via process termination can abort all deadlocked processes at once or one at a time with re-detection, trading speed against wasted work.
Recovery via resource preemption requires victim selection, safe rollback, and starvation prevention.
The OS must balance how often to run detection: frequent runs catch deadlocks fast but add overhead; infrequent runs save CPU but let deadlocks persist longer.

Practice what you learned

1. For a resource-allocation graph where every resource type has exactly one instance, deadlock detection reduces to:

2. How does the multi-instance Detection Algorithm differ from the Banker's Algorithm's Safety Algorithm?

3. In the worked detection example, why is P1 not immediately marked finished in Step 2?

4. Which of the following is a recognized recovery strategy after a deadlock is detected?

5. What is a key risk that must be managed when using resource preemption for recovery?

Was this page helpful?

Deadlock Prevention and Avoidance

Topics covered

#OperatingSystemsStudyNotes#OperatingSystems#DeadlockDetectionAndRecovery#Deadlock#Detection#Recovery#Explanation#StudyNotes#SkillVeris#ExamPrep