GATE CS 2015 Set 2 Q23 — Deadlock

To find the condition under which a deadlock can occur, we use the standard resource allocation inequality. For $N$ processes, each having a maximum demand of $M$ identical resources, with a total of $R$ resources available, the system is guaranteed to be deadlock-free if:

Since all processes have the same maximum demand $M$, this simplifies to:

A deadlock could occur if this condition is violated, i.e., when:

Let's analyze based on the maximum demand $M$:

• With $M = 3$ (Original GATE 2015 Exam Question):
  Here, $R = 6$ and $M = 3$. $$N(3 - 1) \ge 6 \implies 2N \ge 6 \implies N \ge 3$$ Thus, a deadlock can occur for any $N \ge 3$. Among the given options, $N = 4$ can lead to a deadlock (for example, two processes holding $2$ resources each, and two processes holding $1$ resource each, leaving $0$ free resources).
• With $M = 2$ (As printed in the question text):
  Here, $R = 6$ and $M = 2$. $$N(2 - 1) \ge 6 \implies N \ge 6$$ In this case, a deadlock is only possible if $N \ge 6$. None of the options $1, 2, 3,$ or $4$ would lead to a deadlock.

Aligning with the official GATE answer key, the intended question uses $M = 3$, making D the correct option.