Semaphores and Condition Variables

Dijkstra’s semaphore (1965) is an integer with two atomic operations. wait (P, acquire, down): if the count is greater than zero, decrement and continue; otherwise block until it is. signal (V, release, up): increment, and if anyone is blocked, wake one. A semaphore initialised to N admits N concurrent holders; initialised to 1 it admits one; initialised to 0 it admits nobody until someone signals — which makes it a pure signalling device.

There is no owner. Any thread may signal, including one that never called wait, including an interrupt handler. That is the feature: a producer signals a consumer, a completion signals a waiter, a worker releases a slot it did not itself take. It is also the reason a semaphore is the wrong tool for mutual exclusion — nothing stops a bug from signalling twice, the runtime cannot detect a double release or a release by a stranger, and priority inheritance is impossible because there is no holder to inherit to. Mutexes covers what ownership buys.

POSIX gives sem_init/sem_wait/sem_post (unnamed, in-process or in shared memory) and sem_open (named, across processes). C++20 has std::counting_semaphore<N> and std::binary_semaphore. Python has threading.Semaphore(n) and asyncio.Semaphore(n); Go idiomatically uses a buffered channel of capacity N as a semaphore; Java has java.util.concurrent.Semaphore. Under Linux all the thread-level ones are the futex word of Mutexes with a count instead of a bit.

A database connection is a socket (File Descriptors), a server-side process or thread, and memory on both ends; the server caps them (max_connections, commonly 100) and each one you hold idle costs the server something. So the client keeps a pool of, say, 10 open connections and hands them out. The gate on the pool is a counting semaphore with 10 permits: a handler acquires a permit, checks out a connection, runs its queries, checks the connection back in and releases the permit. Forty concurrent handlers means ten working and thirty blocked in acquire, in order, without spinning.

The semaphore is the *admission* control; a mutex still guards the pool’s internal free-list for the microseconds it takes to pop or push a connection. Separating the two is the point: the mutex is held for nanoseconds, the permit for the whole query — milliseconds — and you never want a mutex held for milliseconds (Critical Sections). HikariCP, pgbouncer’s client side, SQLAlchemy’s QueuePool, and every serious HTTP client pool have exactly this structure.

What the pool does under saturation is a policy decision the semaphore exposes: block forever (acquire()), block with a timeout (acquire(timeout=2.0) → fail fast with a 503 rather than pile up), or try_acquire and shed load. Unbounded waiting is how a slow database turns into a thread pool full of blocked handlers and then into an outage of everything else the process does; a timeout on the permit is the cheapest circuit breaker there is.

A bounded buffer of N slots between producers and consumers is the textbook use of two counting semaphores plus a mutex. empty starts at N and counts free slots; full starts at 0 and counts filled ones. A producer wait(empty), locks the buffer, inserts, unlocks, signal(full). A consumer wait(full), locks, removes, unlocks, signal(empty). Producers block only when the buffer is full and consumers only when it is empty; the mutex protects the few instructions that touch the index and the array. Backpressure is the wait(empty): a fast producer is slowed to the consumer’s pace instead of growing memory without bound (What Happens When the Receiver Is Slow is the same idea in the network stack).

The ordering rule is the trap: take the semaphore *before* the mutex. A producer that locks the mutex first and then waits on empty holds the lock while sleeping, so the consumer that would free a slot cannot take the lock to do it — a deadlock with two primitives and one thread each. Kernel pipes (Pipes: A Kernel Buffer Between Two Processes), queue.Queue(maxsize=N) in Python, BlockingQueue in Java and Go’s buffered channels are all this pattern packaged.

A semaphore initialised to 1 looks like a mutex and is not one. It has no owner, so it cannot check that the releaser is the acquirer, cannot support priority inheritance, cannot be recursive, and its typical use is different: a thread waits on it for *another* thread to signal that something happened — a handoff, not a guard. Use a mutex to protect state; use a binary semaphore to signal an event once. Confusing the two is a common interview trap (mutex-vs-semaphore-q) because the code looks identical and the failure modes do not.

The third primitive, the condition variable, exists because neither of the others expresses "wait until some predicate over shared state becomes true". A condvar is always paired with a mutex: wait(cv, m) atomically releases m and sleeps; when woken it re-acquires m and returns. The waiter checks the predicate *in a loop*, because wake-ups may be spurious and because another thread may have consumed the condition between the notify and the re-acquire. notify_one wakes one waiter; notify_all wakes all — which, with many waiters, is the thundering herd that a counting semaphore avoids by design. C++ std::condition_variable, Python threading.Condition, Java’s Object.wait/notify, pthreads’ pthread_cond_t: identical semantics everywhere.

The three compose. A semaphore can be built from a mutex and a condvar (count under the mutex, wait while zero); a bounded queue from a mutex and two condvars (not_empty, not_full); a thread pool from a queue and a condvar. Knowing which one you are actually expressing — exclusion, admission, or predicate — tells you which to reach for.

Most concurrency limits in a backend are semaphores in disguise. A bulkhead — at most 20 concurrent calls to the payments service so a slow dependency cannot absorb every thread — is a semaphore with 20 permits and a timeout. A token-bucket rate limiter is a semaphore that a timer thread refills at R permits per second, with a cap of B; acquire is the request and the count is the bucket. Concurrency limits in asyncio (Semaphore(50) around outbound HTTP), Go’s errgroup.SetLimit, Kubernetes’ per-pod connection limits, and nginx’s limit_conn are all the same primitive at different altitudes.

The design questions are always the same: how many permits (the dependency’s real capacity, not a guess), what to do when none are free (block, time out, shed), and whether the wait queue is fair. Get the first wrong and you either under-use the dependency or overwhelm it; the second wrong and a slow dependency propagates as a hung service; the third wrong and one client’s burst starves another’s steady trickle.