</>EmbeddedInterview

What is a condition variable, and how do you build a thread-safe queue with one?

MediumOperating System Concepts

Short answer: A condition variable lets a thread sleep until some condition on shared data becomes true, without busy-waiting. It is always used together with a mutex that protects the data, and the wait is always inside a while loop that re-checks the condition, because wake-ups can be spurious and another thread may get there first.

#include <pthread.h>
#include <stdbool.h>

#define QSIZE 16

typedef struct {
    int buf[QSIZE];
    unsigned head, tail, count;
    pthread_mutex_t m;
    pthread_cond_t not_empty, not_full;
} queue_t;

void q_init(queue_t *q)
{
    q->head = q->tail = q->count = 0;
    pthread_mutex_init(&q->m, NULL);
    pthread_cond_init(&q->not_empty, NULL);
    pthread_cond_init(&q->not_full, NULL);
}

void q_put(queue_t *q, int v)
{
    pthread_mutex_lock(&q->m);
    while (q->count == QSIZE)                       /* re-check after every wake-up */
        pthread_cond_wait(&q->not_full, &q->m);     /* unlocks m, sleeps, re-locks m */
    q->buf[q->tail] = v;
    q->tail = (q->tail + 1) % QSIZE;
    q->count++;
    pthread_cond_signal(&q->not_empty);
    pthread_mutex_unlock(&q->m);
}

int q_get(queue_t *q)
{
    pthread_mutex_lock(&q->m);
    while (q->count == 0)
        pthread_cond_wait(&q->not_empty, &q->m);
    int v = q->buf[q->head];
    q->head = (q->head + 1) % QSIZE;
    q->count--;
    pthread_cond_signal(&q->not_full);
    pthread_mutex_unlock(&q->m);
    return v;
}

Why pthread_cond_wait takes the mutex: it releases the mutex and goes to sleep atomically. If you unlocked first and then slept, the producer could add an item and signal in between, and the wake-up would be lost.

Why a while and not an if:

  • POSIX allows spurious wake-ups.
  • With several consumers, another consumer may take the item between the signal and this thread re-acquiring the mutex.

signal vs broadcast: pthread_cond_signal wakes at least one waiter; pthread_cond_broadcast wakes all (use when the state change may let several waiters proceed, or when waiters wait for different conditions on the same variable).

Common mistakes: changing the shared state without holding the mutex, waiting without a predicate (a signal sent before the wait is lost forever, since condition variables have no memory), and holding the mutex while doing slow work.

C11 / C++ equivalents: cnd_wait/mtx_t in <threads.h>, std::condition_variable in C++. In an RTOS, the same producer/consumer is usually a message queue, which bundles the buffer, the lock and the blocking.