The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.7k views

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

 

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2=false;
}
/* Remainder section */

 

Here, wants1 and wants2 are shared variables, which are initialized to false.

Which one of the following statements is TRUE about the construct?

  1. It does not ensure mutual exclusion.

  2. It does not ensure bounded waiting.

  3. It requires that processes enter the critical section in strict alteration.

  4. It does not prevent deadlocks, but ensures mutual exclusion.

asked in Operating System by Veteran (59.4k points) | 3.7k views
+1

@arjun sir , this is the link from carniege mellon university . so we can trust the solution . see this link sir . 

https://www.andrew.cmu.edu/course/15-412/ln/412springlecture5.html . sir in this link ,see the last part of the page "broken solution #4" .In this link  they specified the live lock condition sir. They are saying that live lock is a special condition of dead lock in which the processes simply waste the cpu cycles by doing nothing and none of the processes  progress. 

The same scenario  matches here also. both the processes waste the cpu cycles by simply waiting in the while loop and none of the processes progress . so the most precise word will be live lock sir other than dead lock .the term dead lock creates confusion sir

+6
The usage of the word "livelock" is the reason for confusion -- what is the need for it when neither the question nor the options refer to it?
+2
@arjun sir, correct sir . in the question they didn't mention about livelock . but the above situation is live lock sir. we might get some questions related to live lock and it is necessary to distinguish between live lock and dead lock and this is the correct question to comment sir. so only i commented here sir.
+1
-> As per some definitions of deadlock,  it is livelock
-> As per some definitions, it is deadlock not livelock
-> As per some sources livelock is a type of deadlock

 As  Arjun Sir said,  here there is no need of involving livelock concept unless it is asked about livelock.
Bounded Waiting & Deadlock has multiple definitions which are contradicting each other in this particular question.   
But in GATE, either option or a hint will remove ambiguity.
+9

@Ahwan

The main difference between Live lock and Deadlock is :

 in livelock process keep executing and waste cpu cycles but in deadlock they are not executing at all .

+1

Exactly. I agree. :)
But livelock is a special case & not a very popular term like deadlock. As Arjun sir said, Unless mentioned we should not think about it to eliminate deadlock from option.

0

Read this section to understand livelock better:
https://en.wikipedia.org/wiki/Dining_philosophers_problem#Problems

0
In Livelock process involved don't make much progress, as when one process makes progress, another process may preempt this process and then later get preempted by some another process and so on.

 

But in deadlock, no process is able to make progress.

5 Answers

+40 votes
Best answer

P1 can do wants1 = true and then P2 can do wants2 = true. Now, both P1 and P2 will be waiting in the while loop indefinitely without any progress of the system - deadlock.

When P1 is entering critical section it is guaranteed that wants1 = true (wants2 can be either true or false). So, this ensures P2 won't be entering the critical section at the same time. In the same way, when P2 is in critical section, P1 won't be able to enter critical section. So, mutual exclusion condition satisfied.

So, D is the correct choice


Suppose P1 first enters critical section. Now suppose P2 comes and waits for CS by making wants2 = true. Now, P1 cannot get access to CS before P2 gets and similarly if P1 is in wait, P2 cannot continue more than once getting access to CS. Thus there is a bound (of 1) on the number of times another process gets access to CS after a process requests access to it and hence bounded waiting condition is satisfied.



https://cs.stackexchange.com/questions/63730/how-to-satisfy-bounded-waiting-in-case-of-deadlock

answered by Veteran (342k points)
edited by
0
@Bikram Sir time is worth utilizing with this discussion and thank u all for that :)

yes, P2 is already in CS, So, bounded waiting will be 1

@Ahwan has cleared this point

bounded waiting is not about how much time process will be in CS , but after the one process request how many turn other process will take before the request is granted.

Hope everything clear now
+3
@Xylene

After all these discussion, what i got to understand is :

We check BW is for each process , so here first we check for P1 BW is satisfied or not and then check for P2 BW is satisfied or not ?

yes, here definitely Deadlock exists , but we check deadlock for a system and not for a process . so when we check BW condition we don't consider for entire system rather we consider first process p1 then process p2 .

first check for P1 , it makes wants1==true // willing to enter into CS  

then

while (wants2 == true); // there is a loop , but it run finite amount of time because

after wants2== false P1 is out of loop and enter into CS [ as either p1 or p2 can start , so if p1 starts first and p1 can make wants2==false,  and get out of the while() loop . so p1 enter into it's CS ]

then  p1 is out of loop and P2 enter into CS by doing ( wants1==false) [ this is possible as when p1 is out of CS, it makes wants1==false. ]

so all what they try to say is after some finite amount of time p1 leaves p2 to enter into CS and hence Bounded waiting is satisfied.

And BW=1 as after 1 time p1 enter then p2 enter into CS !

And when we check BW, we don't consider that practical scenario that indefinite looping is here and deadlock satisfy so no progress ..we just need to check BW is satisfy for two process or not .

 

So , lets , end this discussion... enough of a day ... end of the day it is BW satisfied .
0

https://gateoverflow.in/39719/gate-2016-1-50

Sir CMU link(in ans) of bounded wait not working here, Can u chk it plz

0
@Bikram , I understood everyone's comment here . Bound is 1 if we ignore the "request granted" part in the definition. I am not fully satisfied with the answer. In my comment above, I gave the case exactly according to the definition in Galvin and BW is not satisfied. But according to gate it seems we must ignore the "granted part". (which is given in Galvin). @Arjun Sir, what do you say ?
0

@xylene

yes, there are 2 way we can define BW :

  1. in terms of time ( indefinite waiting , that the CMU link is talking about )
  2. in terms of number of other process in CS ( what we need to follow and given in book like Galvin )

For first case , you see deadlock is there so BW is not satisfy as there is indefinite waiting.

For 2nd case we just need to check for each process before it enter how many other process can enter into CS ( this is rather more simple way to check , here we don't consider that the system is in deadlock or no progress possible ..etc , we just check when a process request and before that request granted how many other process enter into CS ) .

yes, your assumption is correct, we don't consider the request granted part here , because if we assume that part p2 never enter into CS due to deadlock but if we don't consider there deadlock exists and simply check BW is satisfied or not then from that Galvin definition it can say BW is satisfied.

[ That means we assume , request is granted always ]

So what actually it means ? it means that when we check BW is satisfied or not for 2 process CS problem, we always check how many times other process can enter into CS before our requesting process enter. 

That's it. And no other point needs to consider.

You check https://gateoverflow.in/39719/gate-2016-1-50 , here also same policy applied.

Hope somehow you are convinced now.  

And @srestha

yes that CMU link is not working thta's why i uploaded that pdf, in my answer you can find that same pdf what that CMU link says.. ( they consider BW based on infinite time .. no process should wait for a resource for infinite amount of time) , which we don't consider as this makes unnecessary complication and we follow Galvin mostly for GATE exam.

 

0
@Kapil

" P2 is already in CS, So, bounded waiting will be 1 "

So, can we not say it is strict alteration of process P1 and P2

So, why option C) is incorrect?

@Bikram Sir chk this point
+1
@srestha, Its not strict alteration because P1 can keep on entering CS again and again as wants2=false.
0

@  srestha

It is 2 process CS problem indeed.. and whenever you see this 2 process CS problem most cases BW satisfied.

see the first line " Two processes, P1 and P2, need to access a critical section of code."

But yes, it is Not strict alternation as the reason p1 p1 p1 ..in CS, it is possible.

yes because of this possibility option C is not correct.

0

Sir

Say P1 is in CS.and and P2 wants to enter CS.

Now after P1 exit P2 will enter CS. Now it should be always true

As, wants2=true (this thing u also told in prev comment)

Now, if  we think about a queue P1 exit then it goes in queue after P2.

Then we can say P2 enters and P1 waiting for CS again.

and it will go on. Is it not strict alteration

how p1p1p1..possible then?

@Kapil plz chk this point

0

 srestha

there is busy waiting or livelock possible in this qstn .

when we consider BW , we just consider how many times other process enter into CS before our requestion process able to enter. That's it.. we dont consider there is busy wait or anything..

here p1 p1 p1 ..is possible due to that busy wait.. it is one of the possibility.

there is enough discussion on this..at last what we can say we shld mark only the obvious option. like here ME is satisfied and deadlock possibility is obvious.

https://gateoverflow.in/39719/gate-2016-1-50 here also same doubt occur .. see arjun's answer BW is satisfied ( due to galvin defibition) see that comment by @sushant , he showed correctly how BW dissatisfy as p10 ,p11 can not enter at all into CS..

 

so there are many possibility exists ..some are obvious and some are not, we should go with obvious possibility only.

 

+12 votes
The answer is D.

At the very 1st line itself you can see that it causes Deadlock.

Execute P1 till wants1=True; then Preempt.

Execute P2 till wants2=True; then Preempt P2 and let it enter into P1 and P1 into P2.

Since,

While (wants2==True);------------> This will lead to infinite loop. Coz of that semicolon, which makes the while loop terminate only when the condition inside the loop becomes False.

Similarly,

While (wants1==True);------------> Will also lead to infinite loop.

Hence the system is in Deadlock and Answer is D which is true.
answered by Boss (19.7k points)
+1
But B is false?
+2
Sometimes it bothers me too... Getting more than one answers... But then I choose the one I feel is more close.
–1
bounded waiting means one process is waiting for completion of another process. if bounded waiting not met , it can also not met mutual exclution. so why A is wrong?
0
"if bounded waiting not met then mutual exclusion also not met" This is not true. Where you saw this?
+3
Bounded waiting not satisfied means one process is waiting indefinitely. So, obviously this process is not causing any harm to mutual exclusion.
0

yes sir , if want 1 is active for P1 , then want2 cannot be active for P1 at the same time. So mutual exclusion met. Plz tell me sir it is deadlock because of while(true) loop. Am I right?

+1
Yes. You are right:
Deadlock: Both processes can be in the infinite while loop waiting.
Mutual Exclusion: In critical section for P1, wants1 is true meaning P2 cannot enter critical section. Similarly, for critical section for P2. So, mutual exclusion condition is met.
+1
sir , whats the problem with c).... it is similar to strict alteration method rt ?
+3
alteration is not required here rt? P1 P1 P1 is possible rt?
+1
oo , sorry ...  my mistake .... there is while ... yes it can be p1 p1....thanks
+9 votes

Deadlock can happen if preemption takes place :

both can fall into infinite loop.

But if one escapes that while condition then Mutual Exclusion is ensured.

answer = option D 

answered by Boss (30.6k points)
+6 votes

It ensures Mutual Exclusion as only one process can enter Critical section at a time

But it does not prevent deadlock as if both wants1 and wants2 becomes true it enters in deadlock state...

The Answer is D) 

 

answered by Active (4.5k points)
+6 votes

Consider the following scenario for process P1 .

Process P1:-                                                                                           
while(true)                                                                                                   

     {                                                                                                              
 wants1 = True; //   "I want to enter."                                                                                                

while (wants2 == true);   // "If you want to enter and if it's your turn I don't want to enter any more."                   

/* Critical Section */  //   Enter CS!                                                                                                     

wants1 = false; //  "I don't want to enter any more."   

          }                                                     

 

 this is the scenario. This  guarantee mutual exclusion . 

And  here is Deadlock . If no one either p1 or p2 can enter into CS then deadlock happen.

Hence correct option is option D ,  as both ME and Deadlock is satisfied here.

Also BW does not depends upon deadlock , not depends on progress, BW just says there is some bound exists .. so here in this question BW is satisfied as when p2 willing to enter it's CS by making  int[1]=True;  before that p1 enter into CS one time and after that p2 enter.

hence number of time a process enter into CS is 1 for requesting process p2.

B is not correct as we follow definition of BW based on ' number of times other process can enter into it's CS' .

when we follow Galvin definition of Bounded waiting, it satisfy BW in this question, which makes option B false .

 

see Algorithm #3   ( click the Blue Link )  This CMU link  , they refer BW based on time ( means no process should wait for a resource for infinite amount of time.)

But as in GATE like exam we follow standard books only we should go with Galvin definition ( means how many other process enter into CS before a particular process request to enter into it's CS and that request is granted ).

answered by Veteran (66.7k points)
edited by
+2
no- there is no lock release here and so it is deadlock and not livelock. Moreover, the bounded wait is not same as definite waiting time but follows the definition as in Galvin.
+2

Yes, Bounded waiting is satisfied as per the definition of "Bounded wait", there should be a limit on Count of other processes which can enter into CS. after a certain count a process will get its chance to get into CS. 

+1
Thanks both of you.. i understand it .

that CMU link i gave , they refer BW based on time , if we follow that convention then BW is not satisfied here as there is deadlock exists (or livelock or busy waiting ) .
+1

In one line , we can say this question is a "2 process" CS problem .

Strict alteration for 2 process system can never violate bounded waiting requirement .

Answer:

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

35,458 questions
42,701 answers
121,326 comments
42,104 users