Official PYQ · 2005Q71DeadlockMCQ1 mark

GATE CS 2005 Q71 — Deadlock

Suppose $n$ processes, $P_1, \dots P_n$ share $m$ identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process $P_i$ is $s_i$ , where $s_i > 0$ . Which one of the following is a sufficient condition for ensuring that deadlock does not occur?

View worked solution

Answer: C

To find the sufficient condition to prevent deadlock, we analyze the worst-case allocation scenario where a deadlock could potentially occur.

A deadlock occurs when every process $P_i$ has allocated some resources but cannot finish because it is waiting for more, and all $m$ resources are fully distributed.

The worst-case allocation where no process can complete its execution is when each process $P_i$ is allocated exactly $s_i - 1$ resources (one less than its maximum requirement). In this state, the total number of allocated resources is:

\sum_{i=1}^n (s_i - 1) = \sum_{i=1}^n s_i - n

If the total number of available resources $m$ is strictly greater than this worst-case allocation, then at least one process will be able to acquire its final required resource, run to completion, and release all its allocated resources back to the pool. This guarantees that deadlock cannot occur.

Therefore, for a deadlock-free system, we must have:

m > \sum_{i=1}^n s_i - n

Rearranging the terms, we get:

\sum_{i=1}^n s_i < m + n

Thus, Option C is the correct sufficient condition.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Deadlock questions

GATE CS 2005 Q71 — Deadlock

Related questions