GATE CSE 2006 | Question: 79

Question

Barrier is a synchronization construct where a set of processes synchronizes globally i.e., each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and $S$ be a binary semaphore with the usual $P$ and $V$ functions. Consider the following $C$ implementation of a barrier with line numbers shown on left.

void barrier (void) {

1 P(S);
2 process_arrived++;
3 V(S);
4 while (process_arrived !=3);
5    P(S);
6    process_left++;
7    if (process_left==3) {
8       process_arrived = 0;
9       process_left = 0;
10   }
11 V(S);

}

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

Which one of the following rectifies the problem in the implementation?

• A. Lines $6$ to $10$ are simply replaced by process_arrived--
• B. At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute $P(S)$.
• C. Context switch is disabled at the beginning of the barrier and re-enabled at the end.
• D. The variable process_left is made private instead of shared

Comments

Please write line numbers too in the code given in question.

---

Option D) will be false because every process will have their own version of process_left so process_left for every process will be 1. As a result, process_arrived variable will never to reset to 0. right?

---

Other part of this question ...

https://gateoverflow.in/1853/gate2006-78

---

For all those thinking why option A is wrong, read the statement once again:

“each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier.”

Now, For option 1, consider this case:

P1, P2, P3 are the processes.

First, All P1,P2, P3 executed till line no. 4.

So, process_arrived will be 3, and lets say P2 and P3 are preempted there, Only P1 proceeds execution. Now, According to option 1, process_arrived will be decremented, So, it becomes 2.

Now, Say P1 starts again (i.e. a new set), From line 1. Therefore, after line 2, it will make process_arrived again 3.

So, at line 4, the condition will be false (as process_arrived=3), and P1 can easily proceed execution, and enter critical section.

This voids the quoted line given in the question, as it does not wait for other processes in its set, (i.e. set no. 2)

So, Option a is wrong.

Answer 1

The implementation is incorrect because if two barrier invocations are used in immediate succession the system will fall into a DEADLOCK.

Here's how: Let all three processes make process_arrived variable to the value $3$, as soon as it becomes $3$ previously stuck processes at the while loop are now free, to move out of the while loop.

But for instance let say one process moves out and has bypassed the next if statement & moves out of the barrier function and The SAME process is invoked again(its second invocation) while other processes are preempted still.

That process on its second invocation makes the process_arrived variable to $4$ and gets stuck forever in the while loop with other processes.

At this point of time they are in DEADLOCK. as only 3 processes were in the system and all are now stuck in while loop.

Q.79 answer = option (B)

option (A) here is false as there will always be a need for some process to help some other process to move out of that while loop waiting. Not all processes together can be said to be completed at a time.

option (C) is false. If context switch is disabled then the process who was stuck in while loop will remain there forever and no other process can play a role in bringing it out of there as Context Switch will be required to bring that other process in the system to do the job.

option (D) is false. everyone will be in a loop forever, if that happens.

option (B) is TRUE. at the beginning of the barrier the $1^{st}$ process to enter Critical section should wait until process_arrived becomes zero(i.e. before starting its second invocation). this is to prevent it from making process_arrived value greater than $3$ i.e. rectifying the flaw observed in Q.78

Comments

Everything is ok for the first arrival, But let's consider that P1 has already completed the code while p3 and p2 are still in the lower critical section.

If the second arrival of P1 enters the upper Critical section, by the Time it reaches the while loop process_arrived may have been mode 0 by the lower CS if condition, and we will lose the synchronization of the second arrival of P1.

this will create a deadlock in the lower critical section for the second arrival of P2 and P3 will wait for p1 to make process_left to 3, where the upper critical section has ready processed the second P1.

---

Absolutely correct!

---

Yes @rohith, if we go in accordance with the definition of barrier given in the question, then a process after it’s 1^st traversal can traverse the code an infinite number of times without actually worrying about his fellow processes which violate the definition of Barrier. Hence, option A is incorrect. 

Answer 2

A is false. Consider that all processes arrived at barrier. Now suppose one of the process executed process_arrived-- & immediately again executed P(S); then process_arrived++; & then V(S); This would make process_arrived again equal to 3 and that particular process would again come out of barrier without waiting for other processes. This would be a failure of barrier implementation.

C is false. If context switch is disabled then the process which was stuck in while loop will remain there forever and no other process can bring it out since a Context Switch would be required to bring the other process in the system to do the job.

D is false. process_left of each process will become 3 after every three invocations of it, which in turn will make process_arrived equal to zero after every three executions of each process. That would lead to proper realization of barrier implementation only once (the first time). After one proper execution of barrier, it will no longer remain as barrier since process_arrived would become zero after every 3 executions of barrier by each process.

B is True. At the beginning of barrier() first process to execute remainder of barrier() should wait for process_arrived to become zero (if it was non-zero previously). This would prevent it from changing process_arrived value before it becomes zero after previous barrier synchronization. This would rectify the flaw observed.

Answer 3

if we keep this condition it will always work properly.

while(process_left!=0  && process_arrived == 0);

in given option it just gives hint to implement it, but not completely

So Option B is right .

Comments

great !

---

Could you please explain the code?

Won't this be sufficient
while(process_left!=0);

Thanks

---

Maybe this loop be sufficient?

while(process_arrived == 3);

Answer 4

As we know that the above implementation is incorrect because on immediate succession, it can lead to DEADLOCK. Please refer https://gateoverflow.in/1853/gate2006-78, if you are not able to understand, how DEADLOCK is possible.

Coming to options -

1. If we replace Lines 6 to 10 with process_arrive--, then it contradicts our implementation of Barrier. How? Suppose three processes p1, p2 and p3 arrive at the barrier. They enter the Barrier and will wait at Step 4, until all the processes have made into Barrier. Now, immediately p1 re-enter the Barrier (i.e. leaving the Barrier, which implies decreasing the process_arrive from 3 to 2 and re-enter the code again). At Step 2, it is going to increase the process_arrive back to 3, without waiting for other processes to leave the Barrier (in their previous iteration).
2. (Correct Option) As we have seen earlier, to prevent a DEADLOCK,  we need to make sure that the FIRST Process is not allowed to enter the Barrier again, if process_arrive is not equal to 0.
3. It is dangerous because Disabling Context Switching implies Disabling Interrupts. And, if we Enable Interrupts after Step 11, then every process is going to Starve. CPU will not allow to execute any other process other than the first process which entered the Barrier and this process is not going to execute due to While loop.
4. If making process_left private, then how we are going to maintain the no. of processes which left the Barrier. 

 

Therefore, Answer is B.