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 instances are in use, so the only ones that can become free are those held by $p$ and $q$ once they finish (they need nothing more), giving $X_p+X_q$ free instances. No other process $k$ can complete if its additional need exceeds that amount, for every $k$, i.e. $X_p+X_q<\min_k Y_k$.