Deadlocks

CSS Optional — Paper-II, Section-A · P-II.III.IV · The single most numerically-tested OS subtopic — a Banker's Algorithm or Resource-Allocation-Graph question is nearly guaranteed most years.

1. The Four Necessary (Coffman) Conditions

All four must hold simultaneously for deadlock to be possible:

1. Mutual Exclusion — at least one resource is held in a non-shareable mode.
2. Hold and Wait — a process holding a resource is waiting to acquire more, currently held by others.
3. No Preemption — resources can only be released voluntarily, never forcibly taken.
4. Circular Wait — a cycle of processes exists, each waiting for a resource held by the next.

2. Resource-Allocation Graph (RAG)

An edge Pi → Rj means Pi has requested Rj; Rj → Pi means Rj is allocated to Pi.

• Single-instance resources: a cycle in the RAG is both necessary and sufficient for deadlock.
• Multiple-instance resources: a cycle is necessary but NOT sufficient — you must check whether a free instance exists that could break the cycle by satisfying a pending request (worked example on the numericals page below).

3. Handling Deadlock — Four Strategies

Denying conditions for Prevention (the most-asked pairing):

• Deny Hold-and-Wait: require a process to request all resources it will ever need at once before starting (or release everything before requesting more).
• Deny Circular Wait: impose a strict, total ordering on all resource types; processes may only request resources in strictly increasing order — this makes a cycle structurally impossible.
• (Deny Mutual Exclusion and Deny No-Preemption are less commonly asked because many resources are inherently non-shareable/non-preemptible by nature — e.g. a printer.)

4. Banker's Algorithm (Deadlock Avoidance)

Data structures (n processes, m resource types): Available[m], Max[n][m] (each process's maximum claim), Allocation[n][m] (currently held), Need[n][m] = Max − Allocation.

Safety Algorithm: find some order in which every process's Need can be satisfied using Available plus resources released by processes finishing earlier in that order. If a complete such sequence exists, the state is safe.

Resource-Request Algorithm (when Pi requests Request[i]): (1) if Request[i] > Need[i] → error; (2) if Request[i] > Available → Pi must wait; (3) tentatively allocate (Available -= Request, Allocation += Request, Need -= Request); (4) re-run the Safety Algorithm — if the new state is safe, finalize the grant, else roll back and make Pi wait.

5. Deadlock Detection (when the system uses neither Prevention nor Avoidance)

Single-instance resources: maintain a wait-for graph (collapse the RAG's resource nodes — an edge Pi → Pj means Pi is waiting for a resource held by Pj). Periodically run a cycle-detection algorithm; a cycle means deadlock, and the processes on it are the deadlocked set.

Multiple-instance resources: an algorithm structurally similar to the Banker's Safety Algorithm, but using Request[n][m] (what each process is CURRENTLY requesting, not its maximum future claim) instead of Need:

1. Find a process Pi whose Request[i] ≤ Available.
2. If found, pretend it finishes: add its Allocation[i] back to Available, mark it "not deadlocked," and repeat from step 1 with the remaining processes.
3. If no such process exists among those still unmarked, every remaining unmarked process IS deadlocked.

When to invoke detection: either whenever a resource request cannot be immediately granted (detects deadlock as soon as it could have occurred), or at fixed intervals (less overhead, but deadlock may persist longer before being caught) — a trade-off worth stating explicitly if asked "when should the detection algorithm run?"

6. Recovery From Deadlock

Once detected, two broad recovery strategies:

7. Combined (Hybrid) Approach — a favourite "critique the strategies" exam angle

In practice, real OSes rarely commit to purely one strategy for every resource type. A common exam-winning observation: partition resource types into classes and apply prevention to resources naturally supporting it (e.g. an ordered class of internal kernel resources), avoidance where processes can reasonably declare max claims (memory), and simply the Ostrich Algorithm for everything else (matching what Windows/Linux actually do) — showing you understand deadlock handling as an engineering trade-off rather than a single memorized recipe is what separates a top-band answer from an average one.

---

📐 Worked Numericals

Banker's Algorithm and Resource-Allocation-Graph problems make up almost all of this topic's marks in past papers. Full step-by-step traces live on their own page:

Banker's Algorithm 12-mark safety-state check (2022), RAG with multiple instances (2018), RAG with single instances (2021).

---

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

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• All four Coffman conditions must hold together — a question listing only 2-3 conditions and asking "is deadlock guaranteed?" should be answered "no."
• Cycle = deadlock is only guaranteed for single-instance resource graphs. For multi-instance graphs, always check for a free instance before concluding deadlock (2018's exact trap).
• Avoidance (Banker's) requires processes to declare Max claims in advance — this is what distinguishes it from Detection (no advance declaration needed, just periodic cycle-checking after the fact).
• The Ostrich Algorithm is a legitimate, commonly-used real-world strategy (Windows/Linux use it) — don't dismiss it as "not a real technique" in a list-all-strategies question.
• Detection uses Request (current ask); Avoidance's Safety Algorithm uses Need (Max − Allocation) — mixing up which matrix belongs to which algorithm is a common written-answer error.
• Aborting all deadlocked processes vs one-at-a-time is a genuine cost/benefit trade-off, not a "correct vs incorrect" pair — name both and their trade-off rather than picking just one as "the" answer.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-II · Q4(a) and 2022 · Paper-II · Q3(a) · 8 and 12 marks

Q. Explain the Banker's Algorithm for deadlock avoidance. (2022: given a snapshot with Claim matrix C, Allocation matrix A, Resource vector and Available vector, decide whether the state is safe and give the completion order.)

Ans.

• Idea: the OS grants a request only if the system stays in a safe state (there is some order in which all processes can finish). Deadlock prevention restricts requests, but avoidance uses advance information about maximum needs.
• Data (n processes, m resource types): Available[m], Max (or Claim) [n × m], Allocation [n × m], Need = Max − Allocation.
• Safety algorithm:
  • Step 1: Work = Available; Finish[i] = false for all i.
  • Step 2: Find a process i with Finish[i] = false and Need[i] ≤ Work. If none exists, go to step 4.
  • Step 3: Work = Work + Allocation[i]; Finish[i] = true; go to step 2.
  • Step 4: If all Finish[i] = true the state is safe, otherwise unsafe.
• Resource-request algorithm for Request[i]: if Request ≤ Need and Request ≤ Available, pretend to allocate (Available −= Request, Allocation += Request, Need −= Request) and run the safety algorithm. If safe, grant the request. If unsafe, undo it and make the process wait.
• Worked example (5 processes, 3 resources): Available = (3,3,2). Allocation: P0 (0,1,0), P1 (2,0,0), P2 (3,0,2), P3 (2,1,1), P4 (0,0,2). Max: P0 (7,5,3), P1 (3,2,2), P2 (9,0,2), P3 (2,2,2), P4 (4,3,3). Need: P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1).

• Safe sequence: ⟨P1, P3, P4, P0, P2⟩, so the state is safe.
• For the 2022 snapshot: the matrices in the scan are not legible enough to read reliably. Apply exactly these steps: compute Need = Claim − Allocation, then repeatedly pick a process whose Need ≤ Available, add its allocation to Available, and record the order. If at some point no process qualifies, the state is unsafe, and the processes left over are the ones that could be deadlocked.

2017 · Paper-II · Q4(b) and 2020 · Paper-II · Q3(c) · 6 and 7 marks

Q. Discuss the four necessary conditions for deadlock. How can we deny any two of them? Why do deadlocks occur in multiprocessing and what techniques deal with them?

Ans.

• Four necessary conditions (all must hold together):
  • Mutual exclusion: a resource can be used by only one process at a time.
  • Hold and wait: a process holds some resources while waiting for others.
  • No pre-emption: resources cannot be taken away by force.
  • Circular wait: a closed chain of processes, each waiting for a resource held by the next.
• Denying hold and wait: a process must request all its resources at once before starting (or release everything before asking for more).
• Denying circular wait: number all resource types and require every process to request them in increasing order.
• Also: denying no pre-emption (if a request fails, the process gives up what it holds), and denying mutual exclusion by using sharable resources and spooling.
• Why in multiprocessing: many processes compete for a limited number of shared resources.
• Techniques: prevention (deny a condition), avoidance (Banker's algorithm), detection and recovery (find the cycle in the wait-for graph, then terminate processes or pre-empt resources), and ignoring it (the ostrich approach, used by most general-purpose systems).

2018 · Paper-II · Q4(A) · 8 marks

Q. Processes PA, PB, PC and resources RA (1 instance), RB (1), RC (2). PA holds one RC and requests RA. PB holds RA and requests RB. RB is allocated to PC, which requests an RC. Draw the resource allocation graph and say whether there is a deadlock.

Ans.

RC(1st) → PA → RA → PB → RB → PC ⇢ RC (request)
Edges: RC→PA (allocation), PA→RA (request), RA→PB (allocation),
       PB→RB (request), RB→PC (allocation), PC→RC (request)

• There is a cycle PA → RA → PB → RB → PC → RC → PA, but RC has two instances and only one is allocated (to PA).
• No deadlock: the second instance of RC is free, so PC's request is granted. PC finishes and releases RB. PB then gets RB, finishes and releases RA, and PA gets RA and finishes.
• No process is blocked permanently. Finish order: PC, PB, PA. (A cycle is a deadlock only when every resource in it has a single instance.)

2021 · Paper-II · Q4(c) · 3 marks

Q. Does the resource allocation graph shown consist of a deadlock? Justify.

Ans. (The figure is not legible in the scan, so the rule is given.)

• Single-instance resources: a cycle in the graph means deadlock.
• Multiple instances: a cycle means possible deadlock. Deadlock exists only if no process that is outside the cycle can finish and release an instance that a waiting process needs.
• For the figure: trace the request and allocation edges, check for a cycle (P1 → R2 → P2 → R1 → P1 style), then check whether P3 (which only holds a resource and requests nothing) can complete and release its instance. If it can, the cycle resolves and there is no deadlock. If not, the processes in the cycle are deadlocked.