Condition Variables

A condition variable is a synchronization object that represents a condition (a boolean expression that can be either true or false). Condition variables allow threads to safely block until a condition becomes true.

Example: Stacks

A stack data structure has two operations, stack_push and stack_pop. We’ll implement a stack of integers. The stack_push operation pushes an integer onto the top of the stack. The stack_pop operation pops the top integer off the stack and returns it. The stack has a pretty simple implementation:

typedef struct stack {
    int* v;
    size_t size;
    size_t capacity;
} stack;

void stack_push(stack* s, int value) {
    assert(s->size + 1 <= s->capacity);
    s->v[s->size] = value;
    ++s->size;
}

int stack_pop(stack* s) {
    assert(s->size > 0);
    --s->size;
    return s->v[s->size];
}

Here, the stack_pop operation fails if the stack is empty.

Multithreaded stacks

To make this data structure safe for use in a multithreaded program, we’d need to protect access to shared variables using a mutex. How would you do it? Here’s our answer:

typedef struct stack {
    int* v;
    size_t size;
    size_t capacity;

    pthread_mutex_t mutex;

} stack;
 
void stack_push(stack* s, int value) {

    pthread_mutex_lock(&s->mutex);

    assert(s->size + 1 <= s->capacity);
    s->v[s->size] = value;
    ++s->size;

    pthread_mutex_unlock(&s->mutex);

}
 
int stack_pop(stack* s) {

    pthread_mutex_lock(&s->mutex);

    assert(s->size > 0);
    --s->size;
    int result = s->v[s->size];

    pthread_mutex_unlock(&s->mutex);

    return result;
}

This works fine. But now that there are multiple threads—so one thread might be pushing items onto the stack while another thread pops items off—the “assert if empty” behavior of stack_pop seems badly considered. A better semantic for stack_pop is to wait until the stack becomes non-empty. But how? Here’s one attempt:

int stack_pop(stack* s) {
    pthread_mutex_lock(&s->mutex);

    // Wait until the stack is non-empty     while (s->size == 0) {         pthread_mutex_unlock(&s->mutex);         sched_yield();         pthread_mutex_lock(&s->mutex);     }

    assert(s->size > 0);
    --s->size;
    int result = s->v[s->size];
    pthread_mutex_unlock(&s->mutex);
    return result;
}

Stack_pop must release the mutex before calling sched_yield(), or the thread calling stack_push would block forever in pthread_mutex_lock! (This would be a deadlock: stack_push would be waiting for stack_pop to unlock the mutex, while stack_pop would be waiting for stack_push to add an item.)

Blocking multithreaded stacks

The sched_yield version, of course, spins, which uses a lot of CPU. How could we make stack_pop block?

There are many solutions, including using a pipe like we did for signals, but the classic and best solution for this problem is a condition variable. Here it is:

typedef struct stack {
    int* v;
    size_t size;
    size_t capacity;
    pthread_mutex_t mutex;
    `**`pthread_cond_t nonempty_condvar;`**` // represents condition “s->size > 0”
} stack;
 
void stack_push(stack* s, int value) {
    pthread_mutex_lock(&s->mutex);
    assert(s->size + 1 <= s->capacity);
    s->v[s->size] = value;
    ++s->size;

    pthread_cond_signal(&s->nonempty_condvar);

    pthread_mutex_unlock(&s->mutex);
}
 
int stack_pop(stack* s) {
    pthread_mutex_lock(&s->mutex);
    // Wait until the stack is non-empty
    while (s->size == 0)

        pthread_cond_wait(&s->nonempty_condvar, &s->mutex);

    assert(s->size > 0);
    --s->size;
    int result = s->v[s->size];
    pthread_mutex_unlock(&s->mutex);
    return result;
}

To use a condition variable, follow these guidelines:

• Each condition variable represents a condition. Here, nonempty_condvar represents the nonemptiness condition, specifically “s->size > 0”.
• Each condition variable is associated with a mutex. This mutex should protect all variables that might affect the condition. Here, the s->mutex lock protects s->size, the only variable mentioned in the condition. (This means that any thread that reads or modifies s->size does so with s->mutex locked.)
• To wait for the condition, a thread:
  • Locks the mutex.
  • Checks the condition. If the condition is true, the thread continues. Otherwise it:
  • Calls pthread_cond_wait(&condvar, &mutex). This atomically unlocks the mutex and waits for the condition.
  • When pthread_cond_wait returns, the mutex will be locked again. During the short period that the mutex was unlocked, the condition may have become false, so the thread should check for the condition again. (Thus, in general, a call to pthread_cond_wait should be in a loop.)
• Whenever a thread changes the condition from false to true, it should signal the corresponding condition variable. There are two forms of signal. pthread_cond_signal(&condvar) wakes up one of the threads waiting for the condition, while pthread_cond_broadcast(&condvar) wakes up all threads waiting for the condition. Neither call does anything unless a thread is waiting for the condition.

The sleep-wakeup race

Condition variables are associated with mutexes in order to avoid a problematic race condition called the sleep-wakeup race. You might not see the race condition right away. To understand it better, consider this hypothetical version that doesn’t link the condition variable with a mutex:

void stack_push(stack* s, int value) {
    pthread_mutex_lock(&s->mutex);
    assert(s->size + 1 <= s->capacity);
    s->v[s->size] = value;
    ++s->size;

    pthread_cond_signal(&s->nonempty_condvar);

    pthread_mutex_unlock(&s->mutex);
}
 
int stack_pop(stack* s) {
    pthread_mutex_lock(&s->mutex);
    // Wait until the stack is non-empty
    while (s->size == 0) {

        pthread_mutex_unlock(&s->mutex);         pthread_cond_wait(&s->nonempty_condvar, NULL);         pthread_mutex_lock(&s->mutex);

    }
    assert(s->size > 0);
    --s->size;
    int result = s->v[s->size];
    pthread_mutex_unlock(&s->mutex);
    return result;
}

Can you see the race?

Right: now stack_pop’s pthread_mutex_unlock and its pthread_cond_wait do not happen atomically. Consider the following interleaving between stack_push and stack_pop:

T1: stack_push(value)	s->size	s->mutex state	T2: stack_pop
	0	locked by T2	while (s->size == 0) {
	0	unlocked	pthread_mutex_unlock(&s->mutex);
pthread_mutex_lock(&s->mutex);	0	locked by T1
s->v[s->size] = value;	0	locked by T1
++s->size;	1	locked by T1
pthread_cond_signal(&s->nonempty_condvar); (Note: no thread is waiting!)	1	locked by T1
	1	locked by T1	pthread_cond_wait(&s->nonempty_condvar);
pthread_mutex_unlock(&s->mutex);	1	unlocked

Whoops! T2 has blocked to wait for a condition that has already happened. If no other thread calls stack_push, then stack_pop will block forever, which is a serious bug. We call this a sleep-wakeup race because the sleep in T2—pthread_cond_wait—has a race condition with the wakeup in T1—pthread_cond_signal. The coupling between condition variables and mutexes prevents this race condition.