GATE CSE 2006 | Question: 78

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.

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

Comments

Binary Semaphore value can’t be initialized to 0. Then no process will be able to get in. Binary Semaphore is always set to 1, so only 1 process can get in to Critical Section at once.

---

Is it valid to consider two different barriers?

Barrier1 have 3 process p0,p1,p2. Barrier2 has 3 diff processes p3,p4,p5?

---

https://www.youtube.com/watch?v=NS9FdGk8PIY  for more better understanding

Answer 1

(B) is the correct answer.

Let $3$ processes $p_1, p_2 , p_3$ arrive at the barrier and after $4^{th}$ step process_arrived=3 and the processes enter the barrier. Now suppose process $p_1$ executes the complete code and makes process_left=1, and tries to re-enter the barrier. Now, when it executes $4^{th}$ step, process_arrived=4. $p_1$ is now stuck. At this point all other processes $p_2$ and $p_3$ also execute their section of code and resets process_arrived=0 and process_left=0. Now, $p_2$ and $p_3$ also try to re-enter the barrier making process_arrived=2. At this point all processes have arrived, but process_arrived!=3. Hence, no process can re-enter into the barrier, therefore DEADLOCK!!

Comments

I have got a doubt here. Will P1 execute for infinite number of times or only once. This doubt aroused because there is no mention of while(True) in the question. 

@Arjun sir.

@GateMaster Prime

---

the last process say p3 will make process_left and process_arrived =0 and thus when process arrived becomes 0,lets say p1 has went first made p_a=4,the p2 made it to 5 and then p3 finally made it 0 and went again to the first part making p_a=1...then whats happens is that on successive invocation of the barrier,before all the processes leave the second critical section will lead to the value in process_arrived to eb lesser always than the no of current processes..so even if all the processes comes at the barrier.the barrier condition will never become false(so that the processes could cross the barrier) as P_a will be lesser than the no of total processes.so they will be stuck busywaiting at the barrier as they pre-empt.Thus deadlock occurs.

---

If you would ask me how to stop this program from malfunctioning,we can do one thing.When the processes are leaving then until and unless all the processes have left,i.e the last process have left we should not allow the left process to reenter the first critical section towards the barrier.For this we can apply a barrier further at the end of the second critical section by—

while(process_left!=0); 

or equivalently

while(process_arrived!=0);

because when all the processes whill overcome the barrier (first) and is now in the second cs to leave as and when the first process will leave it will incremement process_left and that will only become 0 only when the last process comes out of the 2^nd CS.again the second code snippet for the 2^nd barrier(the process_arrived one) also works as only after all leaves p_a =0,not before that..

 

Til then the processes that left will busy wait and finally can leave.

Answer 2

Q.78 answer = option B

The implementation is incorrect because if two barrier invocations are used in immediate succession the system will fall into a DEADLOCK.

Here's how: Let all three processes make process_arrived variable to the value $3$, as soon as it becomes $3$ previously stuck processes at the while loop are now free, to move out of the while loop.

But for instance let say one process moves out and has bypassed the next if statement & moves out of the barrier function and The SAME process is invoked again(its second invocation) while other processes are preempted still.

That process on its second invocation makes the process_arrived variable to $4$ and gets stuck forever in the while loop with other processes.

At this point of time they are in DEADLOCK. as only 3 processes were in the system and all are now stuck in while loop.

Comments

So what to write in the above code to run the implementation correctly and where?

I think

While(process_left! =0);

Before line 1

....should be written.

---

very good explanation.

Answer 3

79. Which one of the following rectifies the problem in the implementation?

Ans : We should not allow to execute step 2 again(if any process attem to enter again when other two are not complete the 7^th statement )any process untill process arrived and process left==0.

Comments

if we keep this condition it will always work properly.

while(process_left!=0  && process_arrived == 0);

but I don't know it would be appropriate for option b,as it is asking to use process arrived.

---

Sir can we also solved this problem by putting the v (s) into  inside the if statement at last .and removed from line#11.

I think s=0 when all process comes in first invocation in cs. when p1 tries to enter in 2nd invocation it got blocked and same for p2.so we allow only when s=1 right na?

Pls correct me if I'm wrong.

I edited it , its wrong my bad! If its happened then how process p2 and p3 can execute line#5 . Sorry for little confusion from my side....!