retagged by
12,200 views
30 votes
30 votes

Consider the following snapshot of a system running $n$ concurrent processes. Process $i$ is holding $X_i$ instances of a resource $R$, $1 \leq i \leq 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 \mid 1 \leq k \leq n, k \neq p, k \neq q \}$
  2. $X_p + X_q < \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$
  3. $\text{Min}(X_p,X_q) \geq \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$
  4. $\text{Min}(X_p,X_q) \leq \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$
retagged by

7 Answers

40 votes
40 votes

The process $P$, holds $X_p$ resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds.

The process $Q$, holds $X_q$ resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds.

Total available resources after completion of $P$ and $Q = X_p + X_q$.

If these resources can not satisfy any process new requests, then no process will be able to completes it's execution.

$X_p + X_q < \text{ Min}\{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \} \implies$ delivers that no process going to completes except $P$ and $Q$. Answer is (A)

edited by
5 votes
5 votes
Process P and Q doesn't need any additional instances of resource R thus they can complete their execution and release the instances. Also initially there are no available instances of resource R. Thus after P and Q completes total available instances become $X_p + X_q$

If no more processes can complete their execution then the minimum requirement of all processes should be > ($X_p + X_q$)

Thus

Ans A) $X_p + X_q$ < min ( $Y_k, \forall \ k, k \neq P, k \neq Q$)
edited by
2 votes
2 votes
{P1, P2, ..., Pn}
Pi holds Xi instances.
Pi can request additional Yi instances.
Given two process p & q such that their additional requests are zero.
Yp = Yq = 0
{Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} means that out of 'n' processes, we are left with (n-2) process (except p&q), i.e., Yk indicates additional request of all the processes (n-2) except p & q.
For p & q to complete first, accordingly
Xp + Xq < Min {Yk}
Option A is correct.
There are exactly two process p and q which do not need any additional instances of resources.
So, p and q will complete their execution and will release Xp and Xq instances of resources.
Now to guarantee that no other process apart from p and q can complete execution, the no. of instances of resources available must be less than the minimum no. of instances of resources required by any other process, i.e.,
Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

 

 

For example, given by @srestha in one of the comment

P1,P2,P3,P1,P2,P3

Now,

P1 holding 1 instance of resource R

P2 holding 2 instances of  resource R

P3 holding 3 instances of resource R

And R totally has 6 resources

Now P1 need some additional  instances

and P2,P3,P2,P3 do'not need any additional instances of R , So, after releasing 5 instances of R is free.

Now P1 must need a minimum more than  5 instances

So, A
2 votes
2 votes
Xi → Holding resources for process pi,
Yi → Additional resources for process pi. 

As process p and q doesn’t require any additional resources, it completes its execution and available resources are (Xp + Xq)

There are (n – 2) process pi (1< i < n, i ≠ p, q) with their requirements as Yi (1 < i < n, i ≠ p, q).

In order to not execute process pi, no instance of Yi should be satisfied with (Xp + Xq) resources, i.e., minimum of Yi instances should be greater than (Xp + Xq).

So, option (A) is correct.

Answer:

Related questions

25 votes
25 votes
6 answers
1
40 votes
40 votes
4 answers
3
18 votes
18 votes
4 answers
4