Implementation of a Barrier(a synchronization construct) using binary semaphore

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.

Will the above implementation work? I think it may lead to a deadlock if two barrier invocations are used in immediate succession as first process to enter the barrier doesn’t waits until process_arrived becomes zero before proceeding to execute P(S).

Answer 1

Hmm... restricted to three threads and only binary semaphores, I would be tempted to try this using three semaphores, A, B, C. A controls access to the process_arrived count, B and C are for the first and second threads to wait on. A is initialized to 1, B & C to 0. Thread 1 gets A, so preventing 2 & 3 from entering. A switch on process_arrived causes thread 1 to inc process_arrived, release A and wait on B. Thread 2 gets A, and the switch causes it to inc process_arrived, switch and so release A and wait on C. Thread 3 gets A and the switch causes it to signal B, signal C, set process_arrived to 0, signal A and continue on.

Threads 1 and 2 cannot pass B and C until 3 signals them. When B/C is signaled by 3, 1/2 can run but cannot loop back and get into the barrier until 3 releases A, at which point the barrier is in the correct state to act as a barrier again - A has a count of 1, B and C have zero and process_arrived is zero.

Answer 2

It is mentioned that there are 3 processes. Let it be P1, P2 & P3. Every process arrives at the barrier, that is it completes its first section of the code. Hence process_arrived = 3. Now assume that P1 continues its execution and leaves the barrier and makes process_left=1. Now assume that P1 again invokes the barrier function immediately. At this stage, process_arrived =4. P1 now waits. Soon P2 leaves the barrier, which makes process_left=2. Now P3 leaves the barrier which makes process_left=3. "If" condition is true and now process_arrived and process_left is reset to 0. We know that P1 is waiting. At this stage assume that P2 invokes the barrier function, hence process_arrived=1 and it waits. P3 invokes the barrier function, hence process_arrived=2. All process have reached the barrier but since the process_arrived=2, all processes keeps on waiting. Hence deadlock.