edited by
18,080 views
70 votes
70 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.

The above implementation of barrier is incorrect. Which one of the following is true?

  1. The barrier implementation is wrong due to the use of binary semaphore $S$
  2. The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession.
  3. Lines $6$ to $10$ need not be inside a critical section
  4. The barrier implementation is correct if there are only two processes instead of three.
edited by

3 Answers

Best answer
161 votes
161 votes

(B) is the correct answer.

Let $3$ processes $p_1, p_2 , p_3$ arrive at the barrier and after $4^{th}$ step process_arrived=3 and the processes enter the barrier. Now suppose process $p_1$ executes the complete code and makes process_left=1, and tries to re-enter the barrier. Now, when it executes $4^{th}$ step, process_arrived=4. $p_1$ is now stuck. At this point all other processes $p_2$ and $p_3$ also execute their section of code and resets process_arrived=0 and process_left=0. Now, $p_2$ and $p_3$ also try to re-enter the barrier making process_arrived=2. At this point all processes have arrived, but process_arrived!=3. Hence, no process can re-enter into the barrier, therefore DEADLOCK!!

edited by
23 votes
23 votes

Q.78 answer = option B

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.

11 votes
11 votes

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

Ans : We should not allow to execute step 2 again(if any process attem to enter again when other two are not complete the 7th statement )any process untill process arrived and process left==0.

Answer:

Related questions