Register

GATE CSE 2007 | Question: 58

• edited by
48,554 views
91 91 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.

14 Answers

Best answer
114 114 votes

$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
17 17 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
16 16 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.
13 13 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 

6 6 votes

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) 
 

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

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2007 | Ques...Next → · GATE CSE 2007 | Ques...
← Previous in category · GATE CSE 2007 | Ques...Next in category → · GATE CSE 2007 | Ques...
Position:
Show:

Related questions

28 28 votes
5 answers 5 answers
10.5k
10.5k views
go_editor asked Apr 23, 2016
10,544 views
GATE CSE 2007 | Question: 83
A process, has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequenc...
37 37 votes
4 answers 4 answers
18.0k
18.0k views
Kathleen asked Sep 21, 2014
17,951 views
GATE CSE 2007 | Question: 57
A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following ...
53 53 votes
4 answers 4 answers
26.4k
26.4k views
Kathleen asked Sep 21, 2014
26,409 views
GATE CSE 2007 | Question: 56
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:P: I...
36 36 votes
6 answers 6 answers
14.0k
14.0k views
Kathleen asked Sep 21, 2014
13,967 views
GATE CSE 2007 | Question: 55
An operating system used Shortest Remaining System Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following process...