Register
Dark Mode

GATE CSE 2007 | Question: 58

in Operating System edited by
27,483 views
57 votes
57 votes

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.

in Operating System edited by
by
27.5k views

4 Comments

Show 9 previous comments
by

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
0
by
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.
4
4
by
Answer is (D)

Strict alteration is not necessary, because after execution of P1, if it again wants to enter CS and P2 doesn't want to, P1 can again enter the CS.

The question actually is just a modified version of Algorithm #2 from Galvin's book (6th ed, Chapter 7: Process Synchronization).
0
0

10 Answers

86 votes
86 votes
Best answer

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

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

edited by
by

49 Comments

by
Sir plz explain how bounded waiting is not ensured here?
0
0
by
Explained..
2
2
by
@Arjun sir,

Take B = Bound on the number of processes which will enter critical section after a process has intended to enter critical section which is the definition of BW .

So, here B = 0 as no process can enter the CS .

So, Shouldn't the BW be satisfied ?
3
3
by

Yes, I agree...

@Arjun Sir, Correct me if I am wrong- 

Bounded waiting says that a bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

But, In your explanation about bounded waiting you did not mention about interest of P2.

Suppose P1 first enters critical section. After it leaves, say it again enters critical section while P2 is still waiting. This can go on forever causing P2 to starve and hence bounded waiting also is not satisfied.

If P2 wanted to enter into CS then it must have made wants2 = true, right ?? And now if P1 again wants to enter into CS then it can not get CS again because this time wants2 is true, so P1 will also be waiting in while loop for infinite time. 

3
3
by
If deadlock is satisfied, in that case bounded waiting is not satisfied. As BW says after finite waiting time process must come inside critical section
0
0
by

No srestha, Deadlock does not implies no bounded waiting.

And , 

As BW says after finite waiting time process must come inside critical section

I think, this is for starvation freedom not BW.

7
7
by
@vijay yes, I missed that. Corrected now..
1
1
by
If P1 is in CS and P2 also wants to enter into CS so it makes wants2 = True and in busy waiting in the while loop.

Now P1 makes wants1 = false but at the next cycle again makes wants1 = True.

Now at this stage both P1 and P2 will not able to enter critical section , there is deadlock.

Now as P2 wants to enter in CS but it has to wait infinitely So it could be a case where BW is also not satisfied.

Plese correct me if i am wrong...
1
1
by
@Arjun Sir, Do option B and C contradict each other? i.e. if B happens than C can't and if C happens than B can't. Please explain.
0
0
by
@Arjun Sir, I think vaishali's comment is right. Please see it. Even I think that bounded waiting is not satisfied here.
0
0
by
edited by

Xylene  

There is No relation between Deadlock and Bounded Waiting.

yes here Bounded waiting is Not satisfied , see my answer...

And  Swati Rauniyar 

yes, your assumption is correct.

option B says there is no BW ..and option C says there is BW ( means processes enter the critical section in strict alteration)  so both options are just opposite to each other.

3
3
by
This question is same as the question which I asked here https://gateoverflow.in/143607/does-this-satisfy-bounded-wait#c143940. I think bounded waiting is not satisfied . Sir, read @vaishali_jhalani 's reason.
1
1
by

@ Xylene 

yes, BW is not satisfied.. i answered separately.

Option B is correct as it is straight forward.

0
0
by
You can see bounded waiting definition in Galvin.
3
3
by

In @vijaycs commant

" If P2 wanted to enter into CS then it must have made wants2 = true "

Is that line correct?

how can we say wants2=true?

0
0
by

@Xylene

a bound must exist on the number of times that other processes are allowed to enter their critical sections

which process is entering CS after deadlock?

1
1
by

@ Arjun 

I have only one question .. the problem is here BW is satisfied or NOT .

 BW says there is a bound ( means a specific number of times you can enter into your CS after apply and before grant ur application) [ Galvin definition ]

so here when P1 willing to enter into CS  by  making ( wants1 = true;  )  and loop indefinitely ( due to "; " after while() loop ) then how many times it can enter into it's CS again before P2 enter into it's own(P2's)  CS ?

here is deadlock , it satisfied..[ even livelock or busywiting is kind of deadlock] so option D is correct in that respect.

But how option B is false ?

0
0
by
0
0
by
@Kapil ok got ur point :)
0
0
by
@Kapil, I saw your edited answer. You are saying that there is a bound of 1 on number of times another process gets access to CS after a process requests for CS .

You forgot about the granting of request in the definition .Here, although bound is 1 after a process requests for CS but request to CS is never granted to P2.

Check my comment above .
1
1
by

@Xylene @Bikram Sir

Why they are telling B) is incorrect , point is this.

 BW says there is a bound ( means a specific number of times you can enter into your CS after apply and before grant ur application) [ Galvin definition ]

Now, Say P1 and P2 two process in synchronization.

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.

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

So, no bounded waiting here.

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

Now see Galvin definition.

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

3
3
by

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
2
by

@ srestha 

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 .

which contradicts your opinion.

-------

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.

2
2
by

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

0
0
by

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

6
6
by
@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.
1
1
by

@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 P1 made want1=false....

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 ?

6
6
by
edited by
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.)
4
4
by
@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
0
0
by
edited by
@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 .
10
10
by
edited by

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
0
by
@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
0
by
edited by

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

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

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

1
1
by

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
0
by

 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.

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

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
0
by
what about option c?
0
0
by

Here, you have written that :

 

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

 

If wants2=true and P1 is in cs then if P2 tries to enter cs, it can enter since wants1=true and P1 is not out of the cs yet. Can you please clarify.

0
0
by

https://gateoverflow.in/8405/gate2015-3-10

There is a question in gate 2015 set 3. I have given the link above. 

My question is what is the difference between that question and this question?

0
0
by

Progress is satisfied,  lets say process P1 ran till remainder section, with wants1=false set so process P2 now enters into critical section and ran till remainder section. Now both processes P1 and P2 are in remainder part and critical section is empty

Process executing in remainder section and not interested to enter again should not block any other interested processes to enter the critical section as per Galvin, so in given code we can have any such state where any interested process can enter into critical section without being blocked by the changes done to shared variable by already exited process ,so interested process can make progress!! 

1
1
by
Consider the simple synchronization algorithm which denies entry to all processes.

In this case we have both deadlock and bounded waiting, since any process 𝑝p is not bypassed by some process 𝑝′p′ before entering the critical section, so you could say bounded waiting is satisfied with the constant function 𝑓=0.
2
2
by

@manish_dt Thats wrong. There is a deadlock here and Deadlock implies no progress, hence progress not satisfied. 

0
0
by

@Arjun sir , isn't it livelock here because both the process are continuously spinning around the instructions without proceeding further , but they are not in waiting state right ? Then it should be livelock 

0
0
by
Live lock means multple processes are stuck in loop.if there are multiple processes are using the same resources continueosly without any useful work.

In this question both are stuck in while loop.So livelock is possible.both are in stuck in waiting area.
0
0
14 votes
14 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.
by

4 Comments

Show 8 previous comments
by
alteration is not required here rt? P1 P1 P1 is possible rt?
7
7
by
oo , sorry ...  my mistake .... there is while ... yes it can be p1 p1....thanks
1
1
by

@minal @Arjun tx both of you

0
0
13 votes
13 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 ).

edited by
by

4 Comments

Show 2 previous comments
by
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
1
by

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 .

1
1
by
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.
0
0
12 votes
12 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 

by

1 comment

by
if both wants 1 = false and wants 2 = false than what will be result
0
0
Page:
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

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

Subjects

64.3k questions

77.9k answers

244k comments

80.0k users

Developed by Chun
Link Copied!