GATE CS 2025 Set 2 Q.48: Deadlock Prevention, Avoidance and Detection

$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 \rightarrow P_1, \; R_2 \rightarrow P_2, \; R_3 \rightarrow P_3, \; R_4 \rightarrow P_4$ (the assignment edge $R_1 \rightarrow P_1$ means resource $R_1$ is assigned to process $P_1$ , and so on for others)

Claim edges: $P_1 \rightarrow R_2, \; P_2 \rightarrow R_3, \; P_3 \rightarrow R_1, \; P_2 \rightarrow R_4, \; P_4 \rightarrow R_2$ (the claim edge $P_1 \rightarrow 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?

Aborting $P_1$ makes the system deadlock free.

Aborting $P_3$ makes the system deadlock free.

Aborting $P_2$ makes the system deadlock free.

Aborting $P_1$ and $P_4$ makes the system deadlock free.

Official answer and solution

Official answer: C and D
From: Official GATE 2025 answer key

Solution

Construct the wait-for graph (since each resource has a single instance) and identify all directed cycles.

Since each resource $R_i$ has a single instance and is currently assigned to $P_i$ , a claim edge $P_a \rightarrow R_b$ corresponds to the wait-for edge $P_a \rightarrow P_b$ . The wait-for graph has 5 directed edges:

P_1 \rightarrow P_2, \quad P_2 \rightarrow P_3, \quad P_3 \rightarrow P_1, \quad P_2 \rightarrow P_4, \quad P_4 \rightarrow P_2

This graph contains exactly two elementary cycles:

$C_1: P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_1$
$C_2: P_2 \rightarrow P_4 \rightarrow P_2$

A set of aborted processes makes the system deadlock-free if and only if it intersects every cycle (a feedback vertex set):

Aborting only $P_1$ (A) or only $P_3$ (B) leaves cycle $C_2$ ( $P_2 \leftrightarrow P_4$ ) deadlocked.
Aborting $P_2$ (C) breaks both $C_1$ and $C_2$ , making the system deadlock-free.
Aborting $P_1$ and $P_4$ (D) breaks $C_1$ (via $P_1$ ) and $C_2$ (via $P_4$ ), also making the system deadlock-free.

Final answer

Options (C), (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 48 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source