Deadlock Detection & Recovery

Section 01

The Story That Explains Detection & Recovery

📖 Real World Analogy

The Fire Alarm at the Mall

A crowded shopping mall doesn't try to prevent fires by banning candles or open kitchens — that would kill the food court. It doesn't avoid them by simulating every possible ignition scenario in real time — that would need a supercomputer per shop.

Instead, the mall accepts that fires might happen. It installs smoke detectors on every ceiling (detection), and when one triggers, an evacuation plan kicks in — sprinklers, alarms, fire doors, evacuation staff (recovery). Life goes on. Small losses beat operational paralysis.

Operating systems that use the detection + recovery strategy do exactly the same thing. They let processes lock resources freely, run a periodic checker to spot any deadlock cycle, and — when caught — kill or roll back the minimum needed to restore progress. Database engines like Oracle and PostgreSQL live in this world every day.

💡

Detection vs Prevention vs Avoidance

Prevention makes deadlock impossible by design (breaks a Coffman condition). Avoidance uses a-priori knowledge (Banker's) to refuse risky requests. Detection + Recovery lets deadlocks happen freely, notices them after the fact, and repairs the damage. Cheapest at runtime, most permissive to programmers.

Section 02

Detection — Overview

If the system uses neither prevention nor avoidance, deadlocks may occur. In that case, the OS must periodically ask the two questions:

❓

Question 1

detection algorithm

Does a deadlock currently exist? Yes / no. Requires scanning the current allocation and request state.

🔧

Question 2

recovery scheme

If yes, how do we recover? Terminate processes, preempt resources, roll back to checkpoints — pick a strategy that minimises lost work.

⏰

Overhead

the price of freedom

Runtime cost of the detection algorithm itself plus the cost of any recovery. This is the trade-off you accept for allowing all four Coffman conditions to exist.

🔑

Two Variants of the Detection Algorithm

Galvin distinguishes two cases based on resource instances:
• Single-instance resources — a cycle in the Wait-For Graph is both necessary and sufficient for deadlock. Very cheap: O(n²) cycle detection.
• Multiple-instance resources — cycle is necessary but not sufficient. We must run a full matrix-based algorithm (essentially the safety algorithm with Request in place of Need).

Section 03

Single-Instance Case — The Wait-For Graph

When every resource type has exactly one instance, we can simplify the Resource-Allocation Graph. Since exactly one process holds each resource, we can eliminate resource nodes entirely and record the "who is waiting for whom" relationship directly between processes.

📋 From RAG to Wait-For Graph

Rule

For each pair (P_i, P_j), draw an edge P_i → P_j in the WFG if and only if there exists a resource R_k in the RAG such that P_i requests R_k AND R_k is held by P_j.

Meaning

An edge P_i → P_j means "P_i is waiting for P_j to release something." Resources have been abstracted away.

Deadlock Test

A cycle in the WFG ⇔ deadlock exists among the processes in that cycle. Standard graph algorithms detect cycles in O(V + E).

🎮 Interactive — Derive Wait-For Graph and Detect the Cycle

Four processes P1–P4 and four single-instance resources R1–R4. Step through the derivation of the WFG, one edge at a time.

RAG → Wait-For Graph Conversion

Step 0 of 5

START Left side shows the full RAG: P1 holds R1 and requests R2, P2 holds R2 and requests R3, P3 holds R3 and requests R4, P4 holds R4 and requests R1. Right side will be the WFG we build. Click Next to derive edges one at a time.

Section 04

Multiple-Instance Case — Detection Algorithm

When resource types have multiple instances, a cycle in the graph is necessary but not sufficient — the cycle may resolve if extra instances outside the cycle become free. Galvin defines a matrix-based algorithm nearly identical to Banker's safety check, except we use the current Request matrix instead of the declared Need matrix.

📋 Data Structures — n processes, m resource types

Available[m]

Vector. Instances of each resource type currently free.

Allocation[n][m]

Matrix. Currently held instances per process.

Request[n][m]

Matrix. Instances each process is actually requesting right now (not the declared max). If Request[i][j] = 0 the process is not waiting for that resource.

# Deadlock Detection Algorithm
Work    = Available
Finish  = [Allocation[i] == 0 for i in processes]  # idle procs trivially done

while exists i such that Finish[i] == false and Request[i] <= Work:
    Work      = Work + Allocation[i]                    # pretend Pi finishes, releases
    Finish[i] = true

if exists i where Finish[i] == false:
    return "DEADLOCK — processes with Finish==false are deadlocked"
else:
    return "NO DEADLOCK"

🚩

Two Critical Differences from Banker's

1. Request replaces Need. We use the process's actual pending request, not a declared maximum.
2. No a-priori info required. Detection can run on any live system — you don't need processes to declare Max in advance. This is why it's usable in general-purpose OSes and databases where Banker's isn't.

🎮 Interactive — Detection Algorithm Walkthrough (No Deadlock Case)

Setup: 4 processes, 3 resource types. Total: A=5, B=5, C=4. Sum of allocations: A=4, B=4, C=3, so Available = [1, 1, 1]. Click Next to test one process at a time.

Detection Algorithm — safe outcome (no deadlock)

Allocation

	A	B	C
P0	1	0	1
P1	2	1	0
P2	1	1	1
P3	0	2	1

Request

	A	B	C
P0	0	1	0
P1	0	0	1
P2	1	0	0
P3	1	0	1

Work vector

Work = [ 1, 1, 1 ]

Initially: Work = Available = [1, 1, 1]

Finished processes

⟨ ⟩

Ready to test processes…

Step 0 of 5

START All processes have non-zero allocation → Finish = [F, F, F, F]. Work = [1, 1, 1]. We'll repeatedly find a process whose Request ≤ Work, pretend it finishes, and add its allocation to Work.

Section 05

When to Invoke the Detection Algorithm

Detection is not free. Its overhead is O(m·n²) — same as Banker's safety check. Running it too often wastes CPU; running it too rarely lets deadlocks fester. Two practical strategies:

⏰ Fixed Interval

Run every T seconds (e.g. every 1 minute)

Simple, predictable overhead

Deadlocks may persist for up to T seconds before being noticed

Once found, cannot tell exactly when the deadlock started or which process closed the cycle

📈 Event-Driven

Run when CPU utilisation drops below a threshold (e.g. <40%)

Low utilisation is a strong deadlock symptom — many processes blocked

Detects deadlocks earlier and only when suspected

Can also run per-allocation, but this is very expensive

🔑

Databases Use "Per Request" Detection

Oracle, PostgreSQL, and MySQL InnoDB run detection each time a transaction blocks waiting for a lock. This catches deadlocks immediately but works only because typical databases have far more transactions than resources — the graph stays small.

Section 06

Recovery — Overview

Once a deadlock is detected, we must break the cycle. Galvin outlines two families of solutions. In practice, a single system often uses both together.

💀

Family A — Process Termination

kill victims until cycle breaks

Abort one or more processes to free their resources. Two sub-strategies: abort all deadlocked processes (clean, expensive) or abort one at a time until deadlock is gone (minimises loss).

🔁

Family B — Resource Preemption

snatch resources from victims

Preempt resources from some processes and give them to others until the cycle breaks. The preempted process is rolled back to a safe checkpoint state and must reacquire what was taken.

🎯

Both Need Victim Selection

minimise the pain

Both strategies must pick a "victim" wisely — the process whose termination or preemption causes the least total cost. Blindly picking wastes work; smart selection is what makes recovery viable.

Section 07

Recovery A — Process Termination

Two Sub-strategies

💀💀💀 Abort All Deadlocked

Kill every process in the deadlocked set at once

Simple, one-shot recovery

Wastes all their partial work — potentially hours of computation

Used when work is cheap to redo (batch jobs, stateless services)

💀 Abort One at a Time

Kill lowest-cost victim, re-run detection, repeat until no cycle

Minimises total work lost

Detection algorithm runs again after each kill (O(m·n²) each time)

Preferred when partial work is expensive to redo

Victim Selection — Cost Factors

💰 What Makes a Good Victim?

Priority

Kill low-priority processes first. Preserves important system work.

Work Done

Kill the process with the least CPU time consumed so far — the freshest process wastes the least work when restarted.

Time Remaining

Consider how long the process still needs to run. Killing something 95% done is wasteful.

Resources Held

Killing a process holding many resources frees more for others — one kill may break several cycles.

Interactive vs Batch

Kill batch jobs before interactive processes — users notice the latter.

🎮 Interactive — Cost-Based Victim Selection

Four processes are deadlocked in a cycle. Each has a termination cost (CPU work done so far). Click Next to watch the OS pick victims one at a time until the deadlock is broken.

Iterative victim selection — abort minimum-cost process, re-check

Step 0 of 4

START Four processes deadlocked in a cycle P1→P2→P3→P4→P1. Costs: P1=200, P2=50, P3=150, P4=80. Total abort-all cost would be 480 units. Watch iterative selection minimise the actual cost.

Section 08

Recovery B — Resource Preemption

Instead of killing the process, we take specific resources from it and give them to another. The victim process is rolled back to a state before it held those resources. Three issues must be addressed.

🎯

Issue 1 — Selecting a Victim

which resource to preempt

Same cost-minimisation as termination: consider which resources to seize and which process to seize them from. Pick to minimise total cost (number of resources held, time already running, priority).

⏮️

Issue 2 — Rollback

restore to safe state

Since the victim lost a resource, we can't just continue — data may be inconsistent. Roll back to a previous checkpoint where the process didn't hold that resource. Requires periodic checkpointing infrastructure.

🔠

Issue 3 — Starvation

same victim repeatedly?

If the same process is always the cheapest, it may be preempted forever and never complete. Fix: include number of previous preemptions in the cost calculation, so repeat victims become expensive.

Rollback Illustrated

Process Timeline with Checkpoints and Rollback

⚠️

Total Rollback vs Partial Rollback

The extreme case is total rollback — abort the process entirely and restart from scratch. Effectively the same as Family A (termination). More useful is partial rollback to the most recent safe checkpoint — but this needs checkpointing infrastructure and knowledge of which checkpoint predates the resource acquisition.

Section 09

Numerical Problem 1 — Detection Shows NO Deadlock

Given a system state, run the detection algorithm and determine whether deadlock exists.

Problem Statement

📋 Given

Processes: 5 (P0–P4)

Resource types: 3 (A, B, C)

Total instances: A = 7, B = 2, C = 6

📊 Allocation

	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	3
P3	2	1	1
P4	0	0	2

📊 Request (currently pending)

	A	C
P0	0	0
P1	2	2
P2	0	0
P3	1	0
P4	0	2

📊 Compute Available

Sum_A = 0+2+3+2+0 = 7 → Available_A = 7 − 7 = 0

Sum_B = 1+0+0+1+0 = 2 → Available_B = 2 − 2 = 0

Sum_C = 0+0+3+1+2 = 6 → Available_C = 6 − 6 = 0

Available = [0, 0, 0]

Run Detection

📊 Detection Trace

Init

Work = [0, 0, 0]. All processes have non-zero allocation → Finish = [F, F, F, F, F].

Try P0

Request = [0, 0, 0] ≤ Work [0, 0, 0] ✓ (zero request always satisfies) → pick P0. Work = [0, 0, 0] + [0, 1, 0] = [0, 1, 0].

Try P2

Request = [0, 0, 0] ≤ Work [0, 1, 0] ✓ → pick P2. Work = [0, 1, 0] + [3, 0, 3] = [3, 1, 3].

Try P1

Request = [2, 0, 2] vs Work [3, 1, 3] → 2 ≤ 3 ✓, 0 ≤ 1 ✓, 2 ≤ 3 ✓ → pick P1. Work = [3, 1, 3] + [2, 0, 0] = [5, 1, 3].

Try P3

Request = [1, 0, 0] vs Work [5, 1, 3] ✓ → pick P3. Work = [5, 1, 3] + [2, 1, 1] = [7, 2, 4].

Try P4

Request = [0, 0, 2] vs Work [7, 2, 4] ✓ → pick P4. Work = [7, 2, 4] + [0, 0, 2] = [7, 2, 6].

Done

All Finish = true. Final Work matches total resources. NO DEADLOCK.

🏆

Answer

No deadlock exists. A valid completion sequence is ⟨P0, P2, P1, P3, P4⟩. Even though Available started at [0, 0, 0], processes with zero requests can finish immediately and release resources for the others.

Section 10

Numerical Problem 2 — Interactive Detection Finds a Deadlock

Same system as Numerical 1 with one change: P2's request is now [0, 0, 1] (it wants one more instance of C). Everything else is identical. Click Next to trace the algorithm and watch it get stuck.

Detection Algorithm — DEADLOCK case, identifies which processes are stuck

Allocation

	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	3
P3	2	1	1
P4	0	0	2

Request (P2 changed to [0,0,1])

	A	C
P0	0	0
P1	2	2
P2	0	1
P3	1	0
P4	0	2

Work vector

Work = [ 0, 0, 0 ]

Initially: Work = Available = [0, 0, 0]

Finished processes

⟨ ⟩

Ready to test processes…

Step 0 of 3

START Same as Numerical 1 but with a small change to P2's request. Available = [0, 0, 0]. Let's see what happens when we run the detection algorithm.

🚩

Key Insight

A tiny change (P2's request went from [0,0,0] to [0,0,1]) flipped the system from safe to deadlocked. This shows why detection must run periodically — the state you check five seconds later may be radically different. A single new request can lock everything.

Section 11

Comparison — Detection vs Prevention vs Avoidance

Aspect	Prevention	Avoidance	Detection + Recovery
When applied	Design time	At each request	Periodic / event-driven
Coffman conditions	Breaks at least one	Allows all four	Allows all four
A-priori info needed	None	Max declarations	None
Runtime overhead	Zero	O(m·n²) per request	O(m·n²) per invocation
Cost when deadlock happens	N/A (impossible)	N/A (avoided)	Termination / rollback cost
Resource utilisation	Often low	Moderate — conservative	High
Best fit	General OS, kernel code	Real-time, embedded	Database engines, batch systems

Section 12

Real-World Applications

🖥️

PostgreSQL Deadlock Detection

Runs detection each time a transaction blocks on a lock. When cycle found, aborts the lowest-cost transaction — typically the one with least work done. Aborted transaction sees error 40P01; app must retry.

Detection · Termination · WFG

📈

Oracle Database

Similar strategy — runs detection when a session waits > deadlock_timeout (default 3s) on a lock. Kills the statement (not the whole transaction) with ORA-00060.

Detection · Partial rollback

☕

MySQL InnoDB

Maintains a wait-for graph internally, checks for cycles on every lock wait. Victim selection minimises the transaction with the least undo log — cheapest to roll back.

Detection · WFG · Rollback

📡

Distributed Systems

Detection is harder because there's no global view. Chandy-Misra-Haas probes and edge- chasing algorithms are used. Recovery still boils down to picking a transaction to abort.

Distributed detection · Chandy-Misra-Haas

🔄

Java Deadlock Diagnosis

ThreadMXBean.findDeadlockedThreads() gives runtime deadlock information — pure detection, no recovery. Manual intervention (thread dump analysis) is expected.

Detection · Manual recovery

💾

Linux Kernel Watchdog

The hung_task watchdog notices tasks blocked >120 s (potential deadlock or livelock) and logs stack traces. Recovery is manual — typically requires reboot.

Detection · Manual

Section 13

Golden Rules — Detection & Recovery

🔑 Galvin's Non-Negotiable Rules

Detection + Recovery is the cheapest strategy at runtime when deadlocks are rare. If they're common, the recovery cost dominates and you should prevent instead.

For single-instance resources, use the Wait-For Graph. A cycle in the WFG ⇔ deadlock. Detection is O(V + E) — very cheap.

For multiple-instance resources, a cycle is necessary but not sufficient. Use the matrix-based detection algorithm with the current Request matrix (not the declared Max).

Detection frequency matters. Too frequent = overhead. Too rare = long freezes. A common heuristic: run when CPU utilisation drops below a threshold.

Once a deadlock is detected, you must choose between process termination and resource preemption + rollback. Real systems often use both.

For termination, prefer abort-one-at-a-time with re-detection between kills. Minimises total work lost compared with abort-all.

Victim selection is not arbitrary. Consider priority, CPU time consumed, time remaining, and resources held. Kill the cheapest to restart.

For preemption, you need checkpoint infrastructure to safely roll back. Without checkpoints, preemption degenerates into termination.

Prevent starvation during recovery by tracking how often each process has been chosen as a victim. Include this count in the cost so repeat victims become expensive.

Every well-written database client must handle deadlock-abort errors (Oracle ORA-00060, PostgreSQL 40P01, MySQL 1213) by catching them and retrying the transaction. This is the standard pattern in production.