[SOLVED] When do you need more than 1 pthread barrier variable?

kvm1983 · 09-02-2009, 01:29 PM

Hello all
I am writing a multithreaded program using pthreads. I have a question abt the pthread_barrier functions, which are used to synchronize threads.

To give you a quick overview, to use pthread barrier functions,
a. declare a barrier variable alongwith its attribute and initialize it

Code:

pthread_barrier_t barrier1; 
pthread_barrierattr_t attr;
pthread_barrier_init(&barrier1, &attr, num_threads);

b. use it to synchronize threads

Code:

pthread_barrier_wait(&barrier1);

Now, I was wondering if one would ever need more than one barrier variable.
If you have something like

Code:

<some work>
pthread_barrier_wait(&barrier1);
<some work>
pthread_barrier_wait(&barrier1);
<some work>
pthread_barrier_wait(&barrier1);

you can use the same barrier variable barrier1. Can anyone tell me of a situation where I would need to use different barrier variables?

Thanks,
Kshitij

neonsignal · 09-02-2009, 08:19 PM

When you have more than two threads.

wje_lq · 09-02-2009, 10:07 PM

Quote:

Originally Posted by neonsignal

When you have more than two threads.

Nope. The number of threads to wait at the barrier is defined in the count parameter to pthread_barrier_init(). You could, for example, have one barrier, and have eight threads wait until all of them are at that barrier.

Whether you want more than one barrier depends on the complexity and structure of your program. If you can't think of a reason to use more than one barrier, then you need only one barrier.

neonsignal · 09-02-2009, 10:26 PM

Quote:

You could, for example, have one barrier, and have eight threads wait until all of them are at that barrier.

Yes, but not all the threads are necessarily synchronized together; one barrier is the minimal case, not the maximal one. You may be synchronizing in different groupings, in which case you will need more than one barrier.

The interesting question is what is the maximum number of barriers you could possibly need for a given number of threads. My intuition is n!/2, where n is the number of threads, but I suspect it might be more complicated than that, perhaps akin to a map coloring problem. I can't think of a situation in which a two-thread program would need more than one barrier, which I suspect is what the original poster was asking.

kvm1983 · 09-03-2009, 07:10 AM

Heres a complete program I found on the web that uses multiple barriers. Firstly, I dont understand what it is doing. Secondly, if you change the statement pthread_barrier_wait (&barriers[j]) to pthread_barrier_wait (&barriers[1]), the program hangs. Why? Shouldn't barriers[1] mean that only 2 threads should wait on the barrier and the rest can continue?

Thanks,
Kshitij

Code:

/* Test of POSIX barriers.  */

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NTHREADS 20

#define ROUNDS 20

static pthread_barrier_t barriers[NTHREADS];

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static int counters[NTHREADS];
static int serial[NTHREADS];

    static void *
worker (void *arg)
{
    void *result = NULL;
    int nr = (int) arg;
    int i;

    for (i = 0; i < ROUNDS; ++i)
    {
        int j;
        int retval;

        if (nr == 0)
        {
            memset (counters, '\0', sizeof (counters));
            memset (serial, '\0', sizeof (serial));
        }

        retval = pthread_barrier_wait (&barriers[NTHREADS - 1]);
        if (retval != 0 && retval != PTHREAD_BARRIER_SERIAL_THREAD)
        {
            printf ("thread %d failed to wait for all the others\n", nr);
            result = (void *) 1;
        }

        for (j = nr; j < NTHREADS; ++j)
        {
            /* Increment the counter for this round.  */
            pthread_mutex_lock (&lock);
            ++counters[j];
            pthread_mutex_unlock (&lock);

            /* Wait for the rest.  */
            retval = pthread_barrier_wait (&barriers[j]);

            /* Test the result.  */
            if (nr == 0 && counters[j] != j + 1)
            {
                printf ("barrier in round %d released but count is %d\n",
                        j, counters[j]);
                result = (void *) 1;
            }

            if (retval != 0)
            {
                if (retval != PTHREAD_BARRIER_SERIAL_THREAD)
                {
                    printf ("thread %d in round %d has nonzero return value != PTHREAD_BARRIER_SERIAL_THREAD\n",
                            nr, j);
                    result = (void *) 1;
                }
                else
                {
                    pthread_mutex_lock (&lock);
                    ++serial[j];
                    pthread_mutex_unlock (&lock);
                }
            }

            /* Wait for the rest again.  */
            retval = pthread_barrier_wait (&barriers[j]);

            /* Now we can check whether exactly one thread was serializing.  */
            if (nr == 0 && serial[j] != 1)
            {
                printf ("not exactly one serial thread in round %d\n", j);
                result = (void *) 1;
            }
        }
    }

    return result;
}


int main()
{
    pthread_t threads[NTHREADS];
    int i;
    void *res;
    int result = 0;

    /* Initialized the barrier variables.  */
    for (i = 0; i < NTHREADS; ++i)
        if (pthread_barrier_init (&barriers[i], NULL, i + 1) != 0)
        {
            printf ("Failed to initialize barrier %d\n", i);
            exit (1);
        }

    /* Start the threads.  */
    for (i = 0; i < NTHREADS; ++i)
        if (pthread_create (&threads[i], NULL, worker, (void *) i) != 0)
        {
            printf ("Failed to start thread %d\n", i);
            exit (1);
        }

    /* And wait for them.  */
    for (i = 0; i < NTHREADS; ++i)
        if (pthread_join (threads[i], &res) != 0 || res != NULL)
        {
            printf ("thread %d returned a failure\n", i);
            result = 1;
        }

    if (result == 0)
        puts ("all OK");

    return result;
}

neonsignal · 09-03-2009, 07:50 AM

The program sets up 20 threads. Thread 0 waits on barriers 0 to n-1 in turn, thread 1 waits on barriers 1 to n-1, thread 2 waits on barriers 2 to n-1, and so on. That is why the barriers are initialized with different counts. The program tests to make sure the barriers are working (ie, no thread gets through the barrier until the correct number have reached it). The second part is checking that only one thread is nominated for PTHREAD_BARRIER_SERIAL_THREAD.

Now if you change them to all wait on the barriers[1], you totally mess up the logic of the program. Having a barrier count of 2 doesn't mean that the rest continue, it means that they will be let through in pairs. Not only that, but some threads will get to the second half (where they reuse the same barrier) while others are going through the first part. The reason for the deadlock (despite the fact that there are an even number of waits in total) is because the last thread to get scheduled is probably getting stuck at the first of the barrier_waits after all the rest have returned. In theory it won't get deadlocked every time, but chances are pretty slim (the code sections are short, so it is quite likely that threads will never be preempted, and the sequence is somewhat predictable). If you got rid of the serial check stage, it would not deadlock.

kvm1983 · 09-03-2009, 02:19 PM

Quote:

Having a barrier count of 2 doesn't mean that the rest continue, it means that they will be let through in pairs.

Thanks, that explains it. I have one final question:
If you want only one thread (a designated master thread) to wait for all other threads to reach a point, such that the master thread waits and the other threads only pass that point, can this be implemented using pthread barriers?

Thanks for your help,
Kshitij

neonsignal · 09-03-2009, 03:28 PM

Quote:

If you want only one thread (a designated master thread) to wait for all other threads to reach a point, such that the master thread waits and the other threads only pass that point, can this be implemented using pthread barriers?

That sounds more like a semaphore wait, with the 'master' waiting for a signal (post) from each of the other threads.

Code:

master
for n times
   wait semaphore

n others
   signal semaphore

However, if this is a situation where the other threads are supplying unbuffered information to the master thread, it may be you don't want the other threads to go too far. For example:

Code:

master
loop
   do something else
   wait barrier // waits for data to be produced
   consume data // uses data
   wait barrier // allows other threads to produce data

others
loop
   produce data
   wait barrier // allows master to consume data
   do something else
   wait barrier // waits until data consumed

kvm1983 · 09-03-2009, 03:36 PM

Code:

master
for n times
   wait semaphore

n others
   signal semaphore

Got it. Thanks a ton.