GATE CSE 2019 | Question: 39

Question

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?

• A. $X_p + X_q < \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$
• B. $X_p + X_q < \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$
• C. $\text{Min}(X_p,X_q) \geq \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$
• D. $\text{Min}(X_p,X_q) \leq \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$

Comments

A is correct

---

https://gateoverflow.in/1844/gate2006-66

---

It's mentioned in the question,' process i can place a request for atmost Yi additional instances' . Isn't it possible to infer that process i need not require additional resource in some cases or requires less than Yi  ?

---

@Arjun sir, please add "Resource-allocation" tag on this question instead of  "process-synchronization" tag.

Answer 1

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)

Comments

@Shaik Masthan,

Very beautiful explanation. Thank You...!!!

---

Conclusion: Max available resource $X_p + X_q$ must not be able to solve minimum resource requirement → $\text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$ 

---

Conclusion :  Suppose all the X instances is Holding by the process ,and it requesting the Yi instances .
Given already that all Xi is given to the process , It must that Process p and Process Q also get the xp instances and xq instances . Then it not requesting other process of yp and yq ,Soon it will release the Xp and X q
Now after it release , We must sure that it should minimum then need of the Any Yi request then it will surely deadlock other wise it Sum of the Xp + xq is releasing the Yi request then we cannot it considered to be deadlock.

Answer 2

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$)

Comments

Why not C)?

---

Because the question asks for $no\ other\ process\ apart\ from\ p\ and\ q\ can\ complete\ execution$ and so if we select option C) it is possible that processes which require fewer resources than what is currently held by P or Q then once P or Q completes execution other processes will also be able to complete their execution.

$Y_k$ < $X_p$ or $X_q$ for any k = 1 to n,

implies some k processes can complete their execution once P or Q completes which is NOT asked in the question.

---

See $Y$ is additional resource, not the direct resource itself

So, when a process requires additional resource and $X_{P}+X_{Q}$ less than additional resource

That means that process couldn't complete execution.

So, it will be deadlock condition.

But is all process other than $P,Q$ need additional resource?

Because according to question $P_{3}$ already has $3$ resource and it needs $0$ to $3$ additional resource

right?

---

Yes it will be in an unsafe state and might possibly a deadlock situation.

Now coming to your questions

1. Because according to question $P_3$ already has 3 resources and it needs 0 to 3 additional resource

right?

$Process\ i\ is\ holding\ X_i\ instances\ of\ a\ resource\ R,\ 1≤i≤n$

The above statement can be written as "Process 0 is holding $X_0$ instances of a resource R, Process 1 is holding $X_1$ instances of resource R and so on. See here they have not specified any value so $X_i$ is any value for every $P_i$. .

Similarly this statement

"$process\ i\ can\ place\ a\ request\ for\ at\ most\ Y_i\ additional\ instances\ of\ R\ while\ holding\ the\ X_i\ instances\ it\ already\ has.$" - also doesn't specify any value for the additional resources. It just denotes $Y_0,Y_1,Y_2\ and\ so\ on$. 

2. "But is all process other than P,Q need additional resource?"

Also this line clearly says that other than processes P and Q rest all require additional resources.

$"Of\ the\ n\ processes,\ there\ are\ exactly\ two\ processes\ p\ and\ q\ such\ that\ $

$Y_p=Y_q=\ 0"$

Answer 3

{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

Answer 4

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.