Barriers in parallel computing

Question

I was reading about barriers found an example in Wikipedia. I have doubt whether it is correct. Here is the code from ( https://en.wikipedia.org/wiki/Barrier_(computer_science)#Implementation )

 struct barrier_type
    {
        // how many processors have entered the barrier
        // initialize to 0
        int arrive_counter;
        // how many processors have exited the barrier
        // initialize to P
        int leave_counter;
        int flag;
        std::mutex lock;
    };

// barrier for p processors
void barrier(barrier_type* b, int p)
{
    b->lock.lock();
    if (b->leave_counter == P)
    {
        if (b->arrive_counter == 0) // no other threads in barrier
        {
            b->flag = 0; // first arriver clears flag
        }
        else
        {
            b->lock.unlock();
            while (b->leave_counter != P); // wait for all to leave before clearing
            b->lock.lock();
            b->flag = 0; // first arriver clears flag
        }
    }
    b->arrive_counter++;
    int arrived = b->arrive_counter;
    b->lock.unlock();
    if (arrived == p) // last arriver sets flag
    {
        b->arrive_counter = 0;
        b->leave_counter = 1;
        b->flag = 1;
    }
    else
    {
        while (b->flag == 0); // wait for flag
        b->lock.lock();
        b->leave_counter++;
        b->lock.unlock();
    }
}

In barrier function, before entering the first if block, leave_counter is compared with P to check, whether it equals to P. Again in the else block, there is a comparison.

What is the reason for the second comparison, since the control entered only when leave_counter value is P? Am I missing something here?

You are seeing an example of the double-check locking pattern. http://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/ — Jim Rogers, Oct 19 '17 at 12:53
@Yadhunandana, Are you referring the while (b->leave_counter != P) test? — jwdonahue, Oct 19 '17 at 12:57
Is this C or C++ code? It's tagged C, but uses `std::mutex`, which is C++. They are *not* the same. — Andrew Henle, Oct 19 '17 at 13:12
It does look like this code is incorrect, though; there's a potential race between two "first arrivers" to clear and set `flag`. — Sneftel, Oct 19 '17 at 13:52

score 1 · Answer 1 · edited Oct 19 '17 at 13:43

1

The mutex is locked before the initial test of leave_counter, blocking all other threads.

If the caller is not the first to pass, it unlocks the mutex and then spin-waits in the
while ( b->leave_counter != P ), allowing the other threads to proceed.
Eventually, b->leave_counter == P and the caller proceeds.

edited Oct 19 '17 at 13:43

user3666197

1
6
50
92

answered Oct 19 '17 at 13:12

jwdonahue

6,199
2
21
43

Barriers in parallel computing

1 Answers1