GATE 2025 CS2 Q.48: solution and answer

GATE 2025 · CS2Q.48 · 2 marks · MSQ

$P = {P_{1}, P_{2}, P_{3}, P_{4}}$ consists of all active processes in an operating system. $R = {R_{1}, R_{2}, R_{3}, R_{4}}$ consists of single instances of distinct types of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges: $R_{1} \to P_{1}, R_{2} \to P_{2}, R_{3} \to P_{3}, R_{4} \to P_{4}$ (the assignment edge $R_{1} \to P_{1}$ means resource $R_{1}$ is assigned to process $P_{1}$ , and so on for others)

Claim edges: $P_{1} \to R_{2}, P_{2} \to R_{3}, P_{3} \to R_{1}, P_{2} \to R_{4}, P_{4} \to R_{2}$ (the claim edge $P_{1} \to R_{2}$ means process $P_{1}$ is waiting for resource $R_{2}$ , and so on for others)

Which of the following statement(s) is/are CORRECT?

(A)
Aborting $P_{1}$ makes the system deadlock free.
(B)
Aborting $P_{3}$ makes the system deadlock free.
(C)
Aborting $P_{2}$ makes the system deadlock free.
(D)
Aborting $P_{1}$ and $P_{4}$ makes the system deadlock free.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct statements are (C) and (D).

Official answer: C, DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

Every resource has a single instance, so a cycle in the resource allocation graph means deadlock, and no cycle means no deadlock. Convert to a wait-for graph: $P_{i} \to P_{j}$ if $P_{i}$ waits for a resource held by $P_{j}$ .
Holders: $R_{1}$ is held by $P_{1}$ , $R_{2}$ by $P_{2}$ , $R_{3}$ by $P_{3}$ , $R_{4}$ by $P_{4}$ .
Waiting edges give: $P_{1} \to P_{2}$ (via $R_{2}$ ), $P_{2} \to P_{3}$ (via $R_{3}$ ), $P_{2} \to P_{4}$ (via $R_{4}$ ), $P_{3} \to P_{1}$ (via $R_{1}$ ), $P_{4} \to P_{2}$ (via $R_{2}$ ).
Cycles in the wait-for graph: $P_{1} \to P_{2} \to P_{3} \to P_{1}$ and $P_{2} \to P_{4} \to P_{2}$ . Both pass through $P_{2}$ .
(A) Abort $P_{1}$ : the edges $P_{2} \to P_{4}$ and $P_{4} \to P_{2}$ remain, so the cycle $P_{2} \leftrightarrow P_{4}$ remains. Deadlock persists. False.
(B) Abort $P_{3}$ : the edges $P_{2} \to P_{4}$ and $P_{4} \to P_{2}$ remain. Deadlock persists. False.
(C) Abort $P_{2}$ : it releases $R_{2}$ , $R_{3}$ and $R_{4}$ and withdraws its requests. Every cycle used $P_{2}$ , so the only edge left is $P_{3} \to P_{1}$ , which has no cycle. True.
(D) Abort $P_{1}$ and $P_{4}$ : both edges out of and into $P_{1}$ and $P_{4}$ disappear, so only $P_{2} \to P_{3}$ remains. No cycle. True.
Correct options: (C) and (D).

KEY IDEA

With single-instance resources, deadlock is exactly a cycle in the wait-for graph. Here both cycles pass through $P_{2}$ , so aborting $P_{2}$ breaks both. Aborting ${P_{1}, P_{4}}$ also breaks both, one process per cycle.

WATCH OUT FOR

Aborting only one process of the three-process cycle ( $P_{1}$ or $P_{3}$ ) and forgetting the second cycle $P_{2} \leftrightarrow P_{4}$ that does not contain it.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 6 Deadlock questions, with notes

GATE 2025 CS2 Q.48: solution and answer

Answer and solution

More Deadlock questions