GATE CS 2025 Set 2 Q38 — Deadlock

In a Resource Allocation Graph (RAG) where each resource type has a single instance, the presence of a cycle is a necessary and sufficient condition for a deadlock.

Let's identify the cycles in the given system by tracing the assignment edges ($R_i \rightarrow P_j$) and request/claim edges ($P_j \rightarrow R_k$):

• Cycle 1: $P_1 \rightarrow R_2 \rightarrow P_2 \rightarrow R_3 \rightarrow P_3 \rightarrow R_1 \rightarrow P_1$ (involves processes $P_1, P_2, P_3$)
• Cycle 2: $P_2 \rightarrow R_4 \rightarrow P_4 \rightarrow R_2 \rightarrow P_2$ (involves processes $P_2, P_4$)

To make the system deadlock-free, we must break both cycles:

• Option A (Aborting $P_1$): Only breaks Cycle 1. Cycle 2 remains active, so the system is still deadlocked.
• Option B (Aborting $P_3$): Only breaks Cycle 1. Cycle 2 remains active, so the system is still deadlocked.
• Option C (Aborting $P_2$): Since $P_2$ is common to both Cycle 1 and Cycle 2, aborting $P_2$ breaks both cycles. The system becomes deadlock-free.
• Option D (Aborting $P_1$ and $P_4$): Aborting $P_1$ breaks Cycle 1, and aborting $P_4$ breaks Cycle 2. Both cycles are broken, making the system deadlock-free.