Suppose n processes, P1, …. Pn share m identical resource units, which can be…
2005
Suppose n processes, P1, …. Pn share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process Pi is Si, where Si > 0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
Attempted by 37 students.
Show answer & explanation
Answer: The condition that the sum of all maximum requirements is less than m + n (i.e., sum_{i=1}^n Si < m + n) is sufficient to ensure deadlock cannot occur.
Proof (contradiction):
Assume a deadlock occurs. Let ri be the number of resources currently held by process Pi.
In a deadlock every process is waiting for more resources, so for each i we have ri < Si, hence Si - ri >= 1.
Summing over all processes gives sum(Si) - sum(ri) >= n, i.e. sum(Si) >= sum(ri) + n.
But sum(ri) = m (all m resources are allocated in a deadlock), so sum(Si) >= m + n, which contradicts the assumed condition sum(Si) < m + n.
Therefore deadlock cannot occur under the condition sum(Si) < m + n.
Note: This condition is sufficient but not necessary; deadlock might still be impossible in some cases when sum(Si) >= m + n, but the inequality guarantees no deadlock.
A video solution is available for this question — log in and enroll to watch it.