Detection, recovery, and the minimum-resources formula

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Need = ? from Lesson 4.1.2
2. Does an unsafe state mean deadlock? from Lesson 4.1.2
3. A cycle in a RAG with single-instance resources means? from Lesson 4.1.1

1 · The Hook

Most operating systems (Windows, Linux) do not run the banker's algorithm: it costs time and needs maximum demands in advance. Some simply ignore deadlocks and let the user restart a frozen program. Others check every so often whether a deadlock has formed and then break it. And there is one very quick calculation GATE loves: "how many resources make deadlock impossible?"

3 · Core Concept

Predict First — the answer

With 3: each grabs 1, all wait for a second unit that never comes → deadlock. With 4: whatever happens, someone can get 2 units, finish and release → no deadlock.

In plain words

Detection runs a check like the banker's safety test, but with the processes' current requests instead of their maximum needs: anyone whose current request can be met is assumed to finish and release. Whoever can never finish is deadlocked. Recovery then kills processes or takes resources away until the deadlock is gone.

1. Four strategies overall

1. Prevention (Lesson 4.1.2).
2. Avoidance (banker's).
3. Detection and recovery (this lesson).
4. Ignore it (the "ostrich" approach): used by most general-purpose OSes because deadlocks are rare.

2. Detection with single instances: wait-for graph

Remove the resource boxes from the RAG: draw Pi → Pj if Pi waits for a resource held by Pj. A cycle in the wait-for graph means deadlock.

3. Detection with multiple instances

Data: Available, Allocation, Request (what each process is asking for right now).

1. Work = Available. A process holding nothing is marked finished.
2. Find an unfinished process with Request ≤ Work; then Work += its Allocation; mark finished; repeat.
3. Processes still unfinished are deadlocked.

Example (types A, B, C; Available (0,0,0)):

P3 needs nothing → Work (0,0,1). P0 → (0,1,1). P1 → (1,1,2). P2 → (3,2,2). P4 → (4,3,3). Everyone finishes: no deadlock. If P0's request were (0,1,1) instead: after P3, Work = (0,0,1) and nobody else fits → P0, P1, P2, P4 are deadlocked.

4. Recovery

• Terminate processes: all deadlocked ones at once (simple, expensive), or one at a time until the cycle breaks (re-run detection each time).
• Pre-empt resources: pick a victim, take its resources, roll it back to a safe point; make sure the same process is not always the victim (starvation).

5. How many resources make deadlock impossible?

One resource type with R instances; process i needs at most kᵢ. Worst case: every process holds kᵢ − 1 and waits for one more. If even then one unit is left over, someone finishes. So: Deadlock is impossible ⟺ R ≥ Σ(kᵢ − 1) + 1.

• n processes each needing k: no deadlock ⟺ R ≥ n(k − 1) + 1.
• Needs 3, 4, 5: R ≥ 2 + 3 + 4 + 1 = 10.
• R = 6, each process needs 2: deadlock possible once n(2 − 1) ≥ 6, i.e. n ≥ 6.

4 · Visual

Why sum(k_i - 1) + 1 ?   Needs 3, 4, 5  (worst case: everyone one short)

P1 holds 2 (needs 3)   ██░
P2 holds 3 (needs 4)   ███░
P3 holds 4 (needs 5)   ████░
                       held = 2 + 3 + 4 = 9
With R = 9: nothing free  -> all wait: DEADLOCK possible
With R = 10: 1 unit free  -> someone completes, releases, everyone follows

5 · Worked Examples

Example 1 Easy

4 processes each need at most 3 units. Minimum number of units that makes deadlock impossible?

Solution

4 × (3 − 1) + 1 = 9.

Example 2 Medium

A system has 13 units; each process needs at most 4. What is the largest number of processes that can never deadlock?

Solution

n(4 − 1) + 1 ≤ 13 → 3n ≤ 12 → n ≤ 4.

Example 3 GATE

3 processes share 4 units of one resource; each may request up to K units. Largest K that guarantees no deadlock?

Solution

3(K − 1) + 1 ≤ 4 → K − 1 ≤ 1 → K = 2.

6 · GATE Traps

• The formula is Σ(kᵢ − 1) + 1, not Σkᵢ.
• Detection uses the current Request, avoidance uses Need (= Max − Allocation).
• A process that holds nothing can't be part of a deadlock.
• Wait-for graph only works when every resource has a single instance.

7 · Memory Hook

"Everyone one short, plus one spare: Σ(k − 1) + 1."

8 · Connect the Dots

Phase 4 is complete. Deadlocks are about resources in general; the most important resource of all is memory. Phase 5 covers how the OS shares memory: paging, page tables, TLBs and virtual memory.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Minimum resources

Processes P1, P2, P3 need at most 3, 4 and 5 units of one resource. Minimum number of units for which deadlock is impossible?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Minimum resources

3 processes each need at most 2 units. Minimum number of units that rules out deadlock?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Processes

A system has 6 identical units, and every process needs at most 2. What is the smallest number of processes that could deadlock?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Detection

In this lesson's detection example, P0's request is changed to (0, 1, 1). How many processes are deadlocked?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Wait-for graph

A wait-for graph is used for deadlock detection when:

1. (A) the banker's algorithm is running
2. (B) there are no cycles
3. (C) resource types have many instances
4. (D) every resource type has a single instance

10 · Rule Card

• Strategies: prevention, avoidance, detection + recovery, ignore (ostrich).
• Single instances: wait-for graph cycle = deadlock. Multiple: matrix detection with Request ≤ Work.
• Recovery: kill all / one at a time; pre-empt with victim + rollback (avoid starving one victim).
• No deadlock ⟺ R ≥ Σ(kᵢ − 1) + 1; n equal processes: R ≥ n(k − 1) + 1.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

ostrich approachwait-for graphdeadlock detection algorithmRequest matrixrecovery by terminationrecovery by pre-emptionvictim selection and rollbackminimum resources Σ(k − 1) + 1