9.2 Condition Variables, Semaphores, and Barrier

The threads on the Earth-core monitoring station have mastered using mutexes to protect shared gauges, but there's still no answer to "whose turn is it to act." The data collection thread must wait until the queue is non-empty, four analysis threads must wait until all have completed the current phase, and a scarce resource can only be shared between two worker threads at a time. Mutual exclusion alone isn't enough, resulting behavior often involves threads holding locks and repeatedly polling conditions, causing the CPU to waste cycles and heat up unnecessarily.

9.1 Threads, Data Races, and Mutual Exclusion protects shared invariants. This lesson explores three coordination patterns: waiting for a predicate to become true, limiting the number of concurrent resources, and synchronizing a group of threads at a phase boundary. In the story, the "notification bell" does not store business facts; in the formal model, state is always maintained within a protected predicate.

Condition Variable Does Not Preserve "One-Time Notification"

The consumer must wait until the queue is non-empty. If it repeatedly unlocks, checks, and sleeps, it wastes CPU cycles. If it checks first and then enters sleep separately, the producer might issue a notification exactly between those two steps, causing the consumer to miss it entirely.

A condition variable implements a single atomic protocol for "release mutex and enter waiting state":

lock mutex
while predicate is false:
    cond_wait(condition, mutex)
consume / update state
unlock mutex

pthread_cond_wait returns successfully only after reacquiring the mutex. The caller must hold the lock before calling, otherwise the predicate check, wait, and producer update would not occur within the same synchronization protocol.

Notifications themselves are not queued as business events. signal means "a specific waiter should recheck the condition," and broadcast means "all waiters should recheck." If no waiters are present at the time of notification, the notification has no subsequent effect. The actual state is preserved solely within the predicate protected by the mutex.

Why You Must Use while

After a wait returns, the predicate may still be false:

• POSIX allows spurious wakeups;
• After multiple consumers are woken, another thread might acquire the mutex first and remove the data;
• Broadcasts inherently wake up waiters who may not be able to continue;
• The program may later introduce additional paths that modify the predicate.

Thus, while is not merely a defense against a rare OS bug, it embodies the semantics of Mesa-style condition variables. When a thread is woken, it gains only the right to recontest the mutex; it does not receive a "guarantee" that the condition remains true.

A Complete Protocol for a Single-Slot Channel

The producer writes values 1–5, and the consumer sums them. Both occupied and closed are protected by the same mutex; the condition variable is used only for sleep and wake operations.

#define _POSIX_C_SOURCE 200809L
#include <stdbool.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Channel {
    pthread_mutex_t mutex;
    pthread_cond_t changed;
    bool occupied;
    bool closed;
    int value;
};

struct ConsumerArgument {
    struct Channel *channel;
    int sum;
};

static void check_pthread(const char *operation, int error) {
    if (error != 0) {
        fprintf(stderr, "%s: %s\n", operation, strerror(error));
        abort();
    }
}

static void *produce(void *raw_channel) {
    struct Channel *channel = raw_channel;
    for (int value = 1; value <= 5; value++) {
        check_pthread("lock", pthread_mutex_lock(&channel->mutex));
        while (channel->occupied) {
            check_pthread("wait",
                          pthread_cond_wait(&channel->changed,
                                            &channel->mutex));
        }
        channel->value = value;
        channel->occupied = true;
        check_pthread("broadcast", pthread_cond_broadcast(&channel->changed));
        check_pthread("unlock", pthread_mutex_unlock(&channel->mutex));
    }

    check_pthread("lock", pthread_mutex_lock(&channel->mutex));
    while (channel->occupied) {
        check_pthread("wait",
                      pthread_cond_wait(&channel->changed, &channel->mutex));
    }
    channel->closed = true;
    check_pthread("broadcast", pthread_cond_broadcast(&channel->changed));
    check_pthread("unlock", pthread_mutex_unlock(&channel->mutex));
    return NULL;
}

static void *consume(void *raw_argument) {
    struct ConsumerArgument *argument = raw_argument;
    struct Channel *channel = argument->channel;

    check_pthread("lock", pthread_mutex_lock(&channel->mutex));
    for (;;) {
        while (!channel->occupied && !channel->closed) {
            check_pthread("wait",
                          pthread_cond_wait(&channel->changed,
                                            &channel->mutex));
        }
        if (!channel->occupied && channel->closed) {
            break;
        }

        argument->sum += channel->value;
        channel->occupied = false;
        check_pthread("broadcast", pthread_cond_broadcast(&channel->changed));
    }
    check_pthread("unlock", pthread_mutex_unlock(&channel->mutex));
    return NULL;
}

int main(void) {
    struct Channel channel = {
        .mutex = PTHREAD_MUTEX_INITIALIZER,
        .changed = PTHREAD_COND_INITIALIZER,
        .occupied = false,
        .closed = false,
        .value = 0,
    };
    struct ConsumerArgument consumer_argument = {
        .channel = &channel,
        .sum = 0,
    };
    pthread_t producer;
    pthread_t consumer;

    check_pthread("create consumer",
                  pthread_create(&consumer, NULL, consume,
                                 &consumer_argument));
    check_pthread("create producer",
                  pthread_create(&producer, NULL, produce, &channel));
    check_pthread("join producer", pthread_join(producer, NULL));
    check_pthread("join consumer", pthread_join(consumer, NULL));

    printf("sum=%d\n", consumer_argument.sum);
    check_pthread("destroy condition", pthread_cond_destroy(&channel.changed));
    check_pthread("destroy mutex", pthread_mutex_destroy(&channel.mutex));
    return consumer_argument.sum == 15 ? 0 : 1;
}

This implementation simplifies the single-slot channel protocol using broadcast; when there is only one waiting consumer, signal is sufficient. When extending to a bounded queue, not_empty and not_full are typically used separately to avoid spurious wakeups. Before optimization, it's essential to ensure that every state transition wakes up all potential runnable participants.

timeout must be bound to the appropriate clock

pthread_cond_timedwait Use the condition attribute to select the clock. If using wall clock, clock synchronization by administrators might cause the deadline to jump. When supported, configure the condition variable to CLOCK_MONOTONIC.

After timeout returns, the predicate must still be checked within the mutex. The arrival of the deadline and a state change from the producer might occur simultaneously. The API returning timeout does not necessarily mean the state remains false.

For relative timeouts, spurious wakeups must also be prevented. Re-computing the full wait duration on each iteration can lead to unbounded total wait time. Instead, compute the absolute deadline once, then loop waiting.

semaphore stores the permit count

A counting semaphore maintains a non-negative permit count:

• sem_wait Acquires a permit; if unavailable, blocks until one becomes available.
• sem_post Releases a permit, which may wake up a waiting thread.

It's suitable for limiting the number of threads that can simultaneously access a finite resource, such as exactly 8 database connections. Unlike a mutex, a semaphore typically lacks the semantic requirement that "the same owner must release it"; incorrectly incrementing post will artificially inflate the available capacity.

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <semaphore.h>

static int acquire_permit(sem_t *semaphore) {
    while (sem_wait(semaphore) != 0) {
        if (errno != EINTR) {
            return -1;
        }
    }
    return 0;
}

static int use_limited_resource(sem_t *semaphore) {
    if (acquire_permit(semaphore) != 0) {
        return -1;
    }

    int result = perform_operation();
    int saved_errno = errno;
    if (sem_post(semaphore) != 0 && result == 0) {
        result = -1;
        saved_errno = errno;
    }
    errno = saved_errno;
    return result;
}

perform_operation represents a business function. The code emphasizes that permits are returned on all exit paths; in cases where thread cancellation is possible, additional cleanup handlers are required.

POSIX unnamed semaphores are not universally supported across Unix platforms for process-shared usage, and the lifecycle of named semaphores varies significantly. Cross-platform libraries should verify the target implementation and should not assume that Linux behavior represents the full POSIX specification.

Although a binary semaphore only has a count of 0 or 1, it does not automatically provide mutex semantics such as ownership, priority inheritance, or robust recovery. For protecting critical sections, prefer using a mutex. Use a semaphore only when expressing a limited resource quantity.

barrier Causes the Entire Probe Team to Converge at Stage Boundaries

Four workers can each process a portion of the data, but the next round of aggregation must wait until all participants have completed their current stage. A barrier tracks the number of participants from the current generation that have arrived; it does not represent how many permits are available for a scarce resource.

The predicate of a barrier is "the current generation has reached N participants." The last participant to arrive advances the generation and wakes up the other threads. If the barrier is reused, only the count (without the generation) can lead to ABA-style confusion: a late arrival from one generation might incorrectly interpret the count from the next.

#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { THREADS = 4, ROUNDS = 20 };

struct Barrier {
    pthread_mutex_t mutex;
    pthread_cond_t changed;
    unsigned int participants;
    unsigned int arrived;
    unsigned int generation;
};

struct WorkerArgument {
    struct Barrier *barrier;
};

static _Atomic int arrivals[ROUNDS];

static void check(int error, const char *operation) {
    if (error != 0) {
        fprintf(stderr, "%s: %s\n", operation, strerror(error));
        abort();
    }
}

static void barrier_wait(struct Barrier *barrier) {
    check(pthread_mutex_lock(&barrier->mutex), "lock");
    unsigned int generation = barrier->generation;

    barrier->arrived++;
    if (barrier->arrived == barrier->participants) {
        barrier->arrived = 0;
        barrier->generation++;
        check(pthread_cond_broadcast(&barrier->changed), "broadcast");
    } else {
        while (generation == barrier->generation) {
            check(pthread_cond_wait(&barrier->changed, &barrier->mutex),
                  "wait");
        }
    }
    check(pthread_mutex_unlock(&barrier->mutex), "unlock");
}

static void *run_rounds(void *raw_argument) {
    struct WorkerArgument *argument = raw_argument;
    for (int round = 0; round < ROUNDS; round++) {
        atomic_fetch_add_explicit(&arrivals[round], 1,
                                  memory_order_relaxed);
        barrier_wait(argument->barrier);
        assert(atomic_load_explicit(&arrivals[round],
                                    memory_order_relaxed) == THREADS);
    }
    return NULL;
}

int main(void) {
    struct Barrier barrier = {
        .mutex = PTHREAD_MUTEX_INITIALIZER,
        .changed = PTHREAD_COND_INITIALIZER,
        .participants = THREADS,
        .arrived = 0,
        .generation = 0,
    };
    struct WorkerArgument argument = {.barrier = &barrier};
    pthread_t threads[THREADS];

    for (int index = 0; index < THREADS; index++) {
        check(pthread_create(&threads[index], NULL, run_rounds, &argument),
              "pthread_create");
    }
    for (int index = 0; index < THREADS; index++) {
        check(pthread_join(threads[index], NULL), "pthread_join");
    }

    check(pthread_cond_destroy(&barrier.changed), "cond_destroy");
    check(pthread_mutex_destroy(&barrier.mutex), "mutex_destroy");
    puts("all barrier rounds completed");
    return 0;
}

The number of barrier participants remains constant during execution, and all threads must have exited before the barrier is destroyed. When dynamic participant counts, cancellation, or broken barriers are involved, the state management becomes significantly more complex. In such cases, prefer using the platform's pthread_barrier_t or a mature library rather than reimplementing the logic from scratch.

read-write lock does not guarantee that more reads mean faster performance

A read-write lock allows multiple readers or a single writer. It's suitable for workloads where the critical section is long enough to allow true parallelism and where writes are rare. However, in the following scenarios, a standard mutex might be a better choice:

• The critical section is very short, and the overhead of read-write bookkeeping exceeds the benefits of parallelism;
• Cache line contention remains high due to reader-count updates;
• Write frequency is not low;
• The policy leads to starvation of either readers or writers;
• The read path still modifies lazy cache or statistics, meaning it's not truly a read-only operation.

Fairness and writer preference are typically implementation-specific policies and should not be assumed. Upgrading a read lock to a write lock can lead to deadlocks unless the API explicitly supports it and the protocol properly handles contention.

Chapter 11 discusses spin/futex and lock implementation details; Chapter 16 explains atomic memory ordering. Here, the read-write lock is treated merely as a measurable strategy, not as a guarantee of a one-order-of-magnitude performance improvement.

Choose Primitives by First Writing Predicates

Problem	Preferred Expression
A group of fields must be modified as a unit	mutex
Wait for a queue to be non-empty or not full	mutex + condition variable
At most N concurrent users	counting semaphore
N participants must meet at a stage	barrier
Long read, few writes	consider RW lock after benchmarking
Single counter or flag	C atomic, with memory order proven

Multiple primitives can be combined, but each additional waiting relationship increases the complexity of deadlock avoidance, cancellation handling, and shutdown paths. A bounded queue implemented with a mutex and condition variable is generally easier to maintain and reason about than one simulated with three semaphores, especially in preserving invariants and ensuring close semantics.

Hands-on Verify Notification Protocol

1. Change the single-slot channel's while to if, add two consumers, and construct a timing sequence where the predicate is consumed first.
2. Selectively replace broadcast with signal to illustrate why each position is sufficient or would miss a role.
3. Add cancellation and timeout support to the channel to ensure the producer does not permanently wait after the channel is closed.
4. Remove the generation from the reusable barrier and look for errors that span across rounds.
5. Use a semaphore to limit concurrent operations to three, and verify that all error paths properly return a permit.
6. Compare mutex and RW lock performance on the same read-heavy map, reporting critical-section duration and starvation policy.

Runnable Thread Must Still Wait in Line

Synchronization primitives determine when a thread becomes blocked or runnable, but they don't dictate when that runnable thread will eventually get access to the CPU. The next chapter delves into CPU Scheduling, comparing metrics like response time, turnaround time, fairness, and deadlines, rather than simply memorizing algorithm names.