FOR FREE CONTENT
Q. GATE-CS-2006 | Question 78
The 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.
voidbarrier (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 the 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 barriers in invocations are used in immediate succession.
(C) Lines 6 to 10 need not be inside a critical section.
(D) The barrier implementation is correct if there are only two processes instead of three.
Answer:
The above question is related to the barrier mechanism synchronization problem. (See Barrier Mechanism)
Option a is not correct because mutex is a binary semaphore is used to control the critical section. It never allowed more than one process at a time. So, binary semaphore could arise any problem.
Option b:
Now first we have to understand what option b says, it says
# What does the statement mean, when a set of 3 processes comes in the picture then line 4 (while loop) is true and go to next line 5 up(S) and increment-left = 1 (line 6) and goto line 7. here if the condition is not true because only one process is left.
# So, it goto the next line 10 and up(S), in the meantime, we assume another set of 3 processes try to run. Now S is up the first process of new set executes line 1 and go to CS. Increment process-arrived so, right process-arrived = 4 and down(S) (line 3) and assume that other two processes of the first set leave the barrier so, right now line 7 is true then it reset process-arrived = 0; process-left = 0 and up(S).
# Now the second process of the new set comes and executes line 1 2 3 and right now process-arrived = 1, and line 4 is false.
# And next time 3rd process of the new set is come and executes line 1 2 3 and process-arrived = 2 right now but line 4 while loop still not false because process-arrived still 2 now but three processes of the new set already come.
# The reason is we lost the increment of the first process of the new set. So, it gets deadlock because this set process never exits from the while loop because process-arrived never being 3.
So, Option b is correct.
Option C is incorrect because 6 to 10 should not be inside the critical section.
Option D is also incorrect because the barrier mechanism is possible for more than two processes.
Q. GATE-CS-2006 | Question 79
The 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.
voidbarrier (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.
Which one of the following rectifies the problem in the implementation?
(A) Lines 6 to 10 are simply replaced by process_arrived
(B) At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).
(C) Context switch is disabled at the beginning of the barrier and re-enabled at the end.
(D) The variable process_left is made private instead of shared
Answer:
The problem of the barrier implementation is it may lead to a deadlock if two barriers in requests are used in immediate succession i.e. before one group is finished one or more processors of another group can enter into the critical section which may lead to deadlock. (For more clear idea see the previous question)
Option A: This option is meaningless it change the method of actual barrier implementation even it is not a solution to prevent deadlock.
So, option A is incorrect.
Option B: Yes it an actual solution because all processes of the next group have to wait until all processes of the previous group complete their tusk and process_arrived becomes zero.
So, option B is incorrect.
Option C: This answer is not correct because if we stop the context switching at the being of the barrier then switch between one process to another process within the barrier will not possible.
So, option C is incorrect.
Option D: It is not the solution to process_left is private because if we make it private we cannot access it.
