Consider a system consisting of instances of a resource , being shared by 5 processes. Assume that each process requires a maximum of two instances of resource 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 for the system to be deadlock-free is ________. (answer in integer)
ANSWER
The minimum value of k for a deadlock-free system is 6.
Official answer: 6Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)
Deadlock needs every process to hold part of its need and wait for more, with no free instance left.
Each process needs at most 2 instances, so the worst case is that every process holds exactly 1 instance and waits for its second.
In that worst case the number of instances held is . With all instances are held and nobody can get a second one, so the system deadlocks.
With , even if all 5 processes hold 1 instance each, one instance is still free.
Give the free instance to one process. It now holds its maximum of 2, finishes and releases both, so 2 instances are free. The next process takes one, finishes, and releases 2, leaving 3 free, and so on until all 5 have finished. No process can wait forever.
General rule: deadlock-free if .
The minimum value of is 6.
KEY IDEA
The worst case for deadlock is every process holding one less than its maximum need. With one more instance than that total, some process can always finish, so .
WATCH OUT FOR
Answering 5 (one instance per process) or 10 (the sum of the maximum needs). Five instances can all be held with every process waiting for a second, which is a deadlock. Ten is enough but not the minimum.
From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 6 Deadlock questions, with notes
