GATE CSE
First time here? Checkout the FAQ!
x
+12 votes
2.4k 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 (64.6k points)   | 2.4k views

@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

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

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

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.

5 Answers

+26 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 (294k points)  
edited by
@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
@srestha, Its not strict alteration because P1 can keep on entering CS again and again as wants2=false.

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

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

 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.

http://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.

 

+10 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 Veteran (19.1k points)  
But B is false?
Sometimes it bothers me too... Getting more than one answers... But then I choose the one I feel is more close.
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?
"if bounded waiting not met then mutual exclusion also not met" This is not true. Where you saw this?
Bounded waiting not satisfied means one process is waiting indefinitely. So, obviously this process is not causing any harm to mutual exclusion.

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?

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.
sir , whats the problem with c).... it is similar to strict alteration method rt ?
alteration is not required here rt? P1 P1 P1 is possible rt?
oo , sorry ...  my mistake .... there is while ... yes it can be p1 p1....thanks
+5 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 Veteran (28.7k points)  
+4 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 Loyal (3.8k points)  
+3 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 (44.7k points)  
edited by
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.

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. 

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

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



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,650 answers
79,695 comments
31,069 users