The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 votes

Consider the following snapshot of a system running $n$ processes. Process $i$ is  holding $x_i$ instances of a resource $R$, $ 1\leq i\leq n$ . Currently, all instances of $R$ are occupied. Further, for all $i$, process $i$ has placed a request for an additional $y_i$ instances while holding the $x_i$ instances it already has. There are exactly two processes $p$ and $q$ and such that $y_p=y_q=0$. Which one of the following can serve as  a necessary condition to guarantee that the system is not approaching a deadlock?

  1. $ \min(x_{p},x_{q})<\max_{k\neq p,q}y_{k}$
  2. $ x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$
  3. $ \max(x_{p},x_{q})>1$
  4. $ \min(x_{p},x_{q})>1$
asked in Operating System by Active (3.3k points)
edited by | 4.6k views

@Arjun Sir everywhere answer given is (B) but I cant understand how...

suppose 5 processes holding 1,2,3,4,5 resources respectively and request 0,0,3,7,8 resources respectively ... then process requesting 3 additional resources will get satisfied (available 1+2 =3) and total available resources will become 6(3+3). Now next process requests 7 which will not be satisfied and hence a deadlock will occur. shoud'nt the answer be xp+xq >=Max yk ? Please clarify...

Yes you are right Danish.. It answer can not be (B).. It is asking necessary condition to "GUARANTEE"... But it does not giving guarantee always, so all test cases are not passing in (B).. so there is a bug in (B) :D..

But if see (A), it looks odd and inefficient, but it passes all the test case for giving gurantee to be free from deadlock because it is freeing more than maximum requirement of the system!!

So it's answer is (A).. thanks for raising your doubt!!
How is A satisfying the conditions?

@Danish: The question asks for deadlock in the current state only. So, we need a condition to ensure that there is an allocation possible in the current state and don't need to consider whether a deadlock may occur in future. 

"can serve as  a necessary condition"

This means, without satisfying the condition there must be a deadlock. 

Ok got it "Necessary" NOT "Sufficient" ... Thanks :)
will anybody please explain the meaning of all the answer
Good question for understanding the meaning of necessary but not sufficient :)
Necessary condition not a sufficient condition

It means if that condition B: is satisfied it is not necessary there is no deadlock can happen but if condition B: is not satisfied than there will be definitely a deadlock it is guaranteed.

No Deadlock $\rightarrow$ Option (B)
@chottu @rahul can you explain all these options by taking example ?
I am not understanding clearly.please explain in another way.
Using Banker's Algorithm gives ans B
what could be the sufficient condition can anyone guess.
Necessary condition : resources released by completed process are good enough to satisfy need of any one of the remaining processes.


Sufficient condition : resources released by completed process are good enough to satisfy need of all remaining processes combined.

Sufficient condition here-

xp+xq>= (y1-1)+  (y2-1)+  (y3-1)+  (y4-1)+ .................  (yn-1)+ 1 


1 Answer

+39 votes
Best answer
B.  $x_{p}+x_{q}\geq \min_{k\neq p,q}y_{k}$

The question asks for "necessary" condition to guarantee no deadlock. i.e., without satisfying this condition "no deadlock" is not possible.

Both the processes $p$ and $q$ have no additional requirements and can be finished releasing $x_p$ + $x_q$ resources. Using this we can finish one more process only if condition B is satisfied.

PS: Condition B just ensures that the system can proceed from the current state. it does not guarantee that there won't be a deadlock before all processes are finished.
answered by Veteran (407k points)
selected by

min(xp,xq) < maxk≠p,q Yk

condition said it can prevent deadlock i.e. if xp or xq had more resource then addition resource

request by any process... but not always so this cant be ans... 


In lame language it says the suppose there is a chain of processes involved in a deadlock

Pi.....Pj and every process Pi has demanded for more resource(denoted by Yi) and this Yi may be different for each process Pi in the chain.

Now if there are two processes p and q which do not need any additional resources,

then they can complete and leave the system 

and after they leave the system, the combined resources allocated to both of them

i.e. Xp and Xq( Xp +Xq)

must be able to satisfy the additional resource demand of atleast one process (best case would always select the process demanding for least number of resources from among the set of processes involved in a deadlock)


Xp +Xq >= min (Yk) where K !=p,q

So , option (B)


k being equal to p or q would means yk = 0 as already mentioned in the question that yp and yq are both zero.

actually k != p or q means that process we are talking about is different from p and q.
sir please explain the meaning of all the given option ..if possible then give example @arjun sir
@arjun it is Banker's Algo right?
To absolutely ensure no deadlock, I think condition would be $x_{p}+x_{q}\geq \max_{k\neq p,q}y_{k}$ , isn't it?

And that is why Question asks for necessary  condition not sufficient.

nice explanation @Arjun sir this question is moving around necessary and sufficient condition

What should be the sufficient condition?

is it   $(x_p+x_q)\geq max_{k\neq p,q}(y_k)$

OR   $(x_p+x_q)\geq  \Sigma y_k$    ??


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,530 questions
54,139 answers
71,068 users