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

Step 1: There are 5 processes, each needing a maximum of 2 instances of resource R, and each process can request or release only one instance at a time, meaning it must acquire the first instance before it can request the second.

Step 2: The standard sufficient condition to guarantee no deadlock in such a system is \[k \geq \sum_{i=1}^{n}(\text{max}_i - 1) + 1\] where \(\text{max}_i\) is the maximum demand of process \(i\) and \(n\) is the number of processes. This guarantees that even in the worst case, at least one process can always obtain its full requirement and complete, releasing resources for the others.

Step 3: Here \(n = 5\) and \(\text{max}_i = 2\) for every process, so \(\sum (\text{max}_i - 1) = 5 \times (2-1) = 5\).

Step 4: Adding 1 gives \(k \geq 5 + 1 = 6\).

Step 5: Intuitively, with \(k = 5\) it is possible for every process to hold exactly 1 instance each, using up all 5 instances, after which all 5 processes are stuck waiting for a second instance - a genuine deadlock. With \(k = 6\), even if all 5 processes each hold 1 instance, there is still 1 free instance, which can be given to some process so it reaches 2 instances, finishes, and releases both, breaking any potential deadlock.

Final Answer: \[\boxed{k_{\min} = 6}\]