CSS Prepare

optional · CSS study notes

Deadlocks — Solved Numericals

CSS Optional — Paper-II, Section-A · P-II.III.IV (numericals) · Worked past-paper problems for [Deadlocks]. Read the concepts page first (Coffman conditions, RAG rules, Banker's Algorithm data structures) — this page is pure practice.

Numerical 1 — Banker's Algorithm Safety Check (CSS 2022, 12 marks)

Given Claim (Max) matrix C, Allocation matrix A for 5 processes × 4 resources, Resource Vector = (12,13,6,8), Available = (0,3,0,1):

Need = Claim − Allocation:
P1=(2,0,0,0)  P2=(1,0,0,1)  P3=(0,2,0,1)  P4=(4,2,0,3)  P5=(2,1,1,1)

Safety trace (find a process whose Need ≤ Available, "run" it, release its Allocation back to Available, repeat):

Avail=(0,3,0,1): P1 needs R1=2>0 ✗   P2 needs R1=1>0 ✗   P3=(0,2,0,1)≤Avail ✓ → run P3
  release A[P3]=(3,1,2,2) → Avail=(3,4,2,3)
Avail=(3,4,2,3): P1=(2,0,0,0)≤Avail ✓ → run P1, release (3,1,1,3) → Avail=(6,5,3,6)
Avail=(6,5,3,6): P2=(1,0,0,1)≤Avail ✓ → run P2, release (2,2,1,0) → Avail=(8,7,4,6)
Avail=(8,7,4,6): P4=(4,2,0,3)≤Avail ✓ → run P4, release (0,4,1,0) → Avail=(8,11,5,6)
Avail=(8,11,5,6): P5=(2,1,1,1)≤Avail ✓ → run P5 — all finished.

Answer: the state is SAFE, with safe sequence P3 → P1 → P2 → P4 → P5.

Numerical 2 — RAG with Multiple Instances (CSS 2018, 8 marks)

Three processes PA, PB, PC; RA and RB have 1 instance each, RC has 2 instances. PA holds RC, requests RA. PB holds RA, requests RB. PC holds RB, requests RC.

Edges: RC→PA, PA→RA, RA→PB, PB→RB, RB→PC, PC→RC
Cycle exists: PA→RA→PB→RB→PC→RC→PA

Answer: NOT a deadlock. RC has 2 instances but only 1 is allocated (to PA) — a second instance of RC is free. PC's request for "an instance of RC" can be granted immediately from that free instance, so PC is not actually blocked. PC finishes → releases RB → PB finishes → releases RA → PA finishes. The cycle exists on paper, but the spare RC instance breaks its blocking effect — confirming that for multi-instance resources, a cycle is necessary but not sufficient for deadlock.

Numerical 3 — RAG with Single Instances (CSS 2021, 3 marks)

A cycle P1 → (resource) → P2 → R2 → P1 is shown, all resources single-instance.

Answer: this IS a deadlock. With single-instance resources, a cycle is both necessary and sufficient — P1 and P2 (and anything transitively depending on R2) are stuck in circular wait with no external process able to break it.

🎯 CSS Exam Angle

When a RAG question doesn't explicitly say "single instance" or "multiple instances," check the diagram for instance counts before answering — this single detail flips the correct answer (Numerical 2 vs 3 above). For Banker's Algorithm, always show the Need matrix calculation and the full safety trace step-by-step — the sequence itself is worth as many marks as the final safe/unsafe verdict.

⚠️ MCQ Traps

  • Cycle = deadlock is only guaranteed for single-instance resource graphs. For multi-instance graphs, always check for a free instance before concluding deadlock.
  • Avoidance (Banker's) requires processes to declare Max claims in advance — this is what distinguishes it from Detection (no advance declaration, just periodic cycle-checking after the fact).