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 be a binary semaphore with the usual and functions. Consider the following 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?
View worked solution
Answer: B
To understand why the barrier implementation is incorrect, let us trace a scenario with three processes and where two barrier invocations occur in immediate succession:
- First Invocation: All three processes call
barrier()and execute lines 1–3. The shared variableprocess_arrivedbecomes . - Passing the Loop: Since
process_arrived == 3, all three processes pass the busy-wait loop at line 4. - Fast Process Execution: Suppose is very fast. It executes lines 5–11, incrementing
process_leftto , and exits the first barrier. - Immediate Second Invocation: immediately calls
barrier()a second time. It executes lines 1–3, incrementingprocess_arrivedfrom to , and releases the semaphore . - Stuck at Loop: reaches line 4 of its second invocation:
while (process_arrived != 3);. Sinceprocess_arrivedis , gets stuck in this loop. - Reset by Others: Meanwhile, and complete their first barrier invocation. When the last process () executes lines 7–10, it resets both
process_arrivedandprocess_leftto . - Deadlock: Now, and enter their second barrier invocation. They increment
process_arrivedto and respectively, and both get stuck at line 4. Sinceprocess_arrivedis and all three processes are trapped at line 4, the system is deadlocked.
Thus, the implementation can lead to a deadlock if two barrier invocations are used in immediate succession.
Free practice · Your answers on this page are not saved.