5.2k views

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?

1. The barrier implementation is wrong due to the use of binary semaphore $S$
2. The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession.
3. Lines $6$ to $10$ need not be inside a critical section
4. The barrier implementation is correct if there are only two processes instead of three.
edited ago | 5.2k views
+1
Op a is wrong because by using binary semaphore it works proper for three process

Op b is the ans because firstly three process enters and when while loop get executed it become false and get remove one process  and increase the count of process left

But still the process arrive has count=3

Now if next process try to enter like p4 get blocked due to while loop..

So infinity get blocked  and process inside also can't come outside so get blocked

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

edited by
+3
yes. right :) So, you should know how to fix it also rt?
+15
yupp.. :)
By not allowing the processes to enter the barrier, until process_arrive becomes zero.

That is, option B) is correct answer for Q.79
+2
Yes. But thats not an easy thing to do rt? What about A option?
+3
For option A) situation would be like when for first barrier invocation, all three processes are inside barrier then one of the process executed its section of code and trying to re-enter, it should not be allowed to enter until and unless all other processes are done. But for option A), it is allowed.That's why, its wrong.
Right sir?
0
What happens if there is a preemption after the following line... 6. pocess_left++; Please help me understanding the concept...
0
why not you are , entering process p2 and changing the process arrived = 5; for p2 ,and after p3  process arrived will become =0 so there is two count loss  ( P1 & P2 )
+1
Arjun Sir,

In the ist line before P(S) if we write " while(process_left !=0);" will it solve the problem? or if we write this before calling barrier function for a process ie.we won't allow any process to enter barrier unless process_left==0 ie. all processes have exited from previous barrier call. but in option B it is given process_arrived, but Sir say in the ist invocation P1 enters ad makes proces_arrived=1 now P2 will not be able to enter the barrier function since process_arrived !=0,it is 1 now.
0

Hi @GateMaster Prime ji

Now, when it executes 4th step, process_arrived=4

After this all process could go in infinite loop because of

while (process_arrived !=3);


Same is mentioned in the answer of  https://gateoverflow.in/43564/gate2006-79

0
I think its  easy.

Before line 1 include

While(process_arrive==3);
0
After line 6 if preemption occurs then remaining processes are not allowed to execute line no 6 and onwards.This working simply shows that implementation is following mutual exclusion from line 6 to 10.So that section works like an critical section.

Thus Option C becomes false
0
If P1 preempt after line 6...how others are not allowed ....please answer me sir.....
0

Line 6 to 10 must be kept inside the CS.

Suppose it wasn't kept then,

 P(S);
process_arrived++;
V(S);
while (process_arrived !=3);

process_left++;

if (process_left==3) {
process_arrived = 0;
process_left = 0;
}


Now let P1 executes process_left++; This is not an atomic operation. We know how it is implemented in machine language.

L1:reg1=process_left;
L2:reg1=reg1+1;
L3:process_left=reg1;

Suppose P1 preempts after L2.So reg1=1 and process_left remains 0 as reg1 is not stored back into it.

P2 executes process_left++ in the similar way and pre empts at L2 so reg2=1 and process_left=0.

Then P3 does the same thing and pre empts at L2 so reg3=1 and process_left=0.

Now again let P1 gets back control at L3 and process_left=reg1=1.

Similarly P2 executes L3 and process_left=reg2=1 and same does the P3 do so again process_left=reg3=1.

So now if(process_left==3) is never satisfied and process_arrived value remains 3 and process_left=1.

Let these processes again invoke Barrier, all of them will get stuck at

while(process_arrived!=3);as the process_arrived will be greater than 3 now. Hence Deadlock. So it is necessary to put the block from Line 6 to 10 inside CS so that this does not happen.

0
In critical section also premption takes place.if placed in critical section also it can happen right..so plz explaim

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.

+2
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.
0
very good explanation.

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 7th statement )any process untill process arrived and process left==0.

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

1
2