Deadlock detection and recovery: Question bank — Coding deep dive

Definition Notation — every symbol used on this page, in plain words

So this page is self-contained, here is the whole vocabulary before we test it:

$n$ ::: the number of processes (jobs) in the system. Think "how many kids in the room." Everywhere on this page $n$ = number of processes.
$m$ ::: the number of resource types (printer, tape drive, memory block, …). Each type can have several identical copies = instances. Because there are $m$ types, most quantities below are lists of $m$ numbers, one per type.
$A l l oc a t i o n_{i}$ ::: a list of length $m$ — how many instances of each type process $i$ currently holds right now.
$R e q u es t_{i}$ ::: a list of length $m$ — what process $i$ is asking for right now (its current ask, NOT its lifetime maximum).
$M a x_{i}$ and $N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}$ ::: these belong to Banker's Algorithm. $M a x_{i}$ = the most $i$ could ever need; $N ee d_{i}$ = what's left of that worst case. Detection does not use these — that's the whole trap.
$A v ai l ab l e$ ::: a list of length $m$ — free instances of each type sitting unused in the pool.
$W or k$ ::: a scratch copy of $A v ai l ab l e$ that grows as finished processes hand their resources back. It is the "how much is free so far in the simulation" counter.
$F ini s h [i]$ ::: a true/false flag — has process $i$ been shown able to finish in the simulation yet?
$W F G$ (Wait-For Graph) ::: a picture where each node is a process and an arrow $P_{i} \to P_{j}$ means " $P_{i}$ is waiting for a resource $P_{j}$ holds." Built by collapsing the Resource Allocation Graph (drop the resource nodes).

Figure — Deadlock detection and recovery

The bucket starts nearly empty ( $W or k = A v ai l ab l e$ ). Each time a process passes $R e q u es t_{i} \leq W or k$ , it finishes and pours its $A l l oc a t i o n_{i}$ into the bucket, so the level rises. As the level rises, requests that were "too big" a moment ago now fit — that is the snowball. If at some point no remaining process's request fits the current level and the level stops rising, those leftover processes can never be satisfied → they are the deadlocked set (shown in coral at the bottom of the figure).

True or false — justify

A cycle in the Wait-For Graph always means deadlock.

Only in a single-instance system. With multiple instances per type another holder may release an instance that frees a waiter, so the cycle can dissolve without simulation confirming it (see the finish-snowball figure s02).

If the detection loop finishes with every

F ini s h [i] = t r u e

, the system is deadlock-free right now.

True — a valid finish order exists, so every process can obtain its current

R e q u es t_{i}

, run, and release; nobody is permanently stuck.

Deadlock detection guarantees no process will ever deadlock in the future.

False. Detection is a snapshot of the current state; it says nothing about requests that arrive later. See Deadlock Prevention vs Avoidance — only avoidance/prevention look forward.

A process holding zero resources can still be part of a deadlock.

False. With

A l l oc a t i o n_{i} = 0

it starts

F ini s h = t r u e

: it holds nothing anyone waits for, so it cannot sit in a circular-wait chain.

Running detection more often is strictly better because you catch deadlocks sooner.

False. Detection costs

O (m \cdot n^{2})

(justified in the Why section); running it on every ungrantable request is huge overhead. Rareness of deadlock is exactly why we tolerate delay.

Aborting all deadlocked processes is the safest recovery because it definitely works.

It definitely breaks the deadlock, but "safest" is wrong — it discards the most work. Abort-one-at-a-time wastes less but reruns the detector repeatedly.

The detection algorithm and Banker's safety check are the same algorithm.

False. The loop shape matches, but detection tests actual current

R e q u es t_{i}

(backward-looking) while Banker's tests

N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}

(worst-case, forward-looking).

Preempting a resource always requires a rollback.

Essentially true: the victim lost a resource mid-use, so it must roll back to a safe checkpoint (or restart) to stay consistent — you can't just continue as if nothing happened.

If deadlock detection reports "no deadlock", CPU utilization must be high.

False. Utilization can be low for many reasons (I/O waits, idle jobs). Low utilization is only a trigger to consider running detection, not a synonym for deadlock.

Spot the error

"With multiple instances, we detect deadlock by finding a cycle in the Wait-For Graph."

Error: WFG cycles only decide single-instance systems. Multiple instances require the finish-simulation, because a cycle there is necessary but not sufficient.

"In detection we use

N ee d_{i} = M a x_{i} - A l l oc a t i o n_{i}

to see who can finish."

Error: that's Banker's, which uses the worst-case leftover need. Detection uses the actual current

R e q u es t_{i}

, not any maximum.

R e q u es t_{i} \leq W or k

means process

i

finished, so add

W or k

A l l oc a t i o n_{i}

Two errors: it means

i

can finish (not that it did), and we add

A l l oc a t i o n_{i}

W or k

(reclaim what it holds), not the other way round.

"Since all four Coffman conditions must hold, breaking mutual exclusion is the standard recovery."

Error: the four conditions are mutual exclusion (a resource can't be shared), hold-and-wait, no-preemption, and circular-wait — and mutual exclusion is usually intrinsic (a printer can't be shared), so recovery normally breaks no-preemption (preempt) or circular-wait (abort) instead. See Coffman Conditions.

"Victim selection just picks the process with the fewest resources so cleanup is fast."

Oversimplified/wrong. Cost blends priority, time already run, resources held, processes affected, and — crucially — number of prior rollbacks to prevent starvation.

"The detector tells us exactly which request caused the deadlock."

Error: if detection runs periodically rather than on every request, many requests happened since the deadlock formed, so you generally can't pinpoint the culprit request.

"A safe state and a deadlock-free snapshot are the same thing."

Error: safe (Banker's) means a safe sequence exists for all future worst-case demands (

N ee d_{i}

); deadlock-free detection only means the current

R e q u es t_{i}

can all be satisfied. Safe ⊂ deadlock-free.

Why questions

Why does a zero request always pass the

R e q u es t_{i} \leq W or k

test?

Because the

\leq

is component-wise (defined above):

(0, 0, \dots) \leq W or k

holds for any non-negative

W or k

since every entry

0 \leq W or k [k]

. A process asking for nothing needs nothing granted, so it finishes immediately and releases its holdings. Example with

m = 3

: P0 with

R e q u es t = (0, 0, 0)

passes even when

W or k = (0, 0, 0)

Why do we optimistically grant to whoever can run instead of proving deadlock directly?

Toy example with

m = 3

types: pool starts empty

(0, 0, 0)

, but P0 holds

(0, 1, 0)

and requests nothing. Grant P0 → it finishes →

W or k

grows to

(0, 1, 0)

. Now a process that needed that one unit of the second type can run, hands its stuff back, and the pool snowballs. Anyone still unsatisfiable after the pool stops growing is genuinely, permanently stuck — that's your deadlock set. (See figure s02.)

Why include the number of rollbacks in a victim's cost function?

To prevent starvation. Imagine the cost picks the cheapest victim; if process X is always cheapest, it gets preempted, rolled back, preempted, rolled back… forever and never finishes. Adding "how many times has X already been rolled back?" makes X grow expensive, so eventually someone else is chosen and X can complete.

Why does the single-instance case cost

O (n^{2})

while multiple instances cost

O (m \cdot n^{2})

Single instance = plain cycle detection on the Wait-For Graph, whose nodes are the

n

processes; DFS visits each node and edge, and with up to

n

nodes and up to

n^{2}

possible edges that is

O (n^{2})

(here

n

= number of processes, same

n

used everywhere on this page). Multiple instances: each pass of the finish-loop scans all

n

processes, and for each one compares $m$ resource components in

R e q u es t_{i} \leq W or k

— that's

m \cdot n

work per pass. In the worst case only one new process finishes per pass, so you need up to

n

passes →

m \cdot n \times n = O (m \cdot n^{2})

Why is "detect and recover" chosen over prevention when deadlocks are rare?

Prevention/avoidance runs a check on every single resource request — a permanent tax paid millions of times a second. Detect-and-recover pays nothing per request and only runs the expensive detector occasionally (e.g. when CPU utilization dips). If deadlocks almost never happen, the occasional big bill is far cheaper than the constant small one.

Why can't preemption recovery skip the rollback and just resume the victim later?

Walk it through: process X was halfway through writing a file using resource R when R was snatched. X's internal state (variables, half-written data) assumes it still holds R and its work is intact. If you just hand R back and resume, X continues from corrupt state. Instead it must return to a consistent checkpoint taken before R was in use, and redo from there.

Edge cases

What happens if

A v ai l ab l e

starts as all zeros?

Detection still works:

W or k

begins at

(0, 0, \dots)

, so only processes with a zero

R e q u es t

(or ones satisfied once a finisher reclaims resources) can start. The whole snowball bootstraps from reclaimed

A l l oc a t i o n

, not from free instances.

What if every process holds resources but every

R e q u es t_{i}

is zero?

No deadlock — each process needs nothing more, so all pass the test immediately and finish; there's no circular wait to trap them.

Can a WFG cycle appear yet the snapshot be deadlock-free?

Yes — but only with multiple instances. The snowball may let a third holder finish and release an instance that satisfies one process in the loop, breaking the "cycle". This is exactly why single-instance WFG cycles are sufficient but multi-instance ones are not: the graph loses information about spare copies.

A single process requests more of a resource than the system will ever have — deadlock?

No, that's not deadlock (no set of mutually-waiting processes); it's an unsatisfiable request / error. Deadlock needs circular waiting among a set of two or more.

Detection runs, finds nobody can finish, but one process was about to voluntarily release — is it really deadlocked?

By the snapshot it is deadlocked. Detection judges the frozen state; a release that hasn't happened yet isn't visible, which is a limitation of snapshot-based detection, not a false positive of the rule.

Only three of the four Coffman conditions hold — can deadlock occur?

No. All four (mutual exclusion, hold-and-wait, no-preemption, circular-wait) are necessary; break any one and deadlock is impossible — which is exactly how recovery works.

Recall One-line self-test

The two verdict rules ::: Single instance: cycle in WFG is necessary AND sufficient. Multiple instances: run the finish-simulation; leftover $F ini s h [i] = f a l se$ processes are deadlocked. The two recovery families ::: Process termination (abort all / abort one-by-one, rerunning the detector) and resource preemption (pick victim → rollback to a checkpoint → count rollbacks to avoid starvation).