What a semaphore actually is
A semaphore is two things bolted together: a non-negative integer counter, and a queue of threads blocked waiting on that counter. It exposes exactly two operations, traditionally called wait/acquire/P and signal/release/V (the P/V naming comes from Dijkstra's original Dutch — proberen "to test" and verhogen "to increase"):
wait(s): signal(s):
atomically: atomically:
while s.value == 0: s.value += 1
block until signaled if any thread blocked on s:
s.value -= 1 wake exactly one of them
The critical word is atomically. The check-and-decrement in wait and the increment-and-possibly-wake in signal must each happen as a single indivisible step — if two threads could both observe s.value == 1, both decrement, and both proceed, the semaphore's entire counting guarantee collapses back into the same race condition it exists to prevent. Every real semaphore implementation (java.util.concurrent.Semaphore, POSIX sem_t, Python's threading.Semaphore) guarantees this atomicity internally, usually by layering the semaphore on top of a lower-level mutex + condition variable (or a futex on Linux) — which is itself a fact worth knowing: semaphores and {mutex + condition variable} are equally expressive; you can build either one out of the other. See the reference implementations for a from-scratch semaphore built on a mutex and a condition variable.
A semaphore initialized with value n allows up to n concurrent wait()-holders before the n+1th blocks — this is a counting semaphore. When n = 1, it's called a binary semaphore, and at first glance that looks just like a mutex. It is not.
Binary semaphore vs. mutex: the ownership distinction
This is the single fact interviewers most want to hear you say precisely, because it's the fact that explains why semaphores exist at all if mutexes already solve mutual exclusion:
| Mutex | Binary semaphore |
|---|
| Ownership | Yes — in virtually every real implementation, only the thread that acquired the mutex may release it. Some runtimes (e.g. pthread's PTHREAD_MUTEX_ERRORCHECK) will error or deadlock if a different thread tries to unlock it. | None. Any thread can call signal(), whether or not it ever called wait(). |
| Purpose | Protect a critical section — enforce that only the section's current holder can let go of it. | General-purpose signaling and resource counting between threads, which may or may not be the same thread that last touched the semaphore. |
| Recursion | Reentrant variants exist (a thread can re-acquire a lock it already holds); see the Locks & Mutual Exclusion topic. | Not meaningful — there's no "owner" to compare against. |
| Typical use | "Only one thread may run this code at a time." | "Signal thread B that thread A finished something," or "allow up to N threads to hold this resource." |
This is exactly why a semaphore can do something a mutex structurally cannot: have one thread wait() and a different thread signal(). That's not a misuse of a semaphore — it's the pattern semaphores are for. A generalized thread.join(), a barrier, a bounded producer-consumer buffer, and a "wake me up when the download finishes" callback are all instances of exactly this: thread A blocks on wait(), thread B — which did completely different work — calls signal() when it's done. Try to express that with a mutex and you'll find yourself building a semaphore out of one anyway (a flag + condition variable), which is the point: mutexes alone can't model "signal an event to someone else," only "protect a section I'm currently in."
Common interview trap: if you're asked to implement a mutex using a semaphore, the answer is trivial — Semaphore(1), wait() to lock, signal() to unlock. If you're asked the reverse — implement a semaphore using only a mutex — you need a condition variable too (a bare mutex alone cannot make a thread sleep and be woken by another thread); see the cx-sema-counting-semaphores-vs-mutexes-scratch reference implementation.
Counting semaphores as a resource pool
Where a binary semaphore/mutex encodes "0 or 1 threads allowed in," a counting semaphore initialized to n encodes "up to n threads allowed in" — a direct model for a fixed-size resource pool: database connections, worker slots, rate-limit permits, seats in a waiting room. The pattern is always the same shape:
pool = Semaphore(n)
acquire_resource():
pool.wait()
# one of the n resource slots is now "checked out" to this thread
use_resource()
pool.signal()
Because there's no ownership, this composes cleanly even when the thread that eventually releases a permit is a pooled worker rather than the original caller — e.g. a thread pool where a dispatcher acquires a permit before submitting work, and the worker thread (not the dispatcher) releases it when the job completes. A mutex can't do this without extra bookkeeping, because the runtime itself will reject or misbehave on a cross-thread unlock.
Fairness and starvation
Neither mutexes nor semaphores are fair by default in most implementations. java.util.concurrent.Semaphore explicitly documents this: with the default (non-fair) constructor, a newly arriving thread can "barge" ahead of threads that have been waiting longer, which improves throughput but permits starvation of long-waiters under sustained contention. Passing fair = true switches to strict FIFO servicing of the wait queue, at a real throughput cost (no barging means every handoff pays a full context-switch, even when the resource is momentarily free). This is the same throughput/fairness trade-off you'll see recur, more sharply, in the Readers-Writers Problem later in this topic — semaphores don't remove that trade-off, they just make it an explicit constructor parameter instead of an accident of scheduling.
Building block for everything else in this topic
Every problem that follows — bounded-buffer producer-consumer, dining philosophers, readers-writers — is, underneath, an exercise in composing counting semaphores (for resource counts) with binary semaphores/mutexes (for protecting shared state), and reasoning carefully about the order in which you acquire multiple of them. Get the semaphore-vs-mutex distinction solid here, because every subsequent subtopic assumes it.
Pitfalls and interview gotchas
- Treating a semaphore's value as safely inspectable. There is no atomic "peek" operation on a standard semaphore — you cannot correctly branch on "is the count currently 0?" and then act, because another thread can change the value between your check and your action. (Java's
availablePermits() exists but is explicitly documented as being for debugging/monitoring, not for making synchronization decisions.)
- Assuming a released permit goes to the "right" thread. Signal wakes some blocked waiter, not necessarily in arrival order (unless the semaphore is explicitly fair) — don't design a correctness argument around FIFO delivery unless you've actually requested a fair semaphore.
- Using a semaphore for mutual exclusion but forgetting it has no owner. If your mutual-exclusion code accidentally calls
signal() twice (a double-release bug), a binary semaphore's value goes to 2 and you've silently broken your own exclusion guarantee — with a real mutex, most implementations would instead throw on an unbalanced unlock. This is a genuine reliability trade-off, not just a style choice.
- Deadlocking on ordering when you must hold two semaphores at once. Anticipates the Dining Philosophers problem directly: if two threads acquire semaphores A and B in opposite order, you have a lock-ordering deadlock regardless of whether the primitive is called "mutex" or "semaphore" — the fix (consistent global ordering) is identical either way.
- Conflating "binary semaphore" with "mutex" in an interview answer. They frequently behave the same in the happy path, so it's an easy shortcut to take — but stating the ownership difference unprompted is one of the clearest signals of seniority you can give here.