A barrier is a point in our program we would like all threads to reach before continuing on. In the diagram below, there is a barrier between section 1 and section 2:
This can be useful for several reasons:
In order to implement a barrier, we need all but the slowest thread to wait at the barrier before continuing past it:
In the program below, say we want to introduce a barrier after each thread is done the "computation".
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdio.h>
/* the number of threads */
int num_threads;
/* the function called for each thread */
void* worker(void* idp) {
/* get our thread id */
int id = * (int*) idp;
/* we start to work */
printf("Thread %d starting!\n", id);
/* simulate the threads taking slightly different amounts of time by sleeping
* for our thread id seconds */
sleep(id);
printf("Thread %d is done its work!\n", id);
/* TODO create a barrier here! */
printf("Thread %d is past the barrier!\n", id);
return NULL;
}
int main (int argc, char** argv) {
/* get the number of threads */
if (argc < 2) {
printf("Pass the number of threads to use!\n");
return 0;
} else {
num_threads = atoi(argv[1]);
}
/* an array of threads */
pthread_t threads[num_threads];
int ids[num_threads];
/* spawn all threads */
for (int i = 0; i < num_threads; i++) {
ids[i] = i;
pthread_create(&threads[i], NULL, worker, &ids[i]);
}
/* join all threads */
for (int i = 0; i < num_threads; i++) {
pthread_join(threads[i], NULL);
}
return 0;
}
If we had a barrier in place, what should the output of this program be?
How could we implement a barrier in the above program with a busy-wait loop?
What are the downsides of this?
We can also use semaphores to implement a barrier. The basic idea is:
Upon reaching the barrier, each thread will wait until the counter variable is free (waiting on the first semaphore).
It then will check if that counter is equal to (NUM_THREADS - 1):
This example implements this technique:
/* the function called for each thread */
void* worker(void* idp) {
/* get our thread id */
int id = * (int*) idp;
/* we start to work */
printf("Thread %d starting!\n", id);
/* simulate the threads taking slightly different amounts of time by sleeping
* for our thread id seconds */
sleep(id);
printf("Thread %d is done its work!\n", id);
/***************** begin barrier here *****************/
/* wait for the counter first */
sem_wait(&count_sem);
/* check if we are the last one to the barrier */
if (counter == (num_threads - 1)) {
/* we are the last thread */
/* reset counter and free it */
counter = 0;
sem_post(&count_sem);
/* post once for each waiting thread */
for (int i = 0; i < (num_threads - 1); i++) {
sem_post(&barrier_sem);
}
} else {
/* we are NOT the last thread */
/* increment the counter and free it */
counter++;
sem_post(&count_sem);
/* now wait to be freed */
sem_wait(&barrier_sem);
}
/***************** end barrier here *****************/
printf("Thread %d is past the barrier!\n", id);
return NULL;
}
A somewhat more straightforward approach to creating a barrier is to use a condition variable. A condition variable is used to communicate events between threads. Conditions are always associated with a mutex.
Condition variables are declared with:
pthread_cond_t condition;
pthread_cond_init(pthread_cond_t* condition, pthread_condattr_t* attributes);
As with a mutex, we usually pass NULL for the attributes.
We can wait on a condition with:
pthread_cond_wait(pthread_cond_t* condition, pthread_mutex_t* mutex);
This function unlocks the given mutex, then waits for a thread to signal the condition passed in. Finally it re-locks the mutex.
A thread can signal that the condition has occurred with either:
pthread_cond_signal(pthread_cond_t* condition);
pthread_cond_broadcast(pthread_cond_t* condition);
The first will unblock one of the waiting threads. The second will unblock all of the threads.
We can create a condition that represents the event "all threads have reached the barrier". This leads to code like this example:
/* our counter and condition */
int counter = 0;
pthread_cond_t condition;
pthread_mutex_t condition_mutex;
/* the function called for each thread */
void* worker(void* idp) {
/* get our thread id */
int id = * (int*) idp;
/* we start to work */
printf("Thread %d starting!\n", id);
/* simulate the threads taking slightly different amounts of time by sleeping
* for our thread id seconds */
sleep(id);
printf("Thread %d is done its work!\n", id);
/***************** begin barrier here *****************/
/* lock the condition and increment the counter */
pthread_mutex_lock(&condition_mutex);
counter++;
/* if all the threads have incremented counter */
if (counter == num_threads) {
/* reset the counter and broadcast the event to all waiting threads */
counter = 0;
pthread_cond_broadcast(&condition);
} else {
/* otherwise not all threads are here yet, so we need to wait */
pthread_cond_wait(&condition, &condition_mutex);
}
/* unlock the condition mutex */
pthread_mutex_unlock(&condition_mutex);
/***************** end barrier here *****************/
printf("Thread %d is past the barrier!\n", id);
return NULL;
}
mutex
read-write lock
semaphore
condition variable
Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.