GATE CS 2026 Set 1 Q.35: Deadlock Prevention, Avoidance and Detection

Consider a system consisting of $k$ instances of a resource $R$ , being shared by 5 processes. Assume that each process requires a maximum of two instances of resource $R$ and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.

The minimum value of $k$ for the system to be deadlock-free is ________. (answer in integer)

Your answer

Official answer and solution

Official answer: 6
From: Official GATE 2026 answer key

Solution

Find the maximum number of instances that can be held when all 5 processes are deadlocked, and add 1.

For $n = 5$ processes where each process requires a maximum of $m = 2$ instances of resource $R$ , a deadlock can occur only if every process holds at most $m - 1 = 1$ instance and is waiting for one more instance. The maximum number of instances held in such a deadlocked state is $n(m - 1) = 5 \times (2 - 1) = 5$ . Providing one additional instance guarantees that at least one process can acquire its second instance, finish, and release its resources:

k_{\min} = 5(2 - 1) + 1 = 6

Final answer

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

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 35 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