edited by
14,767 views
42 votes
42 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.
edited by

8 Answers

Best answer
73 votes
73 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
18 votes
18 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 !
2 votes
2 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; 

 

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.

1 votes
1 votes

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.

 

Answer:

Related questions

15 votes
15 votes
4 answers
3