Figure 7.2 shows the operation of a barrier being used to synchronize three threads, called thread 1, thread 2, and thread 3. The figure is a sort of timing diagram, with time increasing from left to right. Each of the lines beginning at the labels in the upper left designates the behavior of a specific thread — solid for thread 1, dotted for thread 2, and dashed for thread 3. When the lines drop within the rounded rectangle, they are interacting with the barrier. If the line drops below the center line, it shows that the thread is blocked waiting for other threads to reach the barrier. The line that stops above the center line represents the final thread to reach the barrier, awakening all waiters.
In this example, thread 1 and then thread 2 wait on the barrier. At a later time, thread 3 waits on the barrier, finds that the barrier is now full, and awakens all the waiters. All three threads then return from the barrier wait.
The core of a barrier is a
FIGURE 7.2
Because the counter will be modified by multiple threads, it has to be protected by a mutex. Because threads will be waiting for some event (a counter value of 0), the barrier needs to have a condition variable and a predicate expression. When the counter reaches 0 and the barrier drops open, we need to reset the counter, which means the barrier must store the original threshold.
The obvious predicate is to simply wait for the counter to reach 0, but that complicates the process of resetting the barrier. When can we reset the count to the original value? We can't reset it when the counter reaches 0, because at that point most of the threads are waiting on the condition variable. The counter must be 0 when they wake up, or they'll continue waiting. Remember that condition variable waits occur in loops that retest the predicate.
The best solution is to add a separate variable for the predicate. We will use a 'cycle' variable that is logically inverted each time some thread determines that one cycle of the barrier is complete. That is, whenever the counter value is reset, before broadcasting the condition variable, the thread inverts the cycle flag. Threads wait in a loop as long as the cycle flag remains the same as the value seen on entry, which means that each thread must save the initial value.
The header file barrier.h and the C source file barrier.c demonstrate an implementation of barriers using standard Pthreads mutexes and condition variables. This is a portable implementation that is relatively easy to understand. One could, of course, create a much more efficient implementation for any specific system based on knowledge of nonportable hardware and operating system characteristics.
6-13 Part 1 shows the structure of a barrier, represented by the type barrier_t. You can see the mutex (mutex) and the condition variable (cv). The threshhold member is the number of threads in the group, whereas counter is the number of threads that have yet to join the group at the barrier. And cycle is the flag discussed in the previous paragraph. It is used to ensure that a thread awakened from a barrier wait will immediately return to the caller, but will block in the barrier if it calls the wait operation again before all threads have resumed execution.
15 The BARRIER_VALID macro defines a 'magic number,' which we store into the valid member and then check to determine whether an address passed to other barrier interfaces is 'reasonably likely to be' a barrier. This is an easy, quick check that will catch the most common errors.[7]
¦ barrier.h part 1 barrier_t
1 #include <pthread.h>
2
3 /*
4 * Structure describing a barrier.
5 */
6 typedef struct barrier_tag {
7 pthread_mutex_t mutex; /* Control access to barrier * /
8 pthread_cond_t cv; /* wait for barrier */
9 int valid; /* set when valid */
10 int threshold; /* number of threads required */
11 int counter; /* current number of threads * /
12 int cycle; /* alternate cycles (0 or 1) * /
13 } barrier_t;
14
15 #define BARRIER_VALID 0xdbcafe
Part 2 shows definitions and prototypes that allow you to do something with the barrier_t structure. First, you will want to initialize a new barrier. 4-6 You can initialize a static barrier at compile time by using the macro BARRIER_ INITIALIZER. You can instead dynamically initialize a barrier by calling the function barrier_init.
11-13 Once you have initialized a barrier, you will want to be able to use it. and the main thing to be done with a barrier is to wait on it. When we're done with a barrier, it would be nice to be able to destroy the barrier and reclaim the resources it used. We'll call these operations barrier_init, barrier_wait, and barrier_ destroy. All the operations need to specify upon which barrier they will operate. Because barriers are synchronization objects, and contain both a mutex and a condition variable (neither of which can be copied), we always pass a pointer to a barrier. Only the initialization operation requires a second parameter, the number of waiters required before the barrier opens.
To be consistent with Pthreads conventions, the functions all return an integer value, representing an error number defined in <errno.h>. The value 0 represents success.
¦ barrier.h part 2 interfaces
1 /*
2 * Support static initialization of barriers.
3 */
4 #define BARRIER_INITIALIZER(cnt)
5 {PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER,
6 BARRIER_VALID, cnt, cnt, 0}
7
8 /*
9 * Define barrier functions
10 */
11 extern int barrier_init (barrier_t *barrier, int count);
12 extern int barrier_destroy (barrier_t *barrier);
13 extern int barrier_wait (barrier_t *barrier);
Now that you know the interface definition, you could write a program using barriers. But then, the point of this section is not to tell you how to use barriers, but to help improve your understanding of threaded programming by showing how to build a barrier. The following examples show the functions provided by barrier .c, to implement the interfaces we've just seen in barrier.h.
Part 1 shows barrier_init, which you would call to dynamically initialize a barrier, for example, if you allocate a barrier with malloc.
12 Both the counter and threshold are set to the same value. The counter is the 'working counter' and will be reset to threshold for each barrier cycle.
14-16 If mutex initialization fails, barrier_init returns the failing status to the caller.
17-21 If condition variable (cv) initialization fails,
