🔍

Deadlock Detection & Recovery — Wait-For Graph & Detection Algorithm

Let deadlocks happen, then catch them: spot a cycle in the wait-for graph, run the detection algorithm on the request matrices, and recover by killing or preempting. With fully worked detection numericals and animated diagrams.

Wait-For Graph Detection Algorithm Victim Selection Rollback

Press Next → or use ← → arrow keys

Section 01

The Story That Explains Detection & Recovery

🔥 ANALOGY · THE FIRE ALARM AT THE MALL

A crowded mall doesn't prevent fires by banning every candle, and it doesn't avoid them by simulating each shopper's every move. That would be paralysing. Instead it accepts that a fire might happen — and installs smoke detectors. When one triggers, an evacuation plan kicks in.

That is detection + recovery: allow all four Coffman conditions, let deadlock occur if it will, detect it periodically, and then recover.

💡

Cheapest When Deadlocks Are Rare

Because it imposes no restrictions up front, this approach gives the highest resource utilisation. You only pay when you actually run the detector — which is why databases and batch systems favour it.

Section 02

Detection — Two Cases

1️⃣

Single Instance

wait-for graph

When every resource type has just one instance, collapse the RAG into a wait-for graph. A cycle ⇔ deadlock, detectable in O(V+E).

🔢

Multiple Instances

detection algorithm

With several instances per type, a cycle is necessary but not sufficient. You must run a safety-like algorithm on the Request matrix.

📥

Request, not Max

key difference

Detection uses what each process is actually requesting right now — not its declared maximum. A zero row means the process isn't waiting.

🔀

RAG → Wait-For Graph

Abstract the resources away: draw an edge Pᵢ → Pⱼ whenever Pᵢ is waiting for a resource that Pⱼ currently holds. The result is a graph of processes only — and a cycle in it means a deadlock.

Section 03 · Diagram

A Cycle in the Wait-For Graph

🔄

P1 → P2 → P3 → P4 → P1

Each edge says "the tail process is blocked waiting for a resource the head process holds." When these wait-for edges close a loop, every process in it is waiting on the next — and none can release. For single-instance resources, this cycle is proof of deadlock.

Section 04

Multiple-Instance Detection Algorithm

# Detection — m resource types, n processes
Work      = Available
Finish[i] = (Allocation[i] == 0)   # idle procs are trivially done

while ∃ i : Finish[i]==false and Request[i] <= Work:
    Work      = Work + Allocation[i]   # pretend Pi finishes & releases
    Finish[i] = true

if ∃ i : Finish[i]==false:
    return "DEADLOCK"   # those procs are deadlocked
else:
    return "NO DEADLOCK"

🆚

Almost the Safety Algorithm — With One Twist

It looks like the Banker's safety check, but it walks the Request matrix (what's needed now), not Need (the declared maximum). A process with a zero request row is assumed able to finish. Any process still Finish[i] == false at the end is deadlocked.

Numerical 1

Detection Example — Is There a Deadlock?

5 processes (P0–P4), 3 resources A/B/C. Total A=7, B=2, C=6. Allocation sums to the totals, so Available = [0, 0, 0].

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 (right now)

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

Available

A	B	C
0	0	0

Two processes (P0, P2) have zero requests — they can finish immediately and hand back their resources, unblocking the rest.

Numerical 1 · Trace

Running the Detector — No Deadlock

Pick	Request ≤ Work?	Work before	Work after (+Alloc)
P0	[0,0,0] ≤ [0,0,0] ✓	[0,0,0]	[0,1,0]
P2	[0,0,0] ≤ [0,1,0] ✓	[0,1,0]	[3,1,3]
P1	[2,0,2] ≤ [3,1,3] ✓	[3,1,3]	[5,1,3]
P3	[1,0,0] ≤ [5,1,3] ✓	[5,1,3]	[7,2,4]
P4	[0,0,2] ≤ [7,2,4] ✓	[7,2,4]	[7,2,6] — all finish

Numerical 2

One Tiny Change → Deadlock

🎯

P2's Request Went From [0,0,0] to [0,0,1]

Same system as before, but now P2 is also waiting — for one unit of C. P0 still finishes (Work → [0,1,0]), but then every remaining process needs resource C, and Work has zero C to give. Nobody can proceed. A one-unit change flipped the system from safe to deadlocked, trapping {P1, P2, P3, P4}.

Section 05

When to Run the Detector

⏰

Fixed Interval

e.g. every 60 s

Simple and predictable, but a deadlock can sit undetected for up to a full interval, wasting resources.

📉

Event-Driven

on low CPU use

Run it when CPU utilisation dips (a hint that processes are stuck), or when a request can't be granted.

⚖️

The Trade-off

O(m·n²) each run

Too often and the algorithm's cost dominates; too rare and users face long freezes. Tune to your workload.

🗄️

How Real Databases Do It

PostgreSQL and Oracle check on a lock-wait timeout and abort the cheapest transaction (errors 40P01 / ORA-00060); MySQL InnoDB keeps an internal wait-for graph and checks on every lock wait. The rule for developers: catch the deadlock error and retry.

Sections 06–08

Recovery — Two Approaches

💀

Terminate: All

simple, wasteful

Abort every deadlocked process at once. Guaranteed to break the cycle — but throws away a lot of work.

🔪

Terminate: One at a Time

minimise loss

Kill one victim, re-run detection, repeat until the cycle clears. Less work lost, but more detection cost.

🔙

Preempt + Rollback

no kill

Seize a resource from a victim, roll it back to a checkpoint, and give the resource to another — needs checkpointing.

🎯

Choosing the Victim Isn't Arbitrary

Pick the lowest-cost victim, weighing priority, CPU time already spent, time remaining, resources held, and interactive-vs-batch. Crucially, fold in how many times a process has already been a victim — otherwise the same unlucky process is picked forever and starves.

Section 07 · Diagram

Iterative Victim Selection — Kill the Cheapest

💰

Lowest Cost Wins

The cycle P1→P2→P3→P4→P1 has costs 200 / 50 / 150 / 80. Aborting P2 (cost 50) frees its resources, and re-running detection shows the cycle is gone — so total work lost is just 50. If one victim weren't enough, you'd kill the next-cheapest and re-check, tracking the running cost.

Section 08 · Diagram

Preemption & Rollback

🔙

Undo Just Enough

To preempt a resource safely, roll the victim back to the last checkpoint where it didn't hold that resource — here CP-2. Everything it did between CP-2 and the preemption is lost work and must be redone. That's the price of preemption, and why it needs a checkpointing system underneath.

Section 11

Prevention vs Avoidance vs Detection

Aspect	Prevention	Avoidance	Detection + Recovery
When applied	Design time	Each request	Periodic / event-driven
Coffman conditions	Breaks ≥1	Allows all 4	Allows all 4
A-priori info	None	Max declarations	None
Overhead	Zero	O(m·n²) / request	O(m·n²) / invocation
Resource use	Often low	Moderate	High
Best fit	General OS, kernel	Real-time, embedded	Databases, batch systems

🌍

Detection Rules the Database World

Because it maximises resource use and only acts when trouble actually strikes, detection + recovery is the default for systems running huge numbers of concurrent transactions — PostgreSQL, Oracle, MySQL — where the occasional aborted-and-retried transaction is a fine price to pay.

Section 13

Eight Rules for Detection & Recovery

🔍 DETECTION & RECOVERY · CHECKLIST

1

Detection + recovery is cheapest at runtime when deadlocks are rare — it imposes nothing up front.

2

Single-instance → use the wait-for graph; a cycle ⇔ deadlock, found in O(V+E).

3

Multi-instance → a cycle is necessary but not sufficient; run the algorithm on the Request matrix.

4

Tune detection frequency: too often is overhead, too rare means long freezes.

5

Recover by termination or preemption + rollback — prefer aborting one at a time.

6

Choose the lowest-cost victim — weigh priority, CPU time, time left, resources held.

7

Preemption needs checkpoints; roll back only far enough to release the resource.

8

Prevent starvation by making repeat victims more expensive; database clients must catch & retry.

FINAL

Catch It, Then Clean It Up

WFGCycle ⇔ deadlock

Requestnot Max

⟨P0,P2,P1,P3,P4⟩Safe completion order

[0,0,1]The one change that broke it

50Cheapest victim cost

🎯

You Can Now Detect and Recover From Any Deadlock

From building a wait-for graph and spotting its cycle, to running the multi-instance detection algorithm on the Request matrices, to selecting a minimum-cost victim and rolling it back — you can handle the full detect-and-recover workflow, by hand or in code.

📚

Where To Go Next

You've now completed the entire deadlock arc — model, conditions, prevention, avoidance, detection and recovery. The next major unit is memory management: contiguous allocation, paging and segmentation, then virtual memory.

🔍 End of tutorial · Press ← to review, or click Restart