Skip to content
GATEiit

GATE CSE 2025 Session 2 Q48: Which process aborts make a resource graph deadlock-free

Question

P={P1,P2,P3,P4}P = \{P_1, P_2, P_3, P_4\} consists of all active processes in an operating system.

R={R1,R2,R3,R4}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: R1→P1R_1 \to P_1, R2→P2R_2 \to P_2, R3→P3R_3 \to P_3, R4→P4R_4 \to P_4 (the assignment edge R1→P1R_1 \to P_1 means resource R1R_1 is assigned to process P1P_1, and so on for others)

Claim edges: P1→R2P_1 \to R_2, P2→R3P_2 \to R_3, P3→R1P_3 \to R_1, P2→R4P_2 \to R_4, P4→R2P_4 \to R_2 (the claim edge P1→R2P_1 \to R_2 means process P1P_1 is waiting for resource R2R_2, and so on for others)

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

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: C, D (official GATE 2025 final answer key)

Concept used: With single-instance resources, a deadlock is exactly a cycle in the wait-for graph.

First step: Build the wait-for graph: P1→P2P_1 \to P_2, P2→P3P_2 \to P_3, P3→P1P_3 \to P_1, P2→P4P_2 \to P_4, P4→P2P_4 \to P_2, and find every cycle.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key