5.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, wants$1$ and wants$2$ 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.

edited | 5.7k views
+4

@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

+9
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?
+3
@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.
+22

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.

+1

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

+3
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.
+1
In deadlock the process waits (infinite waiting) in waiting queue or Blocked State..isn't it?
0

I believe it isn't a Deadlock either. As far as I know Deadlock comes to picture if all the process are in Blocked state waiting for one another and none are in a position to use the CPU( ie. leaving the CPU idle). It seems to be like a spin lock as none of the processes are in BLOCK/WAIT state but all of them are spinning at the same point(i.e; at the start of the while loop) none entering the loop at taking the hold of Critical section.

0
bounded waiting is not with respect to time, but with respect to the number of times the processes enter the critical section before the intended process enters the critical section. If you want to decide whether there is bounded waiting in a deadlock situation then try to avoid deadlock in favour of the early arrival process. In this case suppose if p2 wants to get into C.S and P1 again wants to get into C.S then favouring P2 leads to bounded waiting, similarly for P1.

$P1$ can do wants$1$ $=$ true and then $P2$ can do wants$2$ $=$ 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 wants$1$ $=$ true (wants$2$ 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 wants$2$ $=$ 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.

by Veteran (422k points)
edited
+1

I Would Like to Add following point in regarding check for Bounded waiting:-

1. No process should have to wait forever to enter into the critical section.
2. There should be a bound on getting a chance to enter into the critical section.
3. Some process is indefinitely waiting to enter into CS because CS is always busy by some other process, this situation should not come.
4. If the bounded waiting is not satisfied, it is possible for starvation.

So even though P1 can come again and again in CS, but if P2 has also requested CS then P2 will waiting in while(wants1==true); loop, as soon as P1's wants1 become false even after many iterations, P2's while loop condition will break and P2 come in CS.

It seems like P2 never gonna enter in CS but P1 can't run infinitely, there will be some point when P1 will come out CS and make wants1=FALSE. So BW is satisfied.

+2

I have few points to say :

Point 1:

At first only P1 apply for critical section . As no other process in this time in critical section,so P1 can get critical section easily.

see below code snippet from given algo :
while (wants2 == true);  // there is a semicolon after while(), that means when condition is true inside while() it loop indefinitely .
And this condition is true as p2 makes ( wants2= true;) in the second line of it's code snippet .
 ..so P1 loop indefinitely and p1 can never enter into CS , it can only when (wants2=false;) but see the question again,
wants2=false; is done at end of P2 code snippet .
    /* Critical Section */   // after getting away from while() loop , P1 can enter into CS but this not gonna happen here.

-------

Point 2 :

P1 can executes like P1 P1 P1................[As still now P2 hasnot make any request]

in P2 code snippet , at second line you can see

 wants2 = true; is done by p2 means p2 has already make a request .

-------

Point 3:

Now, P2 made request , but P1 still in CS. So, P2 have to wait.[Here bounded waiting applied]

How p1 still in CS ? it can never go to CS due to indefinite loop ( to be specific due to " ; " after while() )

Can you tell me how much time P2 have to wait ?

or after how many P1 , then P2 can try to enter into it's own CS ?

-----

Point 4:

P1 can executes like P1 P1 P1.

can you say specifically how many times this p1 p1 p1 continue ? if you count how many times p1 execute then there BW is satisfied .[ again Galvin definition ]

-------

Point 5 :

after apply and before grant this P2 request, how many time P1 can execute?

P2 will wait for CS, until P1 comes out. So, bounded wait is 1 here

just few lines above you said it would be like p1 p1 p1 ... then how BW is 1 here ?

if BW is 1 then it must be only p1 , is not it ?

My sincere applogize for my arguments and wasting all your time . I would be happy if you clear my doubts .

Thanks.

0

@bikram sir
read the explanation of definition here ones https://stackoverflow.com/questions/33143779/what-is-progress-and-bounded-waiting-in-critical-section

and the second point even though p1 can run like p1 p1 p1 p1.....but at some point of time should return otherwise what is the use of that process p1 if it never returns? and as soon as it returns p2 is waiting for its chance will get CS.

BW will satisfy at last. I the only way this question BW does not satisfy that either one of the process keeps completing its section and never give other never get a chance.

Think can we get any of the process starve, if yes then BW doesn't satisfy otherwise it satisfies.

+1

@Bikram Sir,

Let me prove bounded waiting is satisfied in a reversed way first.  (Galvin definition only)

For this problem progress is not satisfied. We all agree on that.

As per progress definition if P2 is not in CS then P2 should not stop P1.
But here progress is not satisfied, so definitely P2 is stopping P1 from infinitely getting CS again & again when P2 wants it.
So it is proved.

Now let me prove it in a straight forward way.
-> Lets talk about the situation when both want CS but none is in CS.
There is a limit on a process entering in to CS,  none is entering CS so limit is not crossed.
-> When one process is in CS, if another process want CS.
P1 is in CS, OK P2 is in busy waiting   (Here we are not talking about time, we are talking about turns)
P1 is over & made want1=false,  immediately P2 will enter, because P2 was knocking the door from that time constantly, before P1 goes back & make want1=true before that P2 would be in CS.

I hope it clears everything.  I talked everything as per Galvin Definition only.

+1
@Ahwan, who said P2 will enter immediately ? P1 can continue without giving P2 a chance. Thats the point I am trying to make. Read my comment.
0

@Xylene

P1 is in CS, want2 is true from that time & P2 is constantly knocking the door of CS.  i.e in while loop.

Now tell me, to enter in to CS.... what P1 should do & what P2 should do..
P2 needs to do nothing, already want2 is true, it entered immediately...
P1 has a work to do, i.e to make want1=true......
So tell me can you make this operation in 0 time?  Tell me who will win the race ?

+3
So only one counter argument left.....
That what happens if P1 is executing executing executing.....
Here we are talking about "turns" as per Galvin definition.
Not time.... We assume all process takes finite time......So P1 will definitely stop, the moment it makes want1 to false, P2 will enter...

(P1 will run infinitely only if P2 does not want to enter at all & vice versa....This is not a problem as per Galvin definition, If one process wants CS, then only other process has a bound on number of turns.)
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
+7
@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 ?
+2

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

+1
@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
+7
@srestha, Its not strict alteration because P1 can keep on entering CS again and again as wants2=false.
+1

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

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.

0
i think progress is satisfied. we can check by the definition of progress
0
can anybody explain that progress is satisfy or not?
0

I believe it isn't a Deadlock either. As far as I know Deadlock comes to picture if all the process are in Blocked state waiting for one another and none are in a position to use the CPU( ie. leaving the CPU idle). It seems to be like a spin lock as none of the processes are in BLOCK/WAIT state but all of them are spinning at the same point(i.e; at the start of the while loop) none entering the loop at taking the hold of Critical section.

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.
by Boss (19.9k points)
+1
But B is false?
+3
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?
+1
"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 ?
+4
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

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.

by Boss (30.6k points)
0
if both wants 1 = false and wants 2 = false than what will be result

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

by Veteran (71.9k 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.
+3

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 .

0
I have spent 45 mins on it to understand difference b/w deadlock,BW ,livelock(NEW FOR ME).there is a grt differnce b/w deadlock and BW.now its clear.

Thank you both @vikram sir and also @xylene sir.

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

by Active (4.5k points)
+1 vote
This question is same as Interested variable, so interested variable don't guarantee  bounded waiting because it suffers from deadlock and deadlock is more severe than bounded waiting.

by Junior (515 points)
 /* P1 */ while (true) { wants1 = true; /*preempt here*/ while (wants2 == true); /* Critical Section */ wants1 = false; } /* Remainder section */  /* P2 */ while (true) { wants2 = true; /*preempt here*/ while (wants1 == true); /* Critical Section */ wants2=false; } /* Remainder section */ 

So, deadlock. (Technically, a livelock, because processes are "alive" — they're not doing anything, just busy-waiting forever. In deadlock, processes are blocked.)

Clearly, it guarantees Mutual Exclusion. Because, when the other process wants to enter the CS, the current process would not try to enter.

So, Option D.

Other options are wrong. No bounded waiting, because if a process wants to enter infinite times, it can. There's no "bound" (restriction) on the waiting time of the other process(es).

This also negates strict alteration.

by Active (1k points)