ISRO CS 2025 Q.66: solution and answer

ISRO 2025 · CSQ.66 · 1 mark · MCQ

Analyze the below resource allocation graph. Which of the following is the corresponding wait-for graph?

ISRO CS 2025 question 66: Resource allocation graph with processes P1 to P5 (circles) and resources R1 to R5 (squares, one instance each). — Figure from the ISRO CS 2025 paper. It is part of the question.

(A)
Wait-for graph with edges P1->P2, P2->P5, P2->P3, P2->P4, P3->P4, P4->P1
(B)
Wait-for graph with edges P1->P2, P2->P5, P2->P3, P3->P4, P4->P1 (no edge P2->P4)
(C)
Wait-for graph with edges P1->P2, P2->P5, P2->P3, P2->P4, P4->P1 (no edge P3->P4)
(D)
Wait-for graph with edges P1->P2, P2->P5, P2->P3, P2->P4, P3->P4 (no edge P4->P1)

Answer and solution

ANSWER

Option (a) is the wait-for graph: $P_{1} \to P_{2}$ , $P_{2} \to P_{5}$ , $P_{2} \to P_{3}$ , $P_{2} \to P_{4}$ , $P_{3} \to P_{4}$ , $P_{4} \to P_{1}$ .

Official answer: ASource: ISRO's final answer key of 15 May 2026

In a resource allocation graph, an edge $P \to R$ means $P$ is requesting $R$ , and an edge $R \to P$ means $R$ is currently held by $P$ . A wait-for graph removes the resources and draws $P_{i} \to P_{j}$ when $P_{i}$ requests a resource that $P_{j}$ holds.
Read the holders from the graph: $R_{1}$ is held by $P_{2}$ , $R_{3}$ by $P_{5}$ , $R_{4}$ by $P_{3}$ , $R_{5}$ by $P_{4}$ and $R_{2}$ by $P_{1}$ .
Read the requests: $P_{1}$ requests $R_{1}$ ; $P_{2}$ requests $R_{3}$ , $R_{4}$ and $R_{5}$ ; $P_{3}$ requests $R_{5}$ ; $P_{4}$ requests $R_{2}$ . $P_{5}$ requests nothing.
$P_{1}$ requests $R_{1}$ , held by $P_{2}$ , so $P_{1} \to P_{2}$ .
$P_{2}$ requests $R_{3}$ (held by $P_{5}$ ), $R_{4}$ (held by $P_{3}$ ) and $R_{5}$ (held by $P_{4}$ ), so $P_{2} \to P_{5}$ , $P_{2} \to P_{3}$ and $P_{2} \to P_{4}$ .
$P_{3}$ requests $R_{5}$ , held by $P_{4}$ , so $P_{3} \to P_{4}$ . $P_{4}$ requests $R_{2}$ , held by $P_{1}$ , so $P_{4} \to P_{1}$ .
The wait-for graph has exactly six edges: $P_{1} \to P_{2}$ , $P_{2} \to P_{5}$ , $P_{2} \to P_{3}$ , $P_{2} \to P_{4}$ , $P_{3} \to P_{4}$ , $P_{4} \to P_{1}$ . Only option (a) shows all six. Option (b) lacks $P_{2} \to P_{4}$ , option (c) lacks $P_{3} \to P_{4}$ , and option (d) lacks $P_{4} \to P_{1}$ .

KEY IDEA

To convert a resource allocation graph (single-instance resources) to a wait-for graph, replace each path $P_{i} \to R \to P_{j}$ (request, then holder) by one edge $P_{i} \to P_{j}$ , and drop the resource nodes.

WATCH OUT FOR

Forgetting that one process can wait on several resources, so it contributes several edges (here $P_{2}$ has three outgoing edges). Another slip is to omit an edge that closes a cycle, such as $P_{4} \to P_{1}$ , or to miss $P_{3} \to P_{4}$ because $P_{3}$ and $P_{2}$ both request $R_{5}$ .

From the ISRO CS 2025 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Deadlock questions, with notes