Free lesson · Concurrency Interview Mastery
Semaphores
The mutex lesson ended with a teaser: a semaphore is, loosely, a mutex that lets N threads through instead of one. That's a useful first intuition, but a semaphore is both more general and more interesting than that. It's one of the oldest synchronization primitives - Edsger Dijkstra invented it in the 1960s - and it does two genuinely different jobs depending on how you use it: limiting concurrency to a fixed number of threads, and signaling between threads. Understanding both uses, and the one property that separates a semaphore from a mutex, is what this lesson is about. It's a favorite interview topic precisely because the "semaphore vs mutex" distinction trips up people who've only ever used locks.
What a semaphore is
A semaphore is, at its core, a counter with two atomic operations. Dijkstra named them P and V (from Dutch); modern APIs call them wait/acquire and signal/release:
- wait / acquire / P - decrement the counter. If the counter is now negative (would go below zero), block until it can decrement without going negative.
- signal / release / V - increment the counter. If any threads are blocked waiting, wake one so it can complete its decrement.
The counter represents the number of available "permits." A thread must acquire a permit to proceed (decrementing the count); it releases the permit when done (incrementing it). When permits run out, acquirers block until someone releases one.
semaphore = new Semaphore(3) // 3 permits available
semaphore.acquire() // count 3 -> 2, proceed
semaphore.acquire() // count 2 -> 1, proceed
semaphore.acquire() // count 1 -> 0, proceed
semaphore.acquire() // count 0 -> would be negative: BLOCK until a release
// ... another thread calls release() -> count back to >0, a blocked thread wakes
This single mechanism - a blocking counter - is remarkably flexible, and the two main uses fall directly out of what you initialize the count to and which threads acquire versus release.
Use 1: Limiting concurrency
The most common use is capping how many threads may do something at once. You initialize the semaphore to N (the number of permits), and each thread acquires before the limited operation and releases after. At most N threads hold permits simultaneously, so at most N run the operation concurrently; the rest block until a permit frees.
// Allow at most 5 concurrent downloads
limiter = new Semaphore(5)
function download(url):
limiter.acquire() // wait for a permit (at most 5 proceed)
try:
fetch(url) // the rate-limited work
finally:
limiter.release() // return the permit
This is the counting semaphore as a resource pool. The permits model a finite resource - database connections, concurrent network calls, slots in a fixed-size pool - and the semaphore enforces that no more than the available count are used at once. A thread that needs a connection acquires a permit (waiting if all connections are checked out), uses a connection, and releases the permit when done. This is exactly how a bounded connection pool or a concurrency limiter is built.
flowchart TD
subgraph S["Semaphore (N=3 permits)"]
P["permits: 3 available"]
end
T1[Thread 1] -->|acquire| P
T2[Thread 2] -->|acquire| P
T3[Thread 3] -->|acquire| P
T4[Thread 4] -.acquire: permits=0, BLOCKS.-> P
T1 -->|release when done| P
T4 -.unblocks when a permit frees.-> RUN[Thread 4 proceeds]
This diagram shows a counting semaphore with three permits used to limit concurrency. Three threads each acquire a permit and proceed, bringing the available permits to zero. A fourth thread tries to acquire but, with no permits available, it blocks. When one of the first three threads finishes and releases its permit, the count goes back above zero, and the blocked fourth thread unblocks and proceeds. So the semaphore enforces that at most three threads run the limited operation at once, with the rest waiting their turn.
Use 2: Signaling between threads
The second, quite different use is coordination - having one thread signal another that something has happened. Here you typically start the semaphore at 0 (no permits): the waiting thread acquires (blocking immediately, since the count is 0), and a different thread releases when the awaited event occurs, unblocking the waiter.
ready = new Semaphore(0) // start empty
// Thread B (waiter):
ready.acquire() // blocks until A signals (count is 0)
useResult()
// Thread A (signaler):
prepareResult()
ready.release() // signals B: count 0 -> 1, B's acquire completes
This is signaling, not mutual exclusion. Thread B waits for an event; Thread A causes it. Crucially, the thread that releases is different from the thread that acquires - and that's the property that distinguishes a semaphore from a mutex.
The defining difference: semaphores have no owner
Here's the heart of "semaphore vs mutex," and the most important thing in this lesson. A mutex is owned - only the thread that locked it may unlock it. A semaphore is not owned - any thread can release a permit, including one that never acquired one, and the thread that releases need not be the one that acquired.
This ownership difference dictates which primitive fits which job:
- For mutual exclusion - protecting a critical section where the same thread enters and leaves - you want a mutex. Its ownership lets the runtime detect misuse (unlocking a lock you don't hold) and supports reentrancy. A binary semaphore can enforce mutual exclusion, but it's the wrong tool: it lacks ownership, so it can't catch the "released by the wrong thread" bug and offers no reentrancy.
- For signaling between threads - one thread waits, a different thread signals - you want a semaphore, precisely because it has no owner. A mutex can't do this: you can't have thread B "lock" and thread A "unlock," because that violates ownership. The unowned nature of the semaphore is exactly what makes cross-thread signaling possible.
Important: The rule to carry: mutex for mutual exclusion (owned), semaphore for signaling or limiting concurrency (unowned). A binary semaphore (count 0/1) and a mutex look identical - two states, two operations - but the mutex is owned and the binary semaphore is not, and that single difference determines their proper jobs. When an interviewer asks "what's the difference between a mutex and a semaphore," the answer they're listening for is ownership, and the corollary that it makes the mutex right for critical sections and the semaphore right for signaling and counting. Reciting "a mutex allows one, a semaphore allows N" is the shallow answer; ownership is the deep one.
Counting vs binary semaphores
A counting semaphore has a count that can be any non-negative number - used for the "N permits" concurrency-limiting case. A binary semaphore has a count of just 0 or 1 - effectively a single permit, used for signaling (and, less ideally, as a lock). They're the same primitive with different initial counts and ranges; the binary case is just the counting case capped at one. The interesting binary use is signaling, where the unowned property matters; the interesting counting use is resource pooling.
The classic: bounded-buffer producer-consumer
Semaphores shine in the bounded-buffer producer-consumer problem, the canonical use that combines both roles. A fixed-size buffer sits between producers (which add items) and consumers (which remove them). Producers must wait when the buffer is full; consumers must wait when it's empty. The elegant solution uses two counting semaphores plus a mutex:
emptySlots = new Semaphore(N) // counts empty slots; starts at buffer capacity
fullSlots = new Semaphore(0) // counts filled slots; starts empty
mutex = new Mutex() // protects the buffer structure itself
function produce(item):
emptySlots.acquire() // wait for an empty slot (blocks if full)
mutex.lock()
buffer.add(item) // critical section: modify the buffer
mutex.unlock()
fullSlots.release() // signal: one more item available
function consume():
fullSlots.acquire() // wait for an item (blocks if empty)
mutex.lock()
item = buffer.remove() // critical section
mutex.unlock()
emptySlots.release() // signal: one more empty slot
Study how the two semaphores work as counters of resources: emptySlots tracks how many empty slots remain (a producer consumes one to add an item), and fullSlots tracks how many items are available (a consumer consumes one to remove an item). When the buffer is full, emptySlots is 0 and producers block on emptySlots.acquire(); when empty, fullSlots is 0 and consumers block on fullSlots.acquire(). The mutex separately protects the buffer data structure from concurrent modification - the semaphores handle counting and blocking, the mutex handles mutual exclusion on the shared structure. This division of labor is the classic, and being able to explain why you need all three (two semaphores and a mutex) is a strong interview signal.
Warning: A subtle and important rule in that solution: acquire the semaphore before the mutex, never the reverse. If a producer locked the mutex first and then blocked on a full
emptySlots, it would hold the mutex while waiting - and a consumer needing the mutex to remove an item (which would free a slot) could never get it. Deadlock. Acquiring the counting semaphore first means a blocked producer holds no lock while waiting, so consumers can still make progress and eventually release a slot. Lock-ordering matters even across primitive types, and this producer-consumer ordering is a classic place it bites.
Gotchas
Two failure modes to know. A permit leak: if a thread acquires but fails to release (an exception skips the release), the permit is gone forever, and eventually all permits leak and every acquirer blocks permanently - which is why release belongs in a finally or scope-bound guard, exactly like mutex unlock. And signal/wait imbalance: because a semaphore is just a counter, releasing more than you acquire silently inflates the permit count (letting too many threads through later), and acquiring more than you release blocks threads forever. The counter has no built-in notion of "correct" balance - that discipline is on you, which is part of why semaphores, while powerful, are considered lower-level and more error-prone than higher-level constructs like monitors (covered later in this module).
How a semaphore is implemented, and where it sits
Understanding what's inside a semaphore both demystifies it and clarifies why it behaves as it does. Internally, a semaphore is a counter plus a queue of waiting threads, with all access to both protected atomically. acquire atomically checks the counter: if it's positive, decrement and proceed; if it's zero, add the calling thread to the wait queue and block it. release atomically increments the counter and, if the wait queue is non-empty, removes a waiter and wakes it. The atomicity of these check-and-modify steps is essential - it's what the mutex provided for ordinary critical sections, applied here to the semaphore's own internal state - and on real systems it's built on the same atomic instructions and futex-style blocking that mutexes use. So a semaphore isn't magic; it's a small, carefully-synchronized data structure (a count and a waiter queue) exposing two atomic operations.
This internal view also explains the relationship between semaphores and the other primitives. A mutex can be seen as a binary semaphore with ownership added - the same blocking-counter idea, capped at one permit, plus the rule that only the acquirer may release. Going the other direction, a counting semaphore can be built from a mutex and a condition variable: the mutex protects an integer count, threads wait on a condition variable while the count is zero, and release increments the count and signals. In fact, all of these primitives are inter-constructible - you can build any of them from the others - which is a favorite interview follow-up ("implement a semaphore using a mutex and condition variable"). The reason multiple primitives exist despite this inter-constructibility is ergonomics and performance: each one expresses a particular coordination pattern most directly, and the right primitive makes correct code easy to write while the wrong one makes it awkward.
Where does the semaphore sit in the hierarchy? It's a low-level primitive - powerful and general, but unforgiving. The counter has no notion of correct balance, no ownership to catch misuse, and no structure to prevent signal/wait imbalance, so semaphore-based code is easy to get subtly wrong. This is exactly why higher-level constructs exist on top of it. The monitor (covered later in this module) packages a mutex and condition variables into a single safer abstraction precisely because raw semaphores, while they can express anything, demand discipline that's easy to slip on. The practical guidance: reach for a semaphore when you specifically need its counting or unowned-signaling nature - a concurrency limiter, a resource pool, cross-thread signaling - and prefer higher-level constructs for ordinary mutual exclusion and condition-waiting, where they're safer. Knowing a semaphore is a low-level, general-but-error-prone primitive, and when its specific capabilities justify reaching for it, is the mature framing.
Note: A quick way to keep the two roles straight: ask who acquires and who releases. If the same thread does both (acquire before the work, release after), it's the limiting-concurrency role - you're holding a permit for the duration of some bounded operation. If different threads do them (one waits/acquires, another signals/releases), it's the signaling role - and that asymmetry is only possible because the semaphore is unowned. The acquire/release symmetry tells you which job you're doing, and therefore how to initialize the count.
The interview angle
Interview: Core questions: (1) "Semaphore vs mutex?" - The key difference is ownership: a mutex is owned (only the locker unlocks), suited to mutual exclusion; a semaphore is unowned (any thread can release), suited to signaling between threads and limiting concurrency. "Mutex allows 1, semaphore allows N" is the shallow answer; ownership is the real one. (2) "Counting vs binary semaphore?" - Counting has N permits (resource pools, concurrency limits); binary has 0/1 (signaling). (3) "What are the two main uses of a semaphore?" - Limiting concurrency to N (permits for a finite resource) and signaling/coordination between threads (wait for an event a different thread causes). (4) "Solve bounded-buffer producer-consumer with semaphores." - Two counting semaphores (empty slots, full slots) plus a mutex for the buffer; acquire the semaphore before the mutex to avoid holding the lock while blocked. (5) "Why is a semaphore riskier than a mutex for mutual exclusion?" - No ownership, so it can't catch wrong-thread release, no reentrancy, and signal/wait imbalance silently corrupts the count. Leading with ownership is what marks real understanding.
Quick reference
SEMAPHORE = a blocking counter of PERMITS.
acquire/wait/P -> decrement; BLOCK if it would go below 0
release/signal/V -> increment; wake a blocked waiter
NOT OWNED: any thread can release (vs mutex, which only the locker can unlock)
-> mutex = mutual exclusion (owned)
-> semaphore = signaling between threads + limiting concurrency (unowned)
TWO USES:
limit concurrency -> init to N permits; acquire before / release after the limited op
signal an event -> init to 0; waiter acquires (blocks), other thread releases
COUNTING (N permits: resource pools/limits) vs BINARY (0/1: signaling)
BOUNDED BUFFER: emptySlots(N) + fullSlots(0) + mutex(buffer)
produce: emptySlots.acquire; lock; add; unlock; fullSlots.release
consume: fullSlots.acquire; lock; remove; unlock; emptySlots.release
RULE: acquire the semaphore BEFORE the mutex (never block while holding the lock)
GOTCHAS: release in finally (permit leak) | signal/wait imbalance corrupts the count
The semaphore handles "how many" and "has it happened yet." The next primitive handles a richer question: "wait until this arbitrary condition is true." Condition variables let a thread sleep until any predicate it cares about becomes true - and they pair with a mutex to do it safely, introducing the most subtle and most interview-tested mechanics in this whole module.