Chapter 4.1 Lock-in

ACompressed recap

Four conditions (mutual exclusion, hold and wait, no pre-emption, circular wait). RAG: request P → R, assignment R → P; cycle + single instances = deadlock; multiple instances = maybe. Prevention: break a condition (resource ordering breaks circular wait). Avoidance: banker's, Need = Max − Allocation, safe sequence; unsafe ≠ deadlock. Detection: Request ≤ Work; wait-for graph for single instances. No deadlock ⟺ R ≥ Σ(kᵢ − 1) + 1.

BMerged rule card

4.1.1 Deadlock: the four conditions and resource-allocation graphs

• Deadlock: each process in a set waits for something only another in the set can give.
• Four necessary conditions: mutual exclusion, hold and wait, no pre-emption, circular wait.
• RAG: request P → R, assignment R → P. No cycle → no deadlock; cycle + single instances → deadlock; cycle + multiple instances → maybe.
• Starvation ≠ deadlock.

4.1.2 Prevention and avoidance: safe states and the banker's algorithm

• Prevention breaks a condition: all-at-once requests (hold and wait), pre-emption, resource ordering (circular wait).
• Safe state: some order lets everyone finish. Unsafe ≠ deadlock.
• Banker's: Need = Max − Allocation; Work = Available; pick Need ≤ Work; Work += Allocation; all finish → safe.
• Request: ≤ Need, ≤ Available, pretend, check safety; grant only if safe.

4.1.3 Detection, recovery, and the minimum-resources formula

• 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.

CInterleaved GATE-style questions

Q1 · MCQ · 1 mark(s) — Conditions

Which condition says a resource can't be taken away from the process holding it?

1. (A) No pre-emption
2. (B) Circular wait
3. (C) Hold and wait
4. (D) Mutual exclusion

Q2 · MCQ · 1 mark(s) — RAG

A resource-allocation graph has no cycle. Then:

1. (A) the system is unsafe
2. (B) the system is deadlocked
3. (C) the system is not deadlocked
4. (D) it depends on the number of instances

Q3 · NAT · 2 mark(s) — Banker's

One resource, 12 units. A holds 5 (max 10), B holds 2 (max 4), C holds 2 (max 9). How many units are free?

Numerical answer: ________

Q4 · MCQ · 2 mark(s) — Banker's

In the same state (12 units; A 5/10, B 2/4, C 2/9), C asks for 1 more unit. What happens?

1. (A) Granted: still safe
2. (B) C waits: the new state would be unsafe
3. (C) Granted: banker's never refuses
4. (D) Error: exceeds C's maximum

Q5 · MCQ · 1 mark(s) — Prevention

Making a process request all its resources before it starts breaks:

1. (A) hold and wait
2. (B) mutual exclusion
3. (C) circular wait
4. (D) no pre-emption

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

5 processes each need at most 3 units. Minimum units so that deadlock can never occur?

Numerical answer: ________

Q7 · NAT · 2 mark(s) — Maximum K

4 processes share 9 units; each needs at most K. Largest K that guarantees no deadlock?

Numerical answer: ________

Q8 · MCQ · 1 mark(s) — Detection

In the detection algorithm, a process is assumed able to finish when:

1. (A) it has the highest priority
2. (B) its Allocation ≤ Work
3. (C) its Max ≤ Work
4. (D) its current Request ≤ Work