GATE 2026 CS (CS1) – Question 35
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
Let $P = 5$ be the number of processes.
Each process $i$ has a maximum resource demand of $M_i = 2$.
In the worst-case allocation where deadlock could potentially occur, every process is allocated 1 instance less than its maximum requirement:
$$\text{Worst-case allocated instances} = \sum_{i=1}^P (M_i - 1) = 5 \times (2 - 1) = 5$$
If $k = 5$, all 5 processes hold 1 instance of $R$ and are waiting for a 2nd instance. None can proceed, causing a deadlock.
With just 1 additional instance ($k = 5 + 1 = 6$), at least one process is guaranteed to receive its maximum requirement of 2 instances, complete its execution, and release both instances back to the system, allowing all remaining processes to finish.
$$\text{Minimum } k = \sum_{i=1}^P (M_i - 1) + 1 = 5 \times 1 + 1 = 6$$
The correct answer is 6.