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

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) 
 

Answer 2

/* 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 */

Make a two-column table, for process 1 and process 2, we will keep a track of sequences of operations carried out by processes and prove the possibility of deadlock.

 

P1	P2
1,W1=1 //Wants1 = true, at timestamp 1	2,W2=1 //Wants2 = true, at timestamp 2
3,Busy waiting as W2==1.	4,Busy waiting as W1==1.

Check for bounded waiting

 

P1	P2
1, W1=1	4, W2=1 //Now P2 requests access to CS
2, CS // W2==0
3, W1=0
5, W1=1 // Immediately after P2’s requests, P1 tries to access CS again
6, Busy Waiting as W2==1, Hence, there is a bound on the number of times that other processes are allowed to enter their critical sections (in this case, P1 cannot enter until and unless P2  enters CS and sets W2==0) after a process have made a request to enter its critical section and before that request is granted

Hence bounded waiting satisfied

An extra step to check if starvation is possible

 

P1	P2
1, W1 = 1	//Gets starved as P1 keeps accessing the CS.
2, CS // W2==0
3, W1 = 0
4, W1 = 1 //and so on

Finally, the Mutual Exclusion
 

P1	P2
1, W1 = 1	4, W2 = 1 //Now, P2 wishes to access and no other process is in the CS
2, CS // W2==0	5, CS //W1==0
3, W1 = 0	6, W2 = 0

Similarly, if P2 accesses CS before P1, mutual exclusion remains satisfied, and in the third case, it can lead to deadlock.
Hence, option D.
 

Comments

A very silly doubt, but if this was msq would (b) also be correct? As if there is a deadlock, bounded wait also fails right?

Answer 3

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.

So answer (d) is the right answer.

Answer 4

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