The idea: a counter of permits

A semaphore is a counter that never goes below 0, plus a queue of sleeping threads. It has two operations (Dijkstra's P and V):

  • sem_wait(&s): if the value is above 0, take one (value−−) and go on. If it is 0, sleep until someone posts.
  • sem_post(&s): if a thread sleeps, wake it and give it the permit. Otherwise add one (value++).

The value is the number of permits left. Unlike a mutex, which lets exactly one thread in, a semaphore that starts at N lets up to N threads in. A semaphore that starts at 0 is a signal from one thread to another.

How to use the animation

Each thread has its own CPU. Pick a scenario tab, then Step Tick or Run to End. The box under SHARED MEMORY is the semaphore's value. A thread that has to wait goes to sleep in the kernel's wait queue and its CPU turns grey (free). The strip at the bottom shows every CPU's ticks.

A pool of N

A program has 2 database connections and more threads that want one. sem_init(&pool, 0, 2) creates a semaphore with 2 permits. In Pool of 2 T1 and T2 take the two permits at tick 2 (2 → 1 → 0). T3 asks at tick 3, finds 0 and sleeps. At tick 7 T1 posts: T3 is asleep, so the permit goes straight to T3 and the value stays 0. Never more than 2 threads use the pool.

Before and after. At tick 3 T1 and T2 each hold a permit and use a connection, the value pool is 0, and T3 sleeps in the kernel wait queue after sem_wait. At tick 7 T1 calls sem_post: the permit goes straight to T3, which now uses the connection with T2; the value stays 0 and the queue is empty.
A semaphore starting at 2 lets at most two threads in; a post with a sleeper waiting hands the permit straight to it.
sem_wait(&pool);        /* take a permit, or sleep */
use_connection();
sem_post(&pool);        /* give it back, or wake a sleeper */

A signal between threads

A semaphore that starts at 0 makes one thread wait for another. In Signal: wait, then post T2 needs data that T1 is still preparing. T2's sem_wait(&ready) finds 0 and sleeps; when T1 has written the data it calls sem_post(&ready), which wakes T2.

In Post first is remembered T1 posts before T2 waits. Nobody sleeps, so the value goes up to 1. When T2 calls sem_wait later it takes that 1 and goes on at once, with no system call at all. A condition variable has no such memory: a signal with nobody waiting is lost, which is why it is always used with a flag and a mutex (see Bounded Buffer).

Two time-downward sequences with lanes T1, ready and T2. Left: T2 calls sem_wait on ready = 0 and sleeps while T1 writes the data; T1 calls sem_post, which wakes T2. Right: T1 posts first, so ready goes from 0 to 1; later T2's sem_wait takes the 1 (back to 0) and goes on without sleeping.
A semaphore that starts at 0 is a signal: whichever comes first, wait or post, T2 runs only after T1's data is ready.

No owner

A mutex belongs to the thread that locked it, and only that thread may unlock it (an error-checking mutex returns EPERM otherwise). A semaphore has no owner: any thread may post, and that is exactly what makes signalling possible. The price is that a mistake goes unnoticed. In No owner: stray post T4 calls sem_post(&pool) without ever waiting. The value becomes 1 while the pool is full, T3 walks in, and 3 threads use 2 connections ✗. The extra permit never goes away: the run ends with the value at 3.

MutexSemaphore
Threads inside1up to the initial value
Owneryes, only the owner unlocksno, anyone posts
Remembers a release with nobody waitingit is simply freeyes, the value goes up
Typical useprotect shared datalimit to N, signal an event, count items

Where you meet it

  • POSIX: sem_init/sem_wait/sem_post (unnamed, in memory, futex-based on Linux) and sem_open (named, shared between processes). System V: semget/semop.
  • Java: java.util.concurrent.Semaphore with acquire()/release(); C++20: std::counting_semaphore.
  • Linux kernel: struct semaphore with down()/up().
  • Classic problems: Bounded Buffer uses three semaphores (empty, full, mutex), Readers–Writers and Dining Philosophers too.

What the page leaves out

  • How glibc does it: the value lives in user memory, and sem_wait takes a permit with an atomic instruction, calling futex_wait only at 0, like the mutex. Here a post hands the permit straight to a sleeper; in glibc the woken thread takes it again itself.
  • sem_trywait (fails with EAGAIN instead of sleeping) and sem_timedwait.
  • Fairness: which sleeper is woken first, and threads that arrive just as a permit is posted.
  • Real timing: a system call and a context switch cost far more than one tick.