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.