Question

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)

Hint:

Consider the worst case where every process holds one instance and waits for a second; the minimum safe k follows k = n(m-1) + 1 with n=5 processes and m=2 max instances each.

Answer 1

Correct Answer: 6

Think about the worst case scenario that could lead to deadlock. Each of the 5 processes might grab 1 instance of R and then stall, waiting for a second instance, since it must hold the first before it can even ask for the second.

If there are only \(k=5\) instances total, this worst case is exactly what could happen: all 5 processes each hold 1 instance, all 5 instances are used up, and every process is now stuck waiting forever for one more instance that no one will ever release - a real deadlock, so \(k=5\) is not safe.

Now try \(k=6\). Even in the same worst case where all 5 processes have grabbed 1 instance each, using 5 of the 6 instances, there is still 1 instance left over. That spare instance can be handed to any one waiting process, letting it reach its maximum need of 2, finish its work, and release both instances back to the pool. Those freed instances then let the remaining processes proceed one after another, so the system never gets stuck.

This matches the general safe-allocation rule: for \(n\) processes each needing at most \(m\) instances, the deadlock-free minimum is \(k = n(m-1) + 1\). Plugging in \(n=5\), \(m=2\) gives \(k = 5(1) + 1 = 6\).