Deadlock detection and recovery

1. What is a deadlock (recap)

The four Coffman conditions must all hold: mutual exclusion, hold-and-wait, no preemption, and circular wait. Detection assumes we let these happen and look for the consequence.

2. Detection — single instance per resource type

We build a Wait-For Graph (WFG): collapse the Resource-Allocation Graph by removing resource nodes.

WHAT: node = process. Edge $P_i \to P_j$ means $P_i$ is waiting for a resource currently held by $P_j$ .
HOW to derive it: in the RAG, if $P_i \to R_k$ (request) and $R_k \to P_j$ (allocation), then in the WFG draw $P_i \to P_j$ .

Figure — Deadlock detection and recovery

3. Detection — multiple instances per resource type

Data structures

$\textbf{Available}[1..m]$ : free instances of each of $m$ resource types.
$\textbf{Allocation}[n][m]$ : how much process $i$ currently holds.
$\textbf{Request}[n][m]$ : what process $i$ is currently requesting (note: this is request, not the Banker's "max need").

WHY this works: if $Request_i \le Work$ , process $i$ can get what it asks, run, and release everything it holds — adding $Allocation_i$ back to the pool. We optimistically grant resources to whoever can run, snowballing the free pool. Any process we can never satisfy this way is genuinely stuck.

4. When to run detection?

5. Recovery

Once detected, break at least one Coffman condition. Three families:

Worked example Worked detection — multiple instances

3 types $A,B,C$ with totals; current state:

P	Allocation (A B C)	Request (A B C)
P0	0 1 0	0 0 0
P1	2 0 0	2 0 2
P2	3 0 3	0 0 0
P3	2 1 1	1 0 0

$Available = (0,0,0)$ .

Step 1. $Work=(0,0,0)$ . P0 needs $(0,0,0)\le Work$ ? Yes. Why? zero request always passes. Finish P0, $Work += (0,1,0) = (0,1,0)$ . Step 2. P2 needs $(0,0,0)\le(0,1,0)$ ? Yes. $Work += (3,0,3) = (3,1,3)$ . Step 3. P1 needs $(2,0,2)\le(3,1,3)$ ? Yes. $Work += (2,0,0) = (5,1,3)$ . Step 4. P3 needs $(1,0,0)\le(5,1,3)$ ? Yes. $Work += (2,1,1)=(7,2,4)$ . All finished → no deadlock. Sequence $\langle P0,P2,P1,P3\rangle$ .

Now change $Request_{P2}=(0,0,1)$ . Replay: P0 finishes → $Work=(0,1,0)$ . P2 needs $(0,0,1)\le(0,1,0)$ ? No (C: 1 ≤ 0 fails). P1 needs $(2,0,2)$ ? No. P3 needs $(1,0,0)$ ? No. Nobody else moves → P1, P2, P3 are deadlocked. Why this step matters: one extra unit of demand for C that never gets freed jams the chain.

Recall Feynman: explain to a 12-year-old

Imagine four kids each holding one half of two toys they want to swap, and each is waiting for the other to hand over their half first. Nobody lets go, so they freeze forever — that's a deadlock. The teacher (the OS) walks around with a checklist: "Can anyone finish with the toys lying free right now?" If yes, that kid plays, then drops their toys back into the box so others can grab them — and the teacher keeps going. If she reaches a point where no kid can ever play, those kids are stuck. To fix it she either makes one kid quit and give up their toys (termination) or snatches a toy away and hands it over (preemption) — choosing the kid who'd lose the least progress.

Flashcards

In a single-instance system, what graph condition is necessary AND sufficient for deadlock?

A cycle in the Wait-For Graph (WFG).

Why is a cycle NOT sufficient for deadlock with multiple resource instances?

Another holder may release an instance that satisfies a waiting process, so the cycle can resolve without everyone being stuck. You must simulate finishing.

What's the key difference between the deadlock detection algorithm and the Banker's algorithm?

Detection uses the actual current Request (after the fact, optimistic); Banker's uses Need = Max − Allocation (worst-case, beforehand, to prevent unsafe states).

In detection, why do processes with Allocation = 0 start as Finish = true?

They hold no resources, so they cannot be part of any circular-wait deadlock and can't block anyone.

How does the detection algorithm decide a process can finish?

If its current Request ≤ Work (componentwise); then it runs and releases, so Work += Allocation_i.

After the detection loop ends, who is deadlocked?

Every process i with Finish[i] = false.

Why allow deadlocks then detect, instead of preventing them?

Prevention/avoidance taxes every request; if deadlocks are rare, occasional detection+recovery is cheaper overall.

Name the two main recovery strategies.

Process termination (abort all / abort one-by-one) and resource preemption (with rollback to a checkpoint).

What three issues complicate recovery by preemption?

Victim selection (minimize cost), rollback (to a safe checkpoint), and starvation (don't always pick the same victim).

How do you prevent starvation when the same process is repeatedly chosen as victim?

Include the number of prior rollbacks in the victim-cost function so a chronic victim eventually becomes protected.

What is the cost of cycle detection in a WFG with V processes?

O(V²).

Connections

Resource Allocation Graph — the WFG is its process-only projection.
Banker's Algorithm — same loop, but avoidance (Need) vs detection (Request).
Coffman Conditions — recovery works by breaking one of these.
Checkpointing and Rollback — the mechanism enabling preemption recovery.
CPU Scheduling — victim selection reuses priority/aging ideas.
Deadlock Prevention vs Avoidance — the alternative philosophies.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, deadlock detection ka idea simple hai: kuch OS jaan-boojh kar deadlock hone dete hain, kyunki har request pe prevention ya Banker's algorithm chalana mehenga padta hai. Agar deadlock kabhi-kabhi hi hota hai, toh hone do — baad mein detect karke clean kar lenge. Isme do kaam hain: pehle detect karo ki sach me deadlock hua hai ya nahi, phir recover karo (kisi process ko maaro ya resource cheen lo).

Single instance wale resources me detection bahut aasan hai — bas ek Wait-For Graph banao (Pi → Pj matlab Pi, Pj ke paas wala resource maang raha hai). Agar is graph me cycle ban gaya, deadlock pakka. Cycle = deadlock, sure shot. Lekin jab ek resource type ke multiple instances hain, tab sirf cycle dekhna kaafi nahi — kyunki koi doosra holder release karke waiting process ka kaam bana sakta hai. Tab hum simulate karte hain: $Work = Available$ se shuru karo, dekho kaun apna $Request \le Work$ satisfy karta hai, use finish karwa do aur uska $Allocation$ wapas pool me daal do. Jo process kabhi finish nahi ho sakta — wahi deadlocked hai.

Yahan ek bada confusion hota hai: log isko Banker's algorithm samajh lete hain. Farak yeh hai — Banker's me Need (Max − Allocation) use hota hai pehle se unsafe state rokne ke liye; detection me actual current Request use hota hai baad me deadlock dhoondhne ke liye. Recovery me ya toh process ko abort karo (sabko ya ek-ek karke), ya resource preempt karke checkpoint pe rollback karo. Bas ek baat dhyan rakho — har baar same process ko victim mat banao, warna woh kabhi finish hi nahi karega (starvation). Isliye rollback count ko cost me jod do.

1. What is a deadlock (recap)

2. Detection — single instance per resource type

3. Detection — multiple instances per resource type

Data structures

4. When to run detection?

5. Recovery

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Operating Systems

Connections