Semaphores
Imagine two threads that must coordinate. One produces data into a shared buffer, one consumes it. A plain Locks and Mutual Exclusion can protect the buffer from corrupted concurrent writes. But it cannot tell the consumer "wait, there is nothing to consume yet." Nor can it tell the producer "wait, the buffer is full." Mutual exclusion answers who may enter, not when should I wait. Real systems constantly need both: protecting shared state and sequencing events between threads. Semaphores solve this gap with a single, elegant abstraction. It is an integer counter, manipulated only through two atomic operations. This counter can simultaneously enforce exclusion and encode "how many resources are available" or "how many events have happened." Edsger Dijkstra introduced semaphores in 1965 as part of the THE multiprogramming system. The idea has since become one of the most durable primitives in concurrent programming. It is implemented in every mainstream operating system kernel. It is used to bound thread pools, throttle database connections, implement producer-consumer pipelines, and build higher-level synchronization constructs. The genius of the semaphore is that it unifies two problems that look different on the surface. These are mutual exclusion (binary semaphores) and resource counting or signaling (counting semaphores). It unifies them into one data type with one interface. This article gives you the precise definition of a semaphore. It also provides a correct implementation strategy for `wait` and `signal`. You will see a proof that the invariant these operations maintain is never violated. Finally, there is a worked trace showing how counting semaphores coordinate a bounded buffer. This sets up direct applications in Using Semaphores: Mutual Exclusion and Signaling and comparison against Condition Variables. By the end, you should be able to state the semaphore invariant precisely. You should be able to implement a semaphore atop a spinlock and a wait queue. You should be able to reason about why the implementation cannot deadlock or lose wakeups. And you should recognize when a semaphore is the right tool. Alternatively, you should know when a mutex-plus-condition-variable pair is cleaner.
- A semaphore is an integer counter `S` manipulated only through atomic `wait(S)` (decrement, block if negative) and `signal(S)` (increment, wake a waiter if any).
- Binary semaphores (initialized to 1) act like locks; counting semaphores (initialized to N) track N available resources or N pending events.
- Semaphores unify mutual exclusion and thread signaling/ordering in a single abstraction — something a plain lock cannot do alone.
- A correct implementation needs an internal spinlock plus a blocking wait queue; the invariant `S.value = initial + #signals − #completed waits` must be maintained atomically.
- Complexity of `wait`/`signal` is O(1) for the counter update; wakeup cost is O(1) amortized with a FIFO queue (worst case O(1) per dequeue).
- Misuse — swapped wait/signal order, missing signal on an error path, forgetting the initial value — causes deadlock or race conditions, not crashes, making bugs hard to find.
A semaphore is an atomically-updated counter with blocking decrement (`wait`) and waking increment (`signal`), general enough to express both mutual exclusion and event ordering.
The idea
A semaphore is an object holding a non-negative-in-spirit integer value `S` together with a queue of waiting threads, exposed through exactly two operations, traditionally called `P`/`V` (from Dutch proberen/*verhogen*, Dijkstra's original notation) or `wait`/`signal` (Silberschatz's notation) or `down`/`up` (Unix/Linux notation). Both operations are atomic: once a thread begins one, no other thread can observe an intermediate state or interleave its own semaphore operation on the same variable. `wait(S)` (also `P(S)` or `down(S)`) decrements `S`. If the resulting value is negative, the calling thread blocks — it is removed from the ready queue, placed on the semaphore's wait queue, and yields the CPU, exactly as in a Spinlocks versus Blocking Locks blocking lock. `signal(S)` (also `V(S)` or `up(S)`) increments `S`. If there are threads waiting, one of them is moved from the wait queue to the ready queue. The key conceptual shift from a plain lock is that a semaphore's value is not restricted to `{0, 1}`. A binary semaphore (initial value 1) behaves like a mutex: at most one thread can successfully complete `wait` before a matching `signal`. A counting semaphore (initial value N) models N interchangeable resources — N free buffer slots, N available connections, N permits — and also models "number of events that have occurred but not yet been consumed," which is exactly the signaling capability a raw mutex lacks. This dual nature — exclusion device and event counter — is why semaphores can implement both classic mutual exclusion and producer-consumer style ordering with the same primitive.
How it works
The abstract contract is simple, but building an implementation that is actually atomic and race-free requires care. The standard approach layers a blocking semaphore on top of a cheap internal spinlock (or on top of kernel-level interrupt disabling, in a uniprocessor kernel) that protects a tiny critical section: the read-modify-write of the counter and the enqueue/dequeue of waiting threads.
Semaphore state:
- `value`: integer, may be initialized to any non-negative number.
- `queue`: FIFO list of blocked threads.
- `lock`: an internal spinlock guarding `value` and `queue`.
Step-by-step for `wait(S)`: 1. Acquire the internal spinlock `S.lock`. 2. Decrement `S.value`. 3. If `S.value < 0`, the calling thread must block: add it to `S.queue`, release `S.lock`, and put the thread to sleep (context switch away). When later woken by a `signal`, resume here and return. 4. If `S.value >= 0`, release `S.lock` and return immediately — the thread proceeds.
Step-by-step for `signal(S)`: 1. Acquire the internal spinlock `S.lock`. 2. Increment `S.value`. 3. If `S.value <= 0`, there is at least one waiting thread (because increments and decrements are paired against the invariant below): remove one thread from `S.queue` and wake it (place it on the ready queue). 4. Release `S.lock` and return. The delicate part is step 3 of `wait`: the thread must be enqueued and marked "sleeping" before the lock is released, otherwise a `signal` from another thread could run between "decide to block" and "actually go to sleep," and the wakeup would be lost forever (the lost-wakeup problem). Real kernels solve this by holding the spinlock across the transition into the sleep state, or by an equivalent atomic "enqueue-then-release-then-switch" sequence guaranteed by the scheduler. ``` structure Semaphore: value: integer // may go negative while threads wait queue: FIFO list of Thread lock: SpinLock // protects value and queue function Semaphore.init(S, initial): S.value = initial S.queue = empty S.lock = new SpinLock() function wait(S): // a.k.a. P(S), down(S) acquire(S.lock) S.value = S.value - 1 if S.value < 0: enqueue(S.queue, current_thread) // Must atomically release lock and sleep so no signal // is lost between the two steps (handled by scheduler). release_and_sleep(S.lock) // Execution resumes here only after being signaled/woken. else: release(S.lock) return function signal(S): // a.k.a. V(S), up(S) acquire(S.lock) S.value = S.value + 1 if S.value <= 0: t = dequeue(S.queue) wake(t) // move t to ready queue release(S.lock) return ``` Two implementation notes worth internalizing. First, `S.value` can legitimately be negative in this classic formulation; when negative, `−S.value` equals the number of threads currently blocked in the wait queue. Some textbooks present a variant where `value` never goes below zero and the waiter count is tracked separately — behaviorally identical, just a different bookkeeping choice. Second, `release_and_sleep` denotes an atomic hand-off to the scheduler: the spinlock must not be released until the thread is safely on the sleep queue and cannot miss a concurrent wakeup, a pattern that reappears in Condition Variables as the "sleep atomically with respect to the mutex" requirement.
Complexity & correctness
Time complexity. Each `wait` or `signal` call does O(1) work on the counter itself: acquire a spinlock, adjust an integer, optionally enqueue/dequeue one thread from a FIFO list (O(1) with a doubly linked list or ring buffer), release the spinlock. The spinlock acquisition itself is O(1) expected time under low contention (a handful of atomic compare-and-swap retries), though under a pathological worst case with many contending cores it can degrade — the same caveat that applies to any spinlock-protected critical section, discussed in Spinlocks versus Blocking Locks. The actual context switch triggered when a thread blocks or is woken is not counted as part of the semaphore operation's asymptotic cost but is a real constant-factor cost (typically microseconds) that motivates using semaphores (which yield the CPU) rather than busy-waiting when blocking may be long.
Space complexity. O(1) for the counter plus O(k) for the wait queue, where k is the number of currently blocked threads — bounded by the number of threads in the system, not by anything semaphore-specific.
Correctness argument. The central claim to verify is: > Invariant I: At every moment (i.e., outside any `wait`/`signal` critical section), `S.value = S₀ + (#completed signal calls) − (#completed wait calls)`, where S₀ is the initial value. Moreover the number of threads currently blocked equals `max(0, −S.value)`. Proof sketch. Each `wait` and `signal` executes its counter update while holding `S.lock`, so updates are linearizable: they behave as if executed in some total, one-at-a-time order, even though the calling threads run on different cores. By induction on this total order:
- Base case: before any operation, `S.value = S₀`, and I holds trivially (zero completed calls of either kind, zero blocked threads).
- Inductive step for `wait`: suppose I holds before the k-th operation. If it is a `wait`, `value` decrements by 1, matching the "−1 completed wait" term. If the resulting value is negative, the thread enqueues before releasing the lock and sleeping — this ordering is essential, because it guarantees that any `signal` that runs after this point (and therefore sees the decremented value) will find a matching entry in the queue to wake.
- Inductive step for `signal`: `value` increments by 1, matching the "+1 completed signal" term. If the pre-increment value was negative (equivalently post-increment `value <= 0`), invariant I guarantees at least one thread is in the queue — that thread is dequeued and woken. This is exactly why the wakeup is never sent to an empty queue and never lost: the invariant is checked and acted on atomically, inside the same critical section that produced the count that justified it.
From this invariant, two safety properties follow directly: 1. No spurious blocking beyond capacity. A thread only blocks in `wait` when `value < 0`, which by I means the count of unmatched waits already exceeds the count of unmatched signals — exactly the condition under which no resource/permit is available, so blocking is the correct behavior, not a bug. 2. No lost wakeup. Because enqueue happens strictly before the blocking thread releases the lock (and the corresponding `signal` cannot proceed past its own lock acquisition until the block-and-release completes), there is no window in which a `signal` can find the queue "not yet updated" and thus skip waking a thread that will end up sleeping forever. This is the precise atomicity requirement that also justifies condition variables' "release mutex and sleep atomically" contract.
Liveness (no deadlock from the semaphore mechanism itself). If `signal` is always eventually called after each `wait` that would need it — i.e., the program logic pairs waits and signals correctly — then invariant I guarantees the queue is drained: every blocked thread corresponds to a "debt" that a future `signal` will pay off, in FIFO order if the implementation dequeues FIFO. The semaphore mechanism cannot deadlock on its own; deadlocks arise only from incorrect use (e.g., two semaphores acquired in opposite orders by two threads), a distinct problem from the correctness of the primitive itself.
Tradeoffs. Semaphores are simple and general but offer weaker structure than mutex+condition-variable pairs: a semaphore's counter conflates "how many resources" with "how many threads are waiting," which can make code that uses semaphores for complex signaling harder to read than equivalent condition-variable code, because the semantic intent (mutual exclusion vs. event count) is not visible in the type. Semaphores also do not natively support operations like "wait until predicate P holds" without manual encoding, whereas condition variables are built for exactly that.
Worked example
Trace a bounded buffer of capacity 3 using two counting semaphores plus a binary semaphore for exclusion — the canonical producer-consumer pattern that foreshadows Using Semaphores: Mutual Exclusion and Signaling.
- `mutex` = binary semaphore, initial 1 (protects the buffer array/indices).
- `empty` = counting semaphore, initial 3 (number of free slots).
- `full` = counting semaphore, initial 0 (number of filled slots).
``` producer(): consumer(): wait(empty) wait(full) wait(mutex) wait(mutex) buffer.insert(item) item = buffer.remove() signal(mutex) signal(mutex) signal(full) signal(empty) ``` Trace with one producer P and one consumer C, buffer capacity 3, starting empty:
| Step | Thread | Operation | `empty` before→after | `full` before→after | `mutex` before→after | Effect |
|---|---|---|---|---|---|---|
| 1 | P | `wait(empty)` | 3 → 2 | — | — | slot reserved, proceeds |
| 2 | P | `wait(mutex)` | — | — | 1 → 0 | enters critical section |
| 3 | P | insert item A | — | — | — | buffer = [A] |
| 4 | P | `signal(mutex)` | — | — | 0 → 1 | exits critical section |
| 5 | P | `signal(full)` | — | 0 → 1 | — | announces 1 item ready |
| 6 | C | `wait(full)` | — | 1 → 0 | — | consumes the announcement |
| 7 | C | `wait(mutex)` | — | — | 1 → 0 | enters critical section |
| 8 | C | remove item A | — | — | — | buffer = [] |
| 9 | C | `signal(mutex)` | — | — | 0 → 1 | exits critical section |
| 10 | C | `signal(empty)` | 2 → 3 | — | — | frees the slot back |
Now consider the case that actually tests the blocking behavior: the buffer is full (three items produced, none consumed) and a fourth producer call arrives.
| Step | Thread | Operation | `empty` before→after | Effect |
|---|---|---|---|---|
| 11–19 | P (×3 more) | full cycle each | 3→2→1→0 | buffer now holds 3 items, `empty = 0` |
| 20 | P (4th call) | `wait(empty)` | 0 → −1 | `value < 0` ⇒ P blocks, enqueued on `empty`'s wait queue |
| 21 | C | `wait(full)`, `wait(mutex)`, remove item, `signal(mutex)` | — | consumer drains one item |
| 22 | C | `signal(empty)` | −1 → 0 | since result `≤ 0`, dequeue and wake the blocked P |
| 23 | P | resumes inside `wait(empty)`, returns | — | proceeds to insert its item |
This trace shows exactly the invariant from the correctness section in action: at step 20, `empty.value` goes negative, which by invariant I means "one more wait has been requested than there are matching signals so far" — correctly forcing the 4th producer to block rather than overwrite data. At step 22, `signal(empty)` observes `value <= 0` after incrementing and therefore knows — without any separate bookkeeping — that a thread is waiting, and wakes exactly one, restoring capacity for exactly one more producer, never more.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Swapping the order of `wait(mutex)` and `wait(empty)`/`wait(full)` | Programmer treats all semaphore waits as interchangeable | Deadlock: e.g. consumer holds `mutex` then blocks forever on `wait(full)` while producer cannot get `mutex` to signal `full` |
| Forgetting `signal` on an error/exception path | Early `return` inside a critical section skips cleanup | Permanent resource leak — semaphore count never recovers, eventually every thread blocks forever |
| Using a binary semaphore where a counting semaphore is needed (or vice versa) | Confusing "at most one" with "up to N" | Under-utilized resource pool, or unintended unbounded concurrent access |
| Calling `signal` more times than `wait` ("phantom" signals) | Bug in bookkeeping, or signaling a semaphore from wrong code path | Semaphore's value drifts above intended maximum; mutual exclusion or counting guarantee silently broken |
| Assuming FIFO fairness without checking the implementation | Textbook diagrams often draw a queue, but some implementations wake an arbitrary blocked thread | A thread can starve indefinitely even though signals keep arriving, if the OS scheduler doesn't guarantee FIFO wakeup order |
| Using a semaphore where a condition variable's predicate check is really needed | Semaphore counters don't express arbitrary conditions cleanly | Code becomes hard to read/maintain; easy to miscount when multiple conditions interact |
Pioneers & history
Origins · 1 minEdsger Wybe Dijkstra and how this was discovered
Dijkstra designed the semaphore as part of building the THE operating system, one of the first systems structured as cooperating sequential processes running on primitive hardware with no built-in synchronization support. He needed a mechanism general enough to express both mutual exclusion between processes sharing memory and producer-consumer style handoffs between a process and its I/O — and the semaphore, with its P and V operations, was his answer, published internally and then in his seminal 1968 paper "Cooperating Sequential Processes." Dijkstra was also a pioneer of structured programming and formal reasoning about concurrent correctness, insisting that synchronization primitives be provable rather than merely "seem to work."
Where this matters
Operating system kernels use semaphores internally to guard device drivers, protect kernel data structures before finer-grained locks became dominant, and to implement blocking I/O completion signals. Linux exposes both a kernel-internal `struct semaphore` and POSIX semaphores (`sem_t`) in user space, and uses semaphore-like counting for resources such as available file descriptors in some subsystems. Database connection pools use counting semaphores to cap the number of concurrent connections a client may open — `wait` before checking out a connection, `signal` when returning it. Thread pool implementations use semaphores to throttle the number of concurrently executing tasks. Producer-consumer pipelines in media processing, networking stacks, and message queues (bounded queues in Java's `java.util.concurrent`, Python's `threading.Semaphore`, Go's buffered channels which internalize similar semantics) all trace their coordination logic back to the same `wait`/`signal` invariant proved above. Understanding semaphores is also the direct prerequisite for understanding Condition Variables, which trade some of the semaphore's generality for a cleaner separation between "the lock" and "the wait-for-a-condition" logic, and for understanding classic synchronization problems like readers-writers and dining philosophers that appear throughout Using Semaphores: Mutual Exclusion and Signaling.
Ask the tutor: How would the wait/signal implementation change if I need the wait queue to guarantee strict FIFO wakeup fairness across all waiting threads?
Can a semaphore's value ever be observed as a fractional or non-integer number?
No. A semaphore's value is always an integer by definition, changed only by whole-unit increments (`signal`) and decrements (`wait`). It can, in the classic implementation, go negative — a negative value simply encodes the number of threads currently blocked waiting for a signal, as shown by the invariant `#blocked = max(0, −value)`. Some textbook variants clamp the externally visible "resource count" at zero and track waiter count in a separate field, which is behaviorally equivalent but avoids showing students a negative number. Either way, there is no notion of a semaphore holding a "partial" unit of a resource; it is a discrete counting abstraction, matching its use for indivisible resources like buffer slots, connections, or permits.
How is a semaphore different from a plain mutex, if a binary semaphore can act like one?
A mutex is typically defined with the additional constraint of ownership: only the thread that acquired (locked) the mutex is allowed to release (unlock) it, and many implementations detect or forbid violations of this rule. A binary semaphore has no notion of ownership — any thread can call `signal` on a semaphore, even one it never called `wait` on. This makes semaphores strictly more flexible for signaling between different threads (e.g., a producer signals a semaphore that only a consumer ever waits on) but also more dangerous for pure mutual exclusion, since a bug can accidentally `signal` a mutex-like semaphore from the wrong place, silently corrupting the exclusion guarantee without any ownership check to catch it.
Why does signal() check `value <= 0` rather than `value == 0` before waking a thread?
Because of how the classic implementation's counter behaves once at least one thread is blocked. Suppose `value` was `-2` (two threads waiting) and `signal` increments it to `-1`: the post-increment value is negative, not zero, yet there is still one waiting thread that must be woken because the pre-increment negative value already indicated debt. The condition `value <= 0` after incrementing correctly captures "there was at least one waiter before this increment," across the whole range of negative values, not just the single case where the counter crosses exactly to zero. Using `== 0` would fail to wake threads whenever more than one thread was queued.
Are semaphores still relevant given higher-level concurrency libraries in modern languages?
Yes, directly. Java's `java.util.concurrent.Semaphore`, Python's `threading.Semaphore` and `asyncio.Semaphore`, C#'s `SemaphoreSlim`, and POSIX `sem_t` all expose the same `wait`/`signal` (called `acquire`/`release` in many APIs) contract described here, because it remains the simplest correct way to bound concurrent access to a fixed-size resource pool. Under the hood, kernel scheduling primitives for blocking a thread and futex-based fast paths in Linux are themselves often semaphore-like counters. Higher-level constructs like async/await task schedulers and reactive streams still use semaphore-equivalent counters to implement backpressure and concurrency limits, so the abstraction has not been replaced, only wrapped in friendlier syntax.
Why can two semaphores together cause a deadlock even though each one individually is proven correct?
The correctness proof above only guarantees that a single semaphore's counter and wait queue behave consistently with its own invariant — it says nothing about the order in which a program acquires multiple different semaphores. Deadlock is a property of the program's usage pattern, not of the semaphore primitive: if thread A does `wait(X)` then `wait(Y)` while thread B does `wait(Y)` then `wait(X)`, both can end up holding one and blocking on the other, a circular-wait condition classically analyzed with resource-allocation graphs. The fix is a discipline external to the semaphore itself — consistent lock/semaphore ordering across all threads — not a change to `wait`/`signal`'s internals.
What happens if you call signal() on a semaphore before any thread has called wait() on it?
This is perfectly well-defined and often intentional: it simply increases `value`, meaning a future `wait` call will succeed immediately without blocking, consuming that "banked" signal. This is exactly how semaphores are used for producer-first scenarios — a producer can run ahead of a consumer and call `signal(full)` repeatedly (up to the buffer's capacity) before any consumer has started, and each of those signals will be immediately available to satisfy a later `wait(full)`. This is a deliberate feature distinguishing semaphores from naive "notify" mechanisms that lose a notification if no one is listening yet — the counter itself remembers unconsumed signals.
How do you choose the initial value when creating a semaphore?
The initial value should equal the number of units of the resource being modeled, or zero if the semaphore is purely for signaling an event that has not yet occurred. For mutual exclusion, initialize to 1 (one "permit" to enter the critical section). For a resource pool of size N (buffer slots, connection limit, worker threads), initialize to N. For a pure "has this event happened yet" signal, initialize to 0, so the first `wait` blocks until the first `signal` announces the event — this is the pattern used for `full` in the producer-consumer example, where no items exist until a producer creates one.