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

thnks

 

---

This question is a variation of GATE CSE 2006 question Link
There they have asked necessary condition to guarantee that the system is not approaching a deadlock & here they have asked for conditions guarantees that no other process apart from and can complete execution(deadlock)

---

Free resources = Xp​+Xq​
If Free resources < minimum remaining need, then nobody else can complete.

Hence, Opt A is correct.

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

Say, there are 3 processes

$P_{1},P_{2},P_{3}$

Now, 

$P_{1}$ holding $1$ instances of resource R

$P_{2}$ holding $2$ instances of  resource R

$P_{3}$ holding $3$ instances of resource R

And R totally has $6$ resources

Now $P_{1}$ need some additional  instances

and $P_{2},P_{3}$ donot need any additional instances of $R$ , So, after releasing 5 instances of R is free.

Now $P_{1}$ must need minimum more than  5 instances

So, A)

 

 

---

@Shaik+Masthan

What about option C)?

I mean , if we check additional instances

Then P and Q not required any additional instances.

$Y_{P}=Y_{Q}=0$ (Given)

Then among $X_{P},X_{Q}$ one of them can be $0$ too

right?

---

srestha Option C isn't right as assume p and q are holding 4 and 5 instances of R now after executing these two processes, the processes will release these resources. Now if anyone of the remaining processes requires 3 additional resources then according to option C, it'll be executed apart from p and q  as Min(4,5) ≥ 3.

---

Can some one explain me this part of question with some example . I am unable to decode it . "Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1≤i≤n. "

---

@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.

---

example:

---

you can also think like this  let suppose i have process

precess  =>               p1,p2,p3,p4,p5.......pp , pq.......pn  and every process hold x instanse 
instanse hold =>        x1,x2,x3,x4,x5.......xp,   xq.........xn  now additional instance Y required while holding this
additinoal instanse =>y1,y2,y3,y4,y5.......0,    0............yn

when all process waiting for additional instanse pp and pq wil complete their task as the dont need anyh extra instanse.
now i have xp+xq  resourse which are free... for deadlock  this Xp+Xq  is always less then the additional instance 
we can write like this Xp+Xq < {min Yi where i not equal to p and q

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

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

---

Becoz Process p and q release its resouces , currently its requirement full , n need of min requirement , therefore Opt A is true

 

Answer 3

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 4

We have to ensure deadlock.

So, the soon-to-be-available resources ($X_p + X_q$) should not satisfy even the minimum demand of any other process.

Option A

Answer 5

{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

Comments

@air1ankit bhaiya thank you so much for this fantastic explanation!

Answer 6

P & Q does'nt require any additional resource & therefore they will complete their execution. After that, they will release there aquired resources.(Xp & Xq). Now these resources will be allotted to the process which need less than or equal to the sum of these resources. If only these two processed will complete it's execution & no other process will, then Xp+Xq < min(request  for resource by all the processes), this condition must be satisfied. Option A is correct.