GATE CSE 2007 | Question: 58

Question

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?

• A. It does not ensure mutual exclusion.

• B. It does not ensure bounded waiting.

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

• D. It does not prevent deadlocks, but ensures mutual exclusion.

Comments

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.

---

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.

---

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

Answer 1

$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

Comments

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

---

@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 

---

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.

Answer 2

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.

Comments

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

---

@minal @Arjun tx both of you

Answer 3

Consider the following scenario for process P₁ .

Process P₁:-                                                                                           
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 ).

Comments

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 .

---

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.

Answer 4

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 

Comments

if both wants 1 = false and wants 2 = false than what will be result