It seems to me that this implementation is not correct.
Imagine the following sequence of thread scheduling on a single execution context:
We have three threads who all encounter Barrier A. T0 is the first thread to exit, and proceeds to enter Barrier B. It claims the lock, but since the leave counter is not yet 3, releases the lock and enters the while loop.
Next T1 exits (T2 still hasn't exited) and enters Barrier B. T1 claims the lock and increments arrive counter, then releases the lock. num_arrived is not 3, so T1 enters the else statement. The flag is not 0 because T0 still hasn't been able to set it, so T1 again claims and releases the lock exiting Barrier B before T2 has even exited Barrier A.
Am I correct in this assessment, or is there something I'm missing?
365sleeping
@jhibshma I believe the code is correct. As you mentioned, T0 got stuck in "wait for flag" loop and thus the flag has to be 0.
mallocanswer
@jhibshma, your analysis is good however you missed one thing here. While T0 is stuck in the while loop (while (b->leave_counter != p)), the b->arrive_counter is still 0. So T1 will also enter the while loop if T2 does not make any progress.
jhibshma
@mallocanswer -- Thanks, that makes sense.
MuscleNerd
Why is it said that leave counter is initialized to P? This seems to be confusing me.
fleventyfive
@MuscleNerd, the leave counter denotes the number of threads that have left the last barrier. So, it makes sense to initialize it to P.
fleventyfive
Also, shouldn't the last arriving thread set b->leave_counter to p and not 1?
rajul
@fleventyfive Yes it should be P.
MuscleNerd
if b->leave_counter = P initially won't the first condition i.e. if(b->leave_counter == 0) always become true and the b->flag will be set to 0 even though some threads may still be in the previous barrier. Instead if b->leave_counter = 0, it could be incremented until it becomes P (leaving the previous barrier) to set the flag.
Again I am NOT SURE if this is correct. Can someone please clarify?
rajul
@musclenerd Init would be called before the barrier is used for first time. So ya for the 1st time the condition will be true and the 1st arriving thread sets flag.Next time this condition will only be true if all threads have left the barrier(The last thread resets the values)
MuscleNerd
Oh! now i get it. Thanks a lot for the clarification! Super upvote.
It seems to me that this implementation is not correct.
Imagine the following sequence of thread scheduling on a single execution context:
We have three threads who all encounter Barrier A. T0 is the first thread to exit, and proceeds to enter Barrier B. It claims the lock, but since the leave counter is not yet 3, releases the lock and enters the while loop.
Next T1 exits (T2 still hasn't exited) and enters Barrier B. T1 claims the lock and increments arrive counter, then releases the lock. num_arrived is not 3, so T1 enters the else statement. The flag is not 0 because T0 still hasn't been able to set it, so T1 again claims and releases the lock exiting Barrier B before T2 has even exited Barrier A.
Am I correct in this assessment, or is there something I'm missing?
@jhibshma I believe the code is correct. As you mentioned, T0 got stuck in "wait for flag" loop and thus the flag has to be 0.
@jhibshma, your analysis is good however you missed one thing here. While T0 is stuck in the while loop (while (b->leave_counter != p)), the b->arrive_counter is still 0. So T1 will also enter the while loop if T2 does not make any progress.
@mallocanswer -- Thanks, that makes sense.
Why is it said that leave counter is initialized to P? This seems to be confusing me.
@MuscleNerd, the leave counter denotes the number of threads that have left the last barrier. So, it makes sense to initialize it to P.
Also, shouldn't the last arriving thread set b->leave_counter to p and not 1?
@fleventyfive Yes it should be P.
if b->leave_counter = P initially won't the first condition i.e. if(b->leave_counter == 0) always become true and the b->flag will be set to 0 even though some threads may still be in the previous barrier. Instead if b->leave_counter = 0, it could be incremented until it becomes P (leaving the previous barrier) to set the flag.
Again I am NOT SURE if this is correct. Can someone please clarify?
@musclenerd Init would be called before the barrier is used for first time. So ya for the 1st time the condition will be true and the 1st arriving thread sets flag.Next time this condition will only be true if all threads have left the barrier(The last thread resets the values)
Oh! now i get it. Thanks a lot for the clarification! Super upvote.