edited by
8,242 views
42 votes
42 votes

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?

  1. Lines $6$ to $10$ are simply replaced by process_arrived--
  2. 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)$.
  3. Context switch is disabled at the beginning of the barrier and re-enabled at the end.
  4. The variable process_left is made private instead of shared
edited by

4 Answers

Best answer
45 votes
45 votes

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

edited by
23 votes
23 votes
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.
8 votes
8 votes
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 .
1 votes
1 votes

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.

Answer:

Related questions