GATE 2025 CS (CS2) – Question 48
$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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) Aborting $P_2$ makes the system deadlock free.; (D) Aborting $P_1$ and $P_4$ makes the system deadlock free.
Explanation
Build the wait-for relationships. Each process holds one resource (assignment edges $R_i\to P_i$) and waits for the resources in the claim edges:
- $P_1$ waits for $R_2$, held by $P_2$: $P_1\to P_2$.
- $P_2$ waits for $R_3$ (held by $P_3$) and $R_4$ (held by $P_4$): $P_2\to P_3$ and $P_2\to P_4$.
- $P_3$ waits for $R_1$, held by $P_1$: $P_3\to P_1$.
- $P_4$ waits for $R_2$, held by $P_2$: $P_4\to P_2$.
Cycles: $P_1\to P_2\to P_3\to P_1$ and $P_2\to P_4\to P_2$. **Both cycles contain $P_2$.**
- **(C)** Aborting $P_2$ removes both cycles: deadlock free. True.
- **(A)** Aborting only $P_1$ leaves the cycle $P_2\to P_4\to P_2$. False.
- **(B)** Aborting only $P_3$ leaves $P_2\to P_4\to P_2$. False.
- **(D)** Aborting $P_1$ and $P_4$ breaks both cycles ($P_1$ is in the first, $P_4$ in the second). True.
Answer: C, D.