Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

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:

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.