Semaphores

What it is#

A semaphore is an integer with two atomic operations:

• wait(s) (Dijkstra called it P, for “proberen”) — decrement the counter; if it goes negative, block the caller until someone else posts.
• post(s) (Dijkstra called it V, for “verhogen”) — increment the counter; if any thread is blocked, wake one.

Initialise the counter to K, and the semaphore admits at most K concurrent passers. With K = 1 it’s a binary semaphore — equivalent to a mutex. With K = N it gates access to N units of a resource. With K = 0 it becomes a one-shot wakeup channel between threads.

The big idea is that the counter encodes both “how many slots are free” and “how many waiters are queued.” You don’t have to pair it with a separate mutex to make the wait-and-decrement atomic — that atomicity is the primitive’s whole job.

When to use it#

Reach for a semaphore when the predicate you’re waiting on is a count rather than an arbitrary boolean expression:

• Bounded buffer / producer-consumer — one semaphore counts empty slots (producer waits on it), another counts filled slots (consumer waits on it). No explicit predicate, no mutex inside the wait.
• Connection / thread pool — K available workers; clients wait(s) to grab one, post(s) to release.
• Rate limiter — K tokens; refill them on a schedule.
• Ordering / signalling — K = 0 so the consumer blocks until the producer posts. Pattern for “wait for setup to finish.”
• Readers-writers — combine a counting semaphore (mutex over reader count) with a binary semaphore (exclusion against writers).

Use a condition variable instead when the predicate is “queue has at least 3 items AND temperature < 60” — semaphores can’t combine multiple counters atomically.

How it works#

Implementation sketch#

The textbook implementation built on a mutex and a CV:

typedef struct {
    int val;
    pthread_mutex_t m;
    pthread_cond_t  cv;
} sem_t;

void sem_init(sem_t* s, int v) {
    s->val = v;
    pthread_mutex_init(&s->m, NULL);
    pthread_cond_init(&s->cv, NULL);
}

void sem_wait(sem_t* s) {
    pthread_mutex_lock(&s->m);
    while (s->val <= 0) pthread_cond_wait(&s->cv, &s->m);
    s->val--;
    pthread_mutex_unlock(&s->m);
}

void sem_post(sem_t* s) {
    pthread_mutex_lock(&s->m);
    s->val++;
    pthread_cond_signal(&s->cv);
    pthread_mutex_unlock(&s->m);
}

Production semaphores (Linux sem_t, dispatch_semaphore_t) skip the CV and use a futex directly for the contended path. Uncontended sem_post/sem_wait is one atomic add and a branch — no syscall.

Producer-consumer with semaphores#

The clean form is two counting semaphores plus one mutex:

#define N 16
int buf[N]; int head = 0, tail = 0;
sem_t empty, full;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void init(void) {
    sem_init(&empty, N);  // N empty slots to start
    sem_init(&full,  0);  // 0 filled slots
}

void produce(int x) {
    sem_wait(&empty);
    pthread_mutex_lock(&m);
    buf[tail] = x; tail = (tail + 1) % N;
    pthread_mutex_unlock(&m);
    sem_post(&full);
}

int consume(void) {
    sem_wait(&full);
    pthread_mutex_lock(&m);
    int x = buf[head]; head = (head + 1) % N;
    pthread_mutex_unlock(&m);
    sem_post(&empty);
    return x;
}

The mutex protects the buffer indices because there can be multiple producers and multiple consumers; with a single producer and single consumer, the mutex would be unnecessary. The semaphores do all the waiting.

Binary semaphore as a mutex#

sem_t lock; sem_init(&lock, 1);
sem_wait(&lock);    // == lock
// critical section
sem_post(&lock);    // == unlock

Equivalent to pthread_mutex_lock/unlock, with one critical difference: any thread can sem_post, not just the owner. That’s a bug for mutex-style use (you lose ownership tracking) but a feature for cross-thread signalling.

Ordering semaphore (K = 0)#

sem_t done; sem_init(&done, 0);

void parent(void) {
    pthread_create(&child, NULL, child_fn, NULL);
    sem_wait(&done);     // block until child posts
}
void* child_fn(void* a) {
    // setup work ...
    sem_post(&done);
    return NULL;
}

Initialised to zero, sem_wait always blocks first. The first sem_post releases the waiter. This is pthread_join in spirit but without reclaiming the thread.

Readers-writers#

sem_t rw;      // exclusion against writers (init 1)
sem_t reader_lock; // protects reader count (init 1)
int readers = 0;

void rlock(void) {
    sem_wait(&reader_lock);
    if (++readers == 1) sem_wait(&rw);  // first reader excludes writers
    sem_post(&reader_lock);
}
void runlock(void) {
    sem_wait(&reader_lock);
    if (--readers == 0) sem_post(&rw);  // last reader lets writers in
    sem_post(&reader_lock);
}
void wlock(void)   { sem_wait(&rw); }
void wunlock(void) { sem_post(&rw); }

This is the classic “first reader / last reader” pattern. Writers starve when readers stream continuously; production rwlocks add fairness via a turnstile semaphore.

Dining philosophers#

Five philosophers, five forks; each needs both adjacent forks to eat. Naive: each grabs left then right — deadlocks when all grab left simultaneously. Fix: break the symmetry. One philosopher (say number 4) grabs right then left; the others grab left then right. The cycle is broken; no deadlock.

sem_t fork[5];
void philosopher(int i) {
    while (1) {
        think();
        if (i == 4) { sem_wait(&fork[(i+1)%5]); sem_wait(&fork[i]); }
        else        { sem_wait(&fork[i]); sem_wait(&fork[(i+1)%5]); }
        eat();
        sem_post(&fork[i]); sem_post(&fork[(i+1)%5]);
    }
}

The lesson generalises: deadlock comes from circular wait; break the cycle by imposing a total acquisition order.

Variants#

POSIX named vs. unnamed#

• sem_init / sem_destroy — anonymous semaphores in process-private or shared memory. macOS stubs sem_init to ENOSYS; use named semaphores there.
• sem_open / sem_close / sem_unlink — named semaphores in the filesystem namespace, shareable across unrelated processes.

System V semaphores#

semget / semop / semctl — older, IPC-style, support semaphore sets and undo-on-exit. Rare in new code; POSIX semaphores are the preferred surface.

dispatch_semaphore_t (Apple GCD)#

macOS / iOS lock-free semaphore backed by Mach. Faster than POSIX sem_t on Apple platforms.

std::counting_semaphore (C++20)#

Type-safe wrapper around the OS semaphore; acquire and release instead of wait and post.

Higher-level: Java’s Semaphore, Go’s buffered channel of struct#

Same semantics, friendlier API. A buffered Go channel of capacity K is essentially a counting semaphore — <-ch and ch <- struct{}{} are wait and post.

Trade-offs#

Other tensions:

• Anonymous ownership. A mutex is owned by the locker; only the owner unlocks it. A semaphore has no owner — any thread can post. Power and footgun in equal measure.
• Fairness. POSIX leaves it unspecified. Some implementations are FIFO, some aren’t. If you need strict fairness (e.g. avoiding writer starvation in RW), build it explicitly with a queue semaphore.
• Compositionality. Combining semaphores is brittle — three semaphores have 3! possible acquire orders and most produce deadlock. CVs with a single mutex compose better.

Common pitfalls#

• Forgetting the mutex around buffer state. Two semaphores gate access to slots, but with multiple producers writing tail, you still need a mutex on the index. Single-producer / single-consumer can skip it.
• Wrong initial values. “Counts empty slots” must start at N; “counts filled slots” must start at 0. Swap them and producers wake up to write into a non-existent buffer.
• Posting too few or too many. Each wait should pair with exactly one eventual post. A leaked wait blocks forever; a leaked post lets too many threads in.
• Cancelling a thread mid-wait. If you pthread_cancel a thread between sem_wait and the matching sem_post, the counter drifts. Use cooperative shutdown, not cancellation.
• Using a binary semaphore as a mutex across owners. Works mechanically but loses ownership semantics, priority inheritance, and recursive-lock safety. Use a real mutex.
• Treating semaphore order as guaranteed. POSIX sem_post does not promise to wake the longest-waiting thread. If you depend on order, layer a queue on top.
• sem_init(&s, 1, ...) on macOS. The middle argument is “pshared.” macOS doesn’t implement pshared semaphores via sem_init; the call returns ENOSYS. Use sem_open or dispatch_semaphore_t.

Related building blocks#

• Locks and Spinlocks — a binary semaphore with ownership.
• Condition Variables — the richer predicate cousin.
• Threads and Shared State — the world semaphores coordinate.
• POSIX Threads API — where sem_t lives.
• Concurrency Bugs — Deadlock, Atomicity, Order — how semaphore code deadlocks.