14.3.3. Other Synchronization Constructs

Mutexes and semaphores are not the only example of synchronization constructs that can be used in the context of multi-threaded programs. In this subsection, we will briefly discuss the barrier and condition variable synchronization constructs, which are both part of the Pthreads library:

Barriers

A barrier is a type of synchronization construct that forces all threads to reach a common point in execution before releasing the threads to continue executing concurrently. Pthreads offers a barrier synchronization primitive. To use Pthreads barriers, it is necessary to:

  • declare a barrier global variable (e.g. pthread_barrier_t barrier)

  • initialize the barrier in main() ( pthread_barrier_init(&barrier))

  • destroy the barrier in main() after use ( pthread_barrier_destroy(&barrier))

  • use the pthread_barrier_wait() function to create a synchronization point.

The program below shows the use of a barrier in a function called threadEx():

void *threadEx(void *args){
    //parse args
    //...
    long myid = myargs->id;
    int nthreads = myargs->numthreads;
    int *array = myargs->array

    printf("Thread %ld starting thread work!\n", myid);
    pthread_barrier_wait(&barrier); //forced synchronization point
    printf("All threads have reached the barrier!\n");
    for (i = start; i < end; i++) {
        array[i] = array[i] * 2;
    }
    printf("Thread %ld done with work!\n", myid);

    return NULL;
}

In the above example, no thread can start processing its assigned portion of the array until every thread printed out the message that they are starting work. Without the barrier, it is possible for one thread to have finished work before the other threads printed their starting work message! Notice that it is still possible for one thread to print that it is done doing work before another thread finishes.

Condition Variables

Condition variables force a thread to block until a particular condition is reached. This construct is useful in scenarios where a condition must be met before the thread does some work. In the absence of condition variables, a thread would have to repeatedly check to see if the condition is met, continuously utilizing the CPU. Condition variables are always used in conjunction with a mutex. In this type of synchronization construct, the mutex enforces mutual exclusion, while the condition variable ensures that particular conditions are met before a thread acquires the mutex.

POSIX condition variables have the type pthread_cond_t. Like the mutex and barrier constructs, condition variables must be initialized prior to use and destroyed after use.

To initialize a condition variable, use pthread_cond_init() function. To destroy a condition variable, use the pthread_cond_destroy() function.

The two functions commonly invoked when using condition variables are pthread_cond_wait() and pthread_cond_signal(). Both functions require an address to a mutex in addition to the address of the condition variable:

  • pthread_cond_wait(&cond, &mutex) takes the address of a condition variable cond and a mutex mutex as its arguments. It causes the calling thread to block on condition variable cond until another thread signals it (or "wakes" it up).

  • The pthread_cond_signal(&cond) function causes the calling thread to unblock (or signal) another thread that is waiting on the condition variable cond (based on a scheduling priority). If no threads are currently blocked on the condition, then the function has no effect. Unlike pthread_cond_wait(), the pthread_cond_signal() function can be called by a thread regardless of whether or not it owns the mutex in which pthread_cond_wait() is called.

Condition Variable Example

Traditionally, condition variables are most useful when a subset of threads are waiting on another set to complete some action. In the following example, we use multiple threads to simulate a set of farmers collecting eggs from a set of chickens. "Chicken" and "Farmer" represent two separate classes of threads. The full source of this program is found here. Note that the listing below excludes many comments/error handling for brevity.

The main() function creates a shared variable num_eggs (which indicates the total number of eggs available at any given time, a shared mutex (which is used whenever a thread accesses num_eggs) and a shared condition variable eggs. It then creates two chicken and two farmer threads:

int main( int argc, char **argv ){

    // these will be shared by all threads via pointer fields in t_args
    int num_eggs;           // number of eggs ready to collect
    pthread_mutex_t mutex;  // mutex associated with cond variable
    pthread_cond_t  eggs;   // used to block or wake-up farmer waiting for eggs

    //... args parsing removed for brevity

    num_eggs = 0; // number of eggs ready to collect
    ret = pthread_mutex_init(&mutex, NULL); //initialize the mutex
    pthread_cond_init(&eggs, NULL); //initialize the condition variable

    //... thread_array and thread_args creation/filling omitted for brevity

    // create some chicken and farmer threads
    for(i = 0; i < (2 * nthreads); i++) {
        if( (i % 2) == 0 ) {
            ret = pthread_create( &thread_array[i], NULL, chicken, &thread_args[i]);
        }
        else {
            ret = pthread_create( &thread_array[i], NULL, farmer, &thread_args[i] );
        }
    }

    // wait for chicken and farmer threads to exit
    for (i = 0; i < (2 * nthreads); i++)  {
        ret = pthread_join(thread_array[i], NULL);
    }

    // clean-up program state
    pthread_mutex_destroy(&mutex); //destroy the mutex
    pthread_cond_destroy(&eggs);   //destroy the cond var

    return 0;
}

Each Chicken thread is responsible for laying a certain number of eggs:

void *chicken(void *args ) {
    struct t_arg *myargs = (struct t_arg *)args;
    int *num_eggs, i, num;

    num_eggs = myargs->num_eggs;
    i = 0;

    // lay some eggs
    for (i = 0; i < myargs->total_eggs; i++) {
        usleep(EGGTIME); //chicken sleeps

        pthread_mutex_lock(myargs->mutex);
        *num_eggs = *num_eggs + 1;  // update number of eggs
        num = *num_eggs;
        pthread_cond_signal(myargs->eggs); // wake up a sleeping farmer (squawk)
        pthread_mutex_unlock(myargs->mutex);

        printf("chicken %d created egg %d available %d\n", myargs->id, i, num);
    }
    return NULL;
}

To lay an egg, a Chicken thread sleeps for a while, acquires the mutex and updates total number of available eggs by one. Prior to releasing the mutex, the Chicken thread "wakes up" a sleeping farmer (presumably by squawking). The Chicken thread repeats the cycle until it has laid all the eggs it intends to (total_eggs).

Each Farmer thread is responsible for collecting total_eggs eggs from the set of chickens (presumably for his or her breakfast):

void *farmer(void *args ) {
    struct t_arg * myargs = (struct t_arg *)args;
    int *num_eggs, i, num;

    num_eggs = myargs->num_eggs;

    i = 0;

    for (i = 0; i < myargs->total_eggs; i++) {
        pthread_mutex_lock(myargs->mutex);
        while (*num_eggs == 0 ) { // no eggs to collect
            // wait for a chicken to lay an egg
            pthread_cond_wait(myargs->eggs, myargs->mutex);
        }

        // we hold mutex lock here and num_eggs > 0
        num = *num_eggs;
        *num_eggs = *num_eggs - 1;
        pthread_mutex_unlock(myargs->mutex);

        printf("farmer %d gathered egg %d available %d\n", myargs->id, i, num);
    }
    return NULL;
}

Each Farmer thread acquires the mutex prior to checking the shared num_eggs variable to see if any eggs are available (*num_eggs == 0). While there aren’t any eggs available, the Farmer thread blocks (i.e., takes a nap).

Once the Farmer thread "wakes up" due to a signal from a Chicken thread, it checks to see that an egg is still available (another farmer could have grabbed it first) and if so, the farmer "collects" an egg (decrementing num_eggs by one) and releases the mutex.

In this manner, the Chicken and Farmer work in concert to lay/collect eggs. Condition variables ensure that no Farmer thread collects an egg until it is laid by a Chicken thread.

Broadcasting

Another function used with condition variables is pthread_cond_broadcast() , which is useful when multiple threads are blocked on a particular condition. Calling pthread_cond_broadcast(&cond) wakes up all threads that are blocked on condition cond. In the example below, we show how condition variables can implement the barrier construct discussed previously:

pthread_mutex_t mutex; //mutex (initialized in main)
pthread_cond_t barrier; //condition variable signifying the barrier (initialized in main)

void *threadEx_v2(void *args){
    //parse args
    //...
    long myid = myargs->id;
    int nthreads = myargs->numthreads;
    int *array = myargs->array

    //counter denoting the number of threads that reached the barrier
    int *n_reached = myargs->n_reached;

    //start barrier code
    pthread_mutex_lock(&mutex);
    *n_reached++;

    printf("Thread %ld starting work!\n", myid)
    while (*n_reached < nthreads) { //if some threads have not reached the barrier
        pthread_cond_wait(&barrier, &mutex);
    }
    //all threads have reached the barrier
    printf("all threads have reached the barrier!\n");
    pthread_cond_broadcast(&barrier);

    pthread_mutex_unlock(&mutex);
    //end barrier code

    //normal thread work
    for (i = start; i < end; i++) {
        array[i] = array[i] * 2;
    }
    printf("Thread %ld done with work!\n", myid);

    return NULL;
}

The function threadEx_v2 has identical functionality to threadEx. In this example, the condition variable is named barrier. As each thread acquires the lock, it increments n_reached, the number of threads that have reached that point. While the number of threads that have reached the barrier is less than the total number of threads, the thread waits on the condition variable barrier and mutex mutex.

However, when the last thread reaches the barrier, it calls pthread_cond_broadcast(&barrier), which releases all the other threads that are waiting on the condition variable barrier, enabling them to continue execution.

While the above example is useful for illustrating the pthread_cond_broadcast function, it is best to use the Pthreads barrier primitive whenever barriers are necessary in a program.

One question that students tend to ask is if the while loop around the call to pthread_cond_wait() in the farmer and threadEx_v2 code can be replaced with an if statement. This while loop is in fact absolutely necessary for two main reasons. First, the condition may change prior to the woken thread arriving to continue execution. The while loop enforces that the condition be retested one last time. Second, the pthread_cond_wait() function is vulnerable to spurious wakeups, in which a thread gets erroneously woken up even though the condition may not be met. The while loop is in fact an example of a predicate loop, which forces a final check of the condition variable before releasing the mutex. The use of predicate loops is therefore correct practice when using condition variables.