gate zeal

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 n 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 below.

void barrier(void) {
    P(S);
    process_arrived++;
    V(S);
    while (process_arrived != n);
    P(S);
    process_left++;
    if (process_left == n) {
        process_arrived = 0;
        process_left = 0;
    }

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?

(a) The barrier implementation is wrong due to the use of binary semaphore S.

 (b) The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession

. (c) The barrier implementation is correct if there are only n-1 processes instead of n.

 (d) The barrier implementation is correct for the set of n processes

Comments

how dedlock is possible in this.

Answer 1

Option B:

The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession

isn't that mean : 

barrier();

barrier();

---

Let there are n processes namely 1 to n.

All processes are out from while (process_arrived !=n) of first barrier. --> process_arrived = n

1 to n-1 are entered second barrier after completion of first barrier.  --> process_left = n-1 and process_arrived may be n + 1 or n+2 or ....... n+(n-1) but not n

Therefore Now all those are struck at while(process_arrived !=n); 

 

Meanwhile, process $P_n$ take charge of semaphore and made process_left = n and process_arrived = 0.

Now entered into the 2nd barrier, made process_arrived =1 and struck at while(process_arrived !=n); with other processes.