Condition Variables

Tags

comp-arch

Is a construct that allows a set of threads to sleep until woken up. Condition variables are used in situations where one thread has to block until some condition is met (example a stack is full so you can't push onto it) but that condition has to be achieved by another thread that must communicate the change back to it.

// Thread 1
while (1) {
    lock(mutex); // Blocks waiting for notification from Thread 2.
    // ...
    unlock(mutex); // Tells Thread 2 we are done.
}

// Thread 2
// ... Do the work that precedes the notification
unlock(mutex); // unblocks Thread 1
lock(mutex); // Lock the mutex so Thread 1 will block again.

For example consider code:polled-notifiy. In it we have two threads that use a shared a mutex lock and polling as a sort of naive notification mechanism. Thread 1 repeatedly acquires the lock, checks whether the condition has been met, and then releases the lock. Thread 2 is doing some expensive work in the background that Thread 1 is waiting on and acquires the lock to prevent Thread 1 getting it, then it releases the lock in an attempt to signal Thread 1 that its ready.

This is an expensive notification system since acquiring and releasing locks isn't cheap. In practice it makes more sense to block thread 1 and have thread 2 alert thread 1 when it finishes so that it can check everything's ready and proceed. That's what condition variables are for.

Any thread can call pthread_cond_wait to block the current thread until it is signalled (from another thread) by pthread_cond_broadcast which wakes up all of the threads sleeping in the condition variable or pthread_cond_signal which only wakes up one thread (the thread chosen here is picked by the OS and there's no way for the developer to control which one it is).

Spurious Wake-Ups

Sometimes a waiting thread may wake up for no reason. These happen for performance reasons: On multi-CPU system it is possible for a race condition to cause a wake-up (signal) to go unnoticed. To avoid the potentially lost signal, the thread is woken up so that the program code can test the condition again. This means if you wait for a condition variable on a check (example: if (s->count == 0)), that condition may still not be valid even when pthread_cond_wait returns. To work around this use a while loop instead of a single condition check (and make sure to account for deadlocks).

Thread Safe Stack Push/Pop example

void push(stack_t *s, double v) {
    pthread_mutex_lock(&s->m);
    // Wait until count decreases below capacity.
    while (s->count == capacity)
	// Blocks until signalled by another thread (that has modified the stack).
	pthread_cond_wait(&s->cv, &s->m);
    s->values[(s->count)++] = v;
    pthread_mutex_unlock(&s->m);
    pthread_cond_signal(&s->cv); // Wake up *one* other thread.
}

double pop(stack_t *s) {
    pthread_mutex_lock(&s->m);
    // Wait until the stack isn't empty.
    while (s->count == 0)
	// Blocks until signalled by another thread (that has modified the stack).
	pthread_cond_wait(&s->cv, &s->m);
    double v = s->values[--(s->count)];
    pthread_cond_broadcast(&s->cv); // Wake up *all* the other threads.
    pthread_mutex_unlock(&s->m);
    return v;
}

Here we describe the push and pop operations for a thread-safe stack.

Note: pthread_cond_wait unlocks the stack Mutex and then re-locks it before returning. This is so another thread can acquire and act using the lock while the current thread is blocked waiting on the condition variable. It's also why we must lock the Mutex before calling pthread_cond_wait because otherwise we'll have unlocked a possibly already unlocked mutex (or worse one locked in another thread).