GATE CS 2019 Q.49 (CS Q.39): Process Synchronization and Concurrency

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?

$X_p + X_q < \text{Min}\{Y_k \mid 1 \le k \le n, k \ne p, k \ne q\}$

$X_p + X_q < \text{Max}\{Y_k \mid 1 \le k \le n, k \ne p, k \ne q\}$

$\text{Min}(X_p, X_q) \ge \text{Min}\{Y_k \mid 1 \le k \le n, k \ne p, k \ne q\}$

$\text{Min}(X_p, X_q) \le \text{Max}\{Y_k \mid 1 \le k \le n, k \ne p, k \ne q\}$

Official answer and solution

Official answer: A
From: Official GATE 2019 answer key

Solution

Determine the resource availability threshold after processes p and q finish that prevents any other process from satisfying its maximum claim.

We are given that initially all instances of resource $R$ are in use, so the number of available instances is $0$ .

Processes $p$ and $q$ have additional requests $Y_p = Y_q = 0$ . Since they require $0$ additional instances, both $p$ and $q$ can immediately finish execution without needing any further allocation.

When $p$ and $q$ complete execution, they release the instances they were holding, which are $X_p$ and $X_q$ respectively.
Therefore, the total number of newly available instances of $R$ in the system is:

\text{Available} = X_p + X_q

For any remaining process $k \notin \{p, q\}$ to be able to execute, its additional request $Y_k$ must be less than or equal to the available instances.
If the total available instances $X_p + X_q$ is strictly less than the minimum additional demand among all other processes:

X_p + X_q < \text{Min}\{Y_k \mid 1 \le k \le n, k \ne p, k \ne q\}

Then no remaining process can have its request satisfied. Every remaining process will be permanently blocked, guaranteeing that no process other than $p$ and $q$ can complete execution (Option A).

Final answer

Common trap

Choosing Max instead of Min (if X_p + X_q < Max, some process with smaller Y_k could still run).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 49 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source