LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 09-02-2009, 02:29 PM   #1
kvm1983
Member
 
Registered: Jul 2009
Posts: 47

Rep: Reputation: 0
When do you need more than 1 pthread barrier variable?


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

Last edited by kvm1983; 09-02-2009 at 02:31 PM.
 
Old 09-02-2009, 09:19 PM   #2
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,368
Blog Entries: 52

Rep: Reputation: 354Reputation: 354Reputation: 354Reputation: 354
When you have more than two threads.
 
Old 09-02-2009, 11:07 PM   #3
wje_lq
Member
 
Registered: Sep 2007
Location: Mariposa
Distribution: Debian lenny, Slackware 12
Posts: 809

Rep: Reputation: 178Reputation: 178
Quote:
Originally Posted by neonsignal View Post
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.
 
Old 09-02-2009, 11:26 PM   #4
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,368
Blog Entries: 52

Rep: Reputation: 354Reputation: 354Reputation: 354Reputation: 354
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.
 
Old 09-03-2009, 08:10 AM   #5
kvm1983
Member
 
Registered: Jul 2009
Posts: 47

Original Poster
Rep: Reputation: 0
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;
}
 
Old 09-03-2009, 08:50 AM   #6
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,368
Blog Entries: 52

Rep: Reputation: 354Reputation: 354Reputation: 354Reputation: 354
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.
 
Old 09-03-2009, 03:19 PM   #7
kvm1983
Member
 
Registered: Jul 2009
Posts: 47

Original Poster
Rep: Reputation: 0
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
 
Old 09-03-2009, 04:28 PM   #8
neonsignal
Senior Member
 
Registered: Jan 2005
Location: Melbourne, Australia
Distribution: Debian Wheezy (Fluxbox WM)
Posts: 1,368
Blog Entries: 52

Rep: Reputation: 354Reputation: 354Reputation: 354Reputation: 354
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
 
Old 09-03-2009, 04:36 PM   #9
kvm1983
Member
 
Registered: Jul 2009
Posts: 47

Original Poster
Rep: Reputation: 0
Code:
master
for n times
   wait semaphore

n others
   signal semaphore
Got it. Thanks a ton.
 
  


Reply

Tags
posix, threads


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
libtest.a uses pthread: user of libtest.a should not link pthread again debulu Programming 2 01-31-2007 10:23 PM
POSIX Barrier?? MeMooMeM Programming 5 05-26-2005 03:19 PM
32 Gb barrier using fdisk the_geezus Slackware 4 11-20-2004 10:12 AM
hard drive barrier problem nobodynowhere Linux - Hardware 2 12-12-2003 12:45 PM
hard disk barrier problem nobodynowhere Debian 1 12-12-2003 10:27 AM


All times are GMT -5. The time now is 02:38 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration