§31.1–31.3Semaphores: A Definition … Semaphores For Ordering

We now have locks and condition variables — but Dijkstra realized years ago that a single primitive could do both. That primitive is the semaphore semaphore Dijkstra's single synchronization primitive: an integer manipulated by two atomic routines — sem_wait() (P/down: decrement, then block while the value is negative) and sem_post() (V/up: increment, and wake one waiter if any). The initial value determines its behavior; when the value is negative, its magnitude equals the number of waiting threads. Usable as both a lock and a condition variable. defined in ch. 31 — open in glossary .

31.1 Semaphores: A Definition

A semaphore is an integer value manipulated by two atomic routines. In POSIX they’re sem_wait() and sem_post() (Dijkstra called them P and V, from Dutch; some say down and up). You must initialize it first — and the initial value is everything:

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // third arg is the initial value; 0 = shared within a process

The behavior of the two operations:

int sem_wait(sem_t *s) {
    decrement the value of s by one
    wait if the value of s is negative
}
int sem_post(sem_t *s) {
    increment the value of s by one
    if there are one or more threads waiting, wake one
}

Three things to internalize: sem_wait() either returns immediately (if the value was ≥ 1) or suspends the caller until a later post; sem_post() never waits — it just increments and wakes one waiter if any; and, by Dijkstra’s invariant, when the value is negative, its magnitude equals the number of waiting threads. Step through it:

(Assume for now these actions happen atomically — §31.8 builds a semaphore from a lock and a CV to make that true.)

31.2 Binary Semaphores (Locks)

Our first use is a familiar one: a lock. Bracket the critical section with a wait/post pair — and initialize to 1:

sem_t m;
sem_init(&m, 0, 1); // X = 1

sem_wait(&m);
// critical section here
sem_post(&m);

Why 1? The first thread’s sem_wait drives the value 1 → 0 and enters; a second thread’s sem_wait drives it 0 → −1 and sleeps, until the holder posts. Watch two threads contend:

Because a lock has only two states (held / not held), a semaphore used this way is a binary semaphore binary semaphore A semaphore used as a lock: initialized to 1, with a sem_wait()/sem_post() pair bracketing the critical section. It has only two effective states (held / not held), hence 'binary'. defined in ch. 31 — open in glossary . (Used purely as a binary lock, it could be implemented more simply than the general semaphore.)

31.3 Semaphores For Ordering

Semaphores also order events: one thread waits for something another thread makes happen — exactly what condition variables did. The classic example is a parent waiting for a child (init to 0 this time):

sem_t s;
void *child(void *arg) {
    printf("child\n");
    sem_post(&s); // signal: child is done
    return NULL;
}
int main() {
    sem_init(&s, 0, 0); // X = 0
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait for the child
    printf("parent: end\n");
}

Why 0? If the parent reaches sem_wait first, the value goes 0 → −1 and it sleeps, exactly as we want:

And the other order works too (Case 2): if the child runs to completion first, its sem_post drives the value 0 → 1; when the parent finally calls sem_wait, it finds 1, decrements to 0, and returns without blocking. Either way, “child” prints before “parent: end”.

Same primitive, two opposite jobs — decided entirely by the initial value. Next: the producer/consumer problem, rebuilt on semaphores.