← 🚧 Deadlock
Subtopic 4 of 4

4.4Detection, recovery and the minimum-resources formula

The idea

Detection uses the same reduction but with current requests; recovery kills or preempts. A frequent question: how few resources guarantee no deadlock?

Think of it like this: A party where each guest needs some number of chairs: if everyone has grabbed all but one chair of what they need, one extra chair lets someone finish and unstick the rest.

Why it exists

The worst case analysis gives a closed form that is asked again and again.

How it works

  1. Worst case: every process holds (max need − 1) units and wants one more.
  2. Total held = Σ(mᵢ − 1).
  3. One extra unit lets one process finish and release everything.
  4. So deadlock-free if R ≥ Σ(mᵢ − 1) + 1; for equal needs n(m − 1) + 1.

Worked example: 4 processes each needing up to 3 units

Worst case 4 × 2 = 8 held. With 9 units one is spare, so no deadlock. With 8 units deadlock is possible. Minimum R = 9.

Now play with it

  • →Use the calculator with n = 4, m = 3 and change R.
  • →Ask: how many processes can 9 units support if each needs 3? (4).
Minimum R for deadlock freedom = n(m − 1) + 19
Is R = 9 enough?yes, deadlock-free
Most processes R can support (each needs m)4
Worst-case: units held while stuck8

Worst case: every process holds m − 1 units and wants one more. If one extra unit exists, someone can finish and free everything.

P1P2P3P4R1● ●R2● ●

Dashed red = request edge, solid green = assignment edge.

Cycle in the graph?yes
Deadlock?YES
Deadlocked processesP1, P2, P3, P4

Single instance per resource: a cycle means deadlock. Several instances: a cycle is necessary but not sufficient, so run the detection algorithm (find a process whose requests can be met, let it finish and release, repeat). Here that algorithm decides the answer.

Check yourself

Three processes each need 4 units of one resource. The minimum number of units that guarantees no deadlock is

Remember: R ≥ n(m − 1) + 1 for one resource type. Detection = Banker's with Request instead of Need.
Exam notes (the dense version)

Detection uses the same reduction as Banker's but with each process's current Request instead of Need; processes that can never finish are deadlocked. Recovery: kill all deadlocked processes, kill one at a time, or preempt resources and roll back. Classic counting question: n processes each needing at most m instances of one resource type; deadlock cannot occur if the number of resources R ≥ n(m − 1) + 1. With different needs mᵢ: R ≥ Σ(mᵢ − 1) + 1. The worst case gives everyone one fewer than they need.

Previous year questions: Deadlock (9)

PYQs are grouped by topic, so this is the full set for Deadlock; try the ones that match this subtopic. Open all 9 on the topic page.