Register

GATE CSE 2016 | Set 2 | Question: 48

• edited by
27,930 views
64 64 votes

Consider the following two-process synchronization solution.
$$\begin{array}{|l|l|}\hline \text{PROCESS 0 }  &  \text{Process 1 }\\  \\  \text{Entry: loop while (turn == 1); } & \text{Entry: loop while (turn == 0);} \\  \quad\text{(critical section)} &\quad \text{    (critical section)} \\ \text{Exit: turn = 1;} & \text{Exit turn = 0; }\\ \\\hline \end{array}$$

The shared variable turn is initialized to zero. Which one of the following is TRUE?

  1. This is a correct two- process synchronization solution. 
  2. This solution violates mutual exclusion requirement.
  3. This solution violates progress requirement.
  4. This solution violates bounded wait requirement.

10 Answers

Best answer
91 91 votes

There is strict alternation i.e. after completion of process $0$ if it wants to start again.It will have to wait until process $1$ gives the lock.
This violates progress requirement which is, that no other process outside critical section can stop any other  interested process from entering the critical section.
Hence the answer is that it violates the progress requirement.

The given solution does not violate bounded waiting requirement. 

Bounded waiting is : There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

Here there are only two processes and when process $0$ enters CS, next entry is reserved for process $1$ and vice-versa (strict alteration). So, bounded waiting condition is satisfied here. 

Correct Answer: $C$

• edited by
21 21 votes
Answer => C) why ?

B) Mutual exclusion is maintained.

D) Bounded waiting is there, as this is Strict alteration

C) This is correct. If Process 1 chose not to go in critical section, as it is strict alteration, process 0 can go in only once & then keep waiting forever. So Progress is not ensured !

A) This is false, because due to Progress not maintained !
5 5 votes

Explanation

 

First, you should understand the meaning of this statement :Entry: loop while (turn == 1);  it means that process can enter only in the critical section if the value of turn is 0 and vice versa for turn==0; 

 

A mutual exclusive requirement prevents simultaneous access to a shared resource. Since semaphore turn is initialized to zero and this semaphore value is changing only after the critical section for given processes. So, this ensures at most one process in the critical section at a time, i.e., the mutual exclusive requirement is satisfied.

Progress means that process should eventually be able to complete. But directly Process 1 can not go critical section as the lock value is 0 initially and this process 1 can go CS only after process 0. So, the progress requirement is not satisfied.

In other words, we define progress ->

Progress ->the process which does not wish to execute in the critical section should not be blocking other processes.

Easy way -The people who want to use the restroom would compete for the key, it should be not that the person who doesn't use it, locks and go away. So If process 0 do not wants to go to critical section and process 1 wants to, it cannot as process 1 depends on process 0 to make the turn =1 to unlock the critical section.


Bounded waiting means no process should wait for a resource for an infinite amount of time. Process 1 cannot go directly and Process 1 can go in critical after process 0 into the critical section. So, Bounded waiting is satisfied.

More simplified explanation ->process 0 will first enter critical section as the turn is false and after that exit: turn =1 then process 1 can access the critical section as now turn =1 after exit from process 0  so process 1 can now enter the critical section …..so both processes can go into critical section ( one by one a) , no process has to wait forever.

Option (C) is correct.

2 2 votes

please refer tp this solution

1 1 vote

THis is actually strict alteration and there is only two process so it never violates the Bounded wait (BOUNDED WAIT SATISFIED) but but here progress are not satisfied.

 

0 0 votes
Clearly there is no progress, as even if P2 does not want to enter in the critical section it is forced to enter

It is also known as strict alteration problem

There is mutual exclusion as at a time, only one process is allowed to enter the critical section.

There is bounded waiting, infact after every one turn, one of the process is schduled to enter the CS.
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2016 | Set ...Next → · GATE CSE 2016 | Set ...
← Previous in category · GATE CSE 2016 | Set ...Next in category → · GATE CSE 2016 | Set ...
Position:
Show:

Related questions

36 36 votes
2 answers 2 answers
14.4k
14.4k views
Akash Kanase asked Feb 12, 2016
14,381 views
GATE CSE 2016 | Set 2 | Question: 47
Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remain...
69 69 votes
15 answers 15 answers
26.9k
26.9k views
Akash Kanase asked Feb 12, 2016
26,921 views
GATE CSE 2016 | Set 2 | Question: 49
Consider a non-negative counting semaphore $S$. The operation $P(S)$ decrements $S$, and $V(S)$ increments $S$. During an execution, $20$ $P(S)$ operations and $12$ $V(S)...
141 141 votes
15 answers 15 answers
40.4k
40.4k views
Akash Kanase asked Feb 12, 2016
40,392 views
GATE CSE 2016 | Set 2 | Question: 30
Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two...
75 75 votes
8 answers 8 answers
27.7k
27.7k views
Akash Kanase asked Feb 12, 2016
27,738 views
GATE CSE 2016 | Set 2 | Question: 32
The width of the physical address on a machine is $40$ bits. The width of the tag field in a $512$ KB $8$-way set associative cache is ________ bits.