5k 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 | 5k 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

+8
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.
+18

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

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

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

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

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

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

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.

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

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 .

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

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

1
2