Using Semaphores: Mutual Exclusion and Signaling
Imagine three threads sharing a bank account balance. Imagine a printer spooler shared by a dozen processes. Imagine a video decoder thread that must wait until a network thread has filled a buffer. These look like unrelated problems, but they share a single deep structure: uncontrolled interleaving of concurrent operations. Without discipline, two threads can read-modify-write the same memory at the same time and silently corrupt it. Or a consumer can race ahead of a producer that hasn't produced anything yet. Operating systems solved this class of problems decades ago with a single, remarkably small primitive — the semaphore. The craft of concurrent programming is largely the craft of using it correctly. This article is about usage patterns, not the semaphore's internal machinery. You should already know that machinery from studying Semaphores themselves. Given a working `wait` (P) and `signal` (V) operation, how do you actually build correct programs? The surprising answer is that nearly every classical synchronization problem — mutual exclusion, ordering constraints, resource pools, rendezvous — reduces to a small number of semaphore idioms. These idioms are applied with care about initial values and placement of `wait`/`signal` calls. The big picture: a semaphore is just an integer counter with two atomic operations and a queue of blocked threads. But how you initialize it and where you place P/V calls encodes completely different semantics. Initializing to 1 gives you a lock. Initializing to 0 gives you a signaling channel. Initializing to N gives you a resource pool with N slots. Splitting `wait`/`signal` across different threads (rather than always pairing them in the same thread) turns mutual exclusion into ordering. This flexibility is exactly what makes semaphores dangerous. The compiler and runtime enforce none of these conventions. So correctness lives entirely in the programmer's discipline. This article delivers the core patterns — mutual exclusion, ordering/rendezvous, and resource counting. It includes pseudocode you can adapt directly, and a state-machine diagram of a semaphore in action. It also includes a full worked trace showing an interleaving that would break without synchronization. Finally, it offers a catalogue of the bugs that recur across student code and production systems alike. It sets up the two canonical case studies that build on these patterns: The Producer-Consumer Problem and The Readers-Writers Problem.
- A semaphore is an integer counter with atomic `wait` (decrement, block if negative) and `signal` (increment, wake a waiter) operations.
- Binary semaphores initialized to 1 implement mutual exclusion: critical sections that only one thread executes at a time.
- Semaphores initialized to 0 implement signaling/ordering: one thread's `signal` releases another thread's `wait`, enforcing "B happens after A."
- Counting semaphores initialized to N implement resource pools: exactly N concurrent users of a bounded resource, no more.
- Correctness requires reasoning about invariants tied to the counter's value, not just "it seems to work" testing.
- Misplaced `wait`/`signal` calls cause deadlock, missed signals, or lost mutual exclusion — these bugs are common and often nondeterministic.
A semaphore's initial value and the pairing (or deliberate unpairing) of its wait/signal calls determine whether it enforces mutual exclusion, ordering, or resource counting — the primitive is fixed, but the pattern is everything.
The idea
A semaphore `S` is a protected integer variable manipulated only through two atomic operations, conventionally called `wait(S)` (also `P` or `down`) and `signal(S)` (also `V` or `up`). Conceptually, `wait` decrements `S` and blocks the calling thread if the result would be negative; `signal` increments `S` and, if there are blocked threads, wakes exactly one of them. The semaphore's implementation guarantees that these operations are indivisible with respect to each other — no two threads can be "inside" `wait` or `signal` on the same semaphore simultaneously — and that a queue of waiting threads is maintained fairly (typically FIFO, though the specification only requires eventual progress). The crucial insight for using semaphores well is that the same primitive supports three distinct roles, distinguished only by convention: 1. Mutual exclusion (binary semaphore / mutex pattern). Initialize `S = 1`. Every thread executes `wait(S)` immediately before entering a critical section and `signal(S)` immediately after leaving it. The invariant `S ∈ {0, 1}` combined with `S = 1 ⟺ no thread is in the critical section` guarantees at most one occupant at a time. 2. Ordering / signaling (rendezvous pattern). Initialize `S = 0`. Thread A performs some action, then calls `signal(S)`. Thread B calls `wait(S)` before performing an action that depends on A's action having completed. Because `S` starts at 0, B's `wait` blocks until A's `signal` has executed — this is the "happens-before" idiom, and critically, `wait` and `signal` are called by different threads. 3. Resource counting (counting semaphore pattern). Initialize `S = N`, where `N` is the number of interchangeable resource units (buffer slots, database connections, printer ports). Threads call `wait(S)` before acquiring a unit and `signal(S)` after releasing it. The invariant `S = N − (units currently in use)` prevents more than `N` simultaneous users, and `wait` blocks threads when the pool is exhausted rather than allowing overcommitment. These three patterns are not mutually exclusive; real systems compose them. A bounded buffer, for instance, uses one mutex for exclusive access to a shared queue and two counting semaphores (`empty`, `full`) to enforce ordering and capacity — foreshadowing The Producer-Consumer Problem. Readers-writers locks combine a mutex protecting a reader count with a second semaphore gating writer access — foreshadowing The Readers-Writers Problem. Mastering the three base patterns here is what makes those composite solutions legible rather than mysterious.
How it works
The mechanism underneath every pattern is identical: `wait` and `signal` are atomic, and threads block inside `wait` rather than busy-waiting (this is what separates a semaphore from a spinlock). The patterns differ only in initial value and call placement. Below is the semaphore's own implementation contract, followed by the three usage templates built on top of it. ``` // The semaphore itself — atomic, provided by the OS/runtime. // Assume it is already correctly implemented (see Semaphores). structure Semaphore: integer value queue waitingThreads wait(S): atomically: S.value := S.value - 1 if S.value < 0: add current thread to S.waitingThreads block current thread // released later by a signal signal(S): atomically: S.value := S.value + 1 if S.value <= 0: remove one thread T from S.waitingThreads wake T ```
Pattern 1 — Mutual exclusion. ``` Semaphore mutex := 1 // Every thread runs this: procedure criticalSectionAccess(): wait(mutex) // --- critical section --- // read/modify/write shared data // ------------------------- signal(mutex) ``` Placement rule: `wait` immediately before the shared-data access, `signal` immediately after, on every code path (including error/exception paths — a common bug source, see pitfalls).
Pattern 2 — Ordering / rendezvous. ``` Semaphore ready := 0 // Thread A (producer of the event): procedure threadA(): statementA1() statementA2() signal(ready) // announce "A has finished A1, A2" // Thread B (consumer of the event): procedure threadB(): wait(ready) // block until A has signaled statementB1() // guaranteed to run after A1, A2 ``` Placement rule: `wait` and `signal` are in different threads, and the semaphore starts at 0 so that B cannot proceed until A explicitly releases it. This generalizes to a full barrier: if `k` threads must all finish phase 1 before any starts phase 2, initialize `barrier := 0` and have each thread `signal` once and then `wait` `k` times (or use a dedicated counting scheme — see the worked example).
Pattern 3 — Resource counting. ``` Semaphore pool := N // N interchangeable units procedure useResource(): wait(pool) // blocks if all N units are taken unit := acquireOneUnit() // use unit releaseOneUnit(unit) signal(pool) ``` Placement rule: identical shape to mutual exclusion, but the initial value is `N` instead of `1`. Setting `N = 1` recovers Pattern 1 exactly — mutual exclusion is the special case of resource counting with a pool of size one. This unifying fact is worth internalizing: all three patterns are really one pattern, parameterized by initial value and by whether `wait`/`signal` are co-located in one thread or split across threads. The following diagram shows the semaphore as a state machine (its integer value transitioning under `wait`/`signal`) simultaneously with the queue of blocked threads it manages — the two views you need to trace any interleaving.
Complexity & correctness
Time complexity. Each `wait` or `signal` call is O(1) amortized in the number of shared-memory operations it performs (an atomic decrement/increment plus a possible queue insert/remove), assuming the underlying blocked-queue is O(1) enqueue/dequeue (e.g., a FIFO linked list). The cost to the calling thread is different: a blocking `wait` costs a context switch out and, later, a context switch back in — this is the entire point of using semaphores instead of spin-waiting, since a blocked thread consumes no CPU cycles while waiting. Under contention, the total time until a thread is unblocked depends on scheduling and on how long other threads hold the resource, which is a scheduling-theoretic question, not a semaphore-internals question. Space complexity per semaphore is O(1) for the counter plus O(k) for the wait queue, where k is the number of threads currently blocked on it — never more than the total thread count.
Correctness for mutual exclusion. Define the invariant ``` I: value(mutex) = 1 - (number of threads currently inside the critical section) ``` Initially `value = 1` and zero threads are inside, so `I` holds. Each `wait` that succeeds (does not block) decrements `value` by 1 exactly as one more thread enters the section, preserving `I`. Each `signal` increments `value` by 1 exactly as one thread leaves, preserving `I`. Since `value ≥ 0` whenever a thread is admitted (a blocking `wait` never lets a thread proceed), `I` forces: ``` number of threads inside ≤ 1 for all time, ``` because `value = 1 - occupancy ≥ 0 ⟹ occupancy ≤ 1`. This is the mutual exclusion property. Progress and bounded waiting additionally require that the semaphore's queue release policy be fair (e.g., FIFO) — if the underlying implementation may starve a waiter indefinitely, mutual exclusion still holds but liveness does not. Most production semaphore implementations offer at least eventual (not necessarily FIFO) fairness; strict bounded waiting requires an explicit ticket/queueing discipline layered on top.
Correctness for ordering. With `ready` initialized to 0, the invariant is ``` I: value(ready) = (number of completed signal(ready) calls) - (number of completed wait(ready) calls) ``` A `wait(ready)` can complete (return) only when its decrement does not take `value` below what would require blocking — concretely, `wait` returns only after some matching `signal` has incremented the counter enough to cover it. Since `value` starts at 0, the very first `wait(ready)` call cannot return until at least one `signal(ready)` has executed. This is exactly "B's `wait` happens after A's `signal`" — the happens-before relation required for correct ordering. No assumption about relative thread speeds is needed: the property holds under any interleaving, which is the entire reason to prefer this pattern over ad hoc flags or sleep-based polling (a flag read without synchronization is a data race and provides no such guarantee).
Correctness for resource counting. Same invariant as mutual exclusion but generalized: ``` I: value(pool) = N - (units currently checked out) ``` `value ≥ 0` is preserved exactly as before, forcing `units checked out ≤ N` at all times — no overcommitment of a bounded resource, and threads that arrive when the pool is full block rather than corrupting resource state.
Tradeoffs. Semaphores are simple and universal, but they carry real costs: (1) they provide no structural enforcement that `wait` and `signal` are correctly paired — a forgotten `signal` on an exception path permanently strands other threads; (2) they encode no information about why a thread is blocked, making debugging deadlocks harder than with higher-level constructs like monitors or condition variables; (3) counting semaphores used for signaling (Pattern 2) do not compose well when multiple distinct conditions must be waited on — this is precisely the motivation for monitors, which layer semaphore-like semantics under structured mutual exclusion, a topic developed further in The Producer-Consumer Problem and The Readers-Writers Problem.
Worked example
Consider a shared bank-account balance, `balance = 100`, accessed by two threads that each perform a deposit-then-withdraw sequence. We compare the unsynchronized interleaving (which corrupts the balance) against the mutex-protected version (Pattern 1), and then use ordering (Pattern 2) so that an audit thread only reads the balance after both transactions commit.
Unsynchronized race, both threads executing `balance := balance + 10` then later `balance := balance - 10` compiled to load/add/store:
| Step | Thread 1 instruction | Thread 2 instruction | Register/mem state |
|---|---|---|---|
| 1 | `r1 := balance` (r1=100) | balance=100 | |
| 2 | `r2 := balance` (r2=100) | balance=100 | |
| 3 | `r1 := r1 + 10` (r1=110) | balance=100 | |
| 4 | `r2 := r2 + 10` (r2=110) | balance=100 | |
| 5 | `balance := r1` | balance=110 | |
| 6 | `balance := r2` | balance=110 (should be 120) |
One deposit is silently lost — the classic lost update. This is exactly the failure mutual exclusion prevents.
With `mutex = 1` guarding the whole read-modify-write:
| Step | Action | mutex value | Effect |
|---|---|---|---|
| 1 | T1 calls `wait(mutex)` | 1 → 0 | T1 proceeds |
| 2 | T2 calls `wait(mutex)` | 0 → -1 | T2 blocks, added to queue |
| 3 | T1: `r1:=balance` (100), `r1+=10` (110), `balance:=r1` | 110 | balance=110 |
| 4 | T1 calls `signal(mutex)` | -1 → 0 | wakes T2 |
| 5 | T2 resumes: `r2:=balance` (110), `r2+=10` (120), `balance:=r2` | balance=120 | |
| 6 | T2 calls `signal(mutex)` | 0 → 1 | mutex free again |
Final balance is 120 — correct — under every interleaving, because mutual exclusion forbids step 3's read from happening between step-3-of-T1's read and write.
Ordering example, an audit thread T3 must read the final balance only after both deposits have committed. Use `Semaphore done := 0`, and after each of T1 and T2 finishes its critical section, they call `signal(done)`; T3 calls `wait(done)` twice before reading: ``` Semaphore mutex := 1 Semaphore done := 0 T1/T2 (each): wait(mutex) balance := balance + 10 signal(mutex) signal(done) // announce completion T3 (auditor): wait(done) // waits for 1st completion wait(done) // waits for 2nd completion print(balance) // guaranteed: both deposits committed ``` Trace: `done` starts at 0. If T3 runs first, its first `wait(done)` decrements to -1 and blocks; T1's `signal(done)` bumps it to 0 and wakes T3's first wait, but T3 immediately issues a second `wait(done)`, decrementing to -1 again and blocking until T2's `signal(done)` arrives. Regardless of the actual thread scheduling order, T3 cannot print until exactly two signals have occurred — the invariant from the Complexity section guarantees this without T3 ever needing to poll or sleep.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Swapped `wait`/`signal` order | Copy-paste error; writing `signal(mutex)` before entering the section | No mutual exclusion at all — the "lock" never actually locks |
| Missing `signal` on an exception/early-return path | Critical section has multiple exit points, only the main path is guarded | Permanent lockout: every future `wait` on that semaphore blocks forever |
| Using the same semaphore for two unrelated purposes | Trying to save a variable; conflating mutex and signaling roles | Deadlock or logically meaningless value transitions |
| Nesting two mutexes in inconsistent order across threads | Thread A does `wait(S1); wait(S2)`, Thread B does `wait(S2); wait(S1)` | Classic deadlock (circular wait) |
| `signal` before `wait` in the ordering pattern, semaphore initialized to 1 instead of 0 | Copying the mutex template without adjusting initial value | Ordering guarantee silently disappears — B may run before A |
| Assuming FIFO wakeup order without checking the implementation | Belief that semaphores are inherently "fair" | Starvation of some thread under sustained contention |
| Calling `wait`/`signal` outside the intended critical boundary (too early/late) | Sloppy placement "close enough" to the shared access | Race window still exists even though a semaphore is "used" |
Pioneers & history
Origins · 1 minEdsger W. Dijkstra and how this was discovered
Dijkstra introduced the semaphore (originally named with the Dutch verbs passeren and vrijgeven, abbreviated P and V) as part of his work on structuring concurrent programs for the THE operating system in the mid-1960s. His broader contribution — insisting that concurrent correctness be provable via invariants rather than argued informally by intuition — set the methodological standard this article follows: every pattern above is justified by an explicit invariant on the semaphore's value, in the Dijkstra tradition.
Where this matters
Every general-purpose operating system kernel uses semaphore-family primitives to protect internal data structures — scheduler run queues, file system inode tables, page frame allocators — from concurrent corruption by multiple CPUs or interrupt handlers. POSIX (`sem_wait`/`sem_post`), Win32 (`WaitForSingleObject` on semaphore objects), and language runtimes (Java's `Semaphore` class, Python's `threading.Semaphore`) all expose this exact triad of patterns directly to application programmers. Database connection pools use the resource-counting pattern to cap concurrent connections to a fixed limit. Thread pools and worker-queue systems use the ordering pattern to implement task-completion barriers. Device drivers use mutual exclusion semaphores to serialize access to hardware registers shared across interrupt contexts and kernel threads. Understanding these three patterns is the direct prerequisite for the two canonical composite problems built from them: The Producer-Consumer Problem, which layers counting semaphores for buffer capacity atop a mutex for safe access, and The Readers-Writers Problem, which layers priority policies atop the same primitives to balance reader throughput against writer fairness.
Ask the tutor: How would you combine a mutex and two counting semaphores to solve the bounded-buffer producer-consumer problem?
Can I use a single semaphore for both mutual exclusion and signaling at the same time?
Technically the counter doesn't distinguish uses, but doing this is a well-known source of bugs. A semaphore dedicated to mutual exclusion has an invariant tied to "is anyone in the critical section," while a signaling semaphore has an invariant tied to "how many completion events have occurred." Mixing the two conflates these invariants: an increment meant as "resource freed" can be misread as "event occurred," and vice versa. The disciplined approach used throughout real systems (and in the composite problems that follow this one) is to declare a separate semaphore per role — one mutex, one or more signaling/counting semaphores — even though it costs a little extra memory.
Why not just use a busy-wait loop (spinning on a shared flag) instead of a semaphore?
A busy-wait loop consumes CPU cycles the entire time a thread is "waiting," starving other runnable threads (including, potentially, the thread it's waiting for, on a single-core system) and wasting energy. A semaphore's `wait` instead blocks the thread — removing it from the scheduler's runnable set — so the CPU can do useful work for other threads while this one waits. Spinning is only justified when the expected wait time is shorter than the cost of two context switches, which is why some real kernels use a hybrid: spin briefly, then block if the lock isn't released quickly (adaptive mutexes).
What happens if two threads call wait() on the same semaphore at exactly the same instant?
This cannot actually happen, by construction: `wait` is required to be atomic, meaning the semaphore's underlying implementation (often built on a hardware atomic instruction like compare-and-swap, or a short critical section disabling interrupts) serializes concurrent calls so that each one's decrement-and-check happens indivisibly. From the outside, it looks as if the two `wait` calls occurred in some sequential order, even if they were issued at the same wall-clock instant. This atomicity guarantee is exactly what the correctness proofs in this article rely on — without it, the invariant `value = 1 − occupancy` could be violated by two threads decrementing "simultaneously."
Does the order in which blocked threads are woken matter for correctness?
It matters for fairness (freedom from starvation) but not for the basic safety properties proven above. Mutual exclusion and resource-count bounds hold regardless of which blocked thread a `signal` wakes, because the invariant argument only depends on the count of successful waits versus signals, not on which thread benefits. However, if the wake policy is not FIFO (or at least not eventually fair), a specific thread could in principle be perpetually passed over while others repeatedly cut in line — this is starvation, a liveness bug rather than a safety bug, and it becomes a central concern in The Readers-Writers Problem.
How is a semaphore different from a mutex/lock as a language-level construct?
A binary semaphore used in Pattern 1 behaves like a mutex, but true mutex implementations often add ownership semantics: only the thread that acquired the lock may release it, and some implementations detect or forbid a different thread calling `unlock`. A general semaphore has no notion of ownership — any thread can call `signal` on a semaphore even if it never called the matching `wait`, which is a feature (it enables the ordering pattern, where wait and signal are in different threads) and simultaneously a hazard (a bug can call `signal` an extra time, corrupting the invariant). Choose a strict mutex when you want ownership enforcement; choose a semaphore when you need the extra flexibility of splitting wait/signal across threads.
Why does the resource-counting pattern still need a separate mutex if I'm just protecting a counter?
If the "resource units" involve more state than the count alone — say, a pool of actual buffer objects, database handles, or worker threads that must be selected from a list — then acquiring a slot (decrementing the counting semaphore) and actually removing/inserting an object from the underlying list are two separate operations on shared data. The counting semaphore alone guarantees no more than N units are checked out; it does not, by itself, guarantee the list of available units is manipulated safely if multiple threads try to pop from it concurrently. In that case you need both: the counting semaphore for the capacity invariant, and a mutex (or equivalent) protecting the list's internal structure — exactly the combination used in the bounded-buffer solution to The Producer-Consumer Problem.
Is it possible to build ordering constraints without semaphores, e.g., with a shared boolean flag?
Not safely, in general. A plain shared boolean read and written without synchronization is a data race under most memory models: the reading thread has no guarantee it will observe the writer's update in a timely or ordered fashion, and compilers/CPUs are free to reorder or cache the access. A semaphore's `wait`/`signal` pair carries the memory-ordering guarantees (acquire/release semantics) needed to make the "B happens after A" property actually hold in the presence of compiler optimizations and multicore memory hierarchies, not just in a naive single-threaded mental model. This is a key reason semaphores (and their cousins, mutexes and condition variables) remain necessary even when the "data" being coordinated is as simple as a single flag.