The GATE Grind

GATE 2019 CS – Question 49

Operating System · Deadlock · 2 marks · Multiple choice

Consider the following snapshot of a system running $n$ concurrent processes. Process $i$ is holding $X_i$ instances of a resource R, $1\le i\le n$. Assume that all instances of R are currently in use. Further, for all $i$, process $i$ can place a request for at most $Y_i$ additional instances of R while holding the $X_i$ instances it already has. Of the $n$ processes, there are exactly two processes $p$ and $q$ such that $Y_p=Y_q=0$. Which one of the following conditions guarantees that no other process apart from $p$ and $q$ can complete execution?

  1. $X_p+X_q<\text{Min}\{Y_k\mid1\le k\le n,k\ne p,k\ne q\}$
  2. $X_p+X_q<\text{Max}\{Y_k\mid1\le k\le n,k\ne p,k\ne q\}$
  3. $\text{Min}(X_p,X_q)\ge\text{Min}\{Y_k\mid1\le k\le n,k\ne p,k\ne q\}$
  4. $\text{Min}(X_p,X_q)\le\text{Max}\{Y_k\mid1\le k\le n,k\ne p,k\ne q\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $X_p+X_q<\text{Min}\{Y_k\mid1\le k\le n,k\ne p,k\ne q\}$

Explanation

All $R$ instances are currently held, so nothing is free. Processes $p$ and $q$ have $Y_p=Y_q=0$: they need nothing more, so they can finish and release their instances. After both finish, the number of free instances is at most $X_p+X_q$.

Any other process $k$ can complete only if it can obtain its remaining need $Y_k$ from the free pool. So none of them can complete exactly when
$$X_p+X_q<Y_k\quad\text{for every } k\ne p,q,$$
which is the same as $X_p+X_q<\min\{Y_k\}$.

That is option (A). Option (B) uses the maximum, which would only block the process with the largest need, not all of them.

More Deadlock questions

All Deadlock questions →