What is a semaphore in concurrent programming, and what is the difference between a counting semaphore and a binary semaphore?
answer
- permits counter + waiter queue
- P/V = acquire/release = down/up
- init N = N units, init 1 = mutex-ish, init 0 = signal
- binary caps at 1 permit
- no owner: any thread may release
basics
~20 sA semaphore is a counter of permits with two atomic operations: acquire, which takes a permit and blocks while none are free, and release, which returns one. A counting semaphore starts with N permits; a binary semaphore holds at most one.
solid answer
~50 sA semaphore is a synchronization primitive that is essentially an atomic non-negative counter of **permits** plus a queue of waiters. `acquire` (Dijkstra's P) takes one permit, blocking if the count is zero; `release` (V) gives one back and wakes a waiter. Both operations are atomic with respect to each other. A **counting semaphore** is initialised to N and models N interchangeable units of some resource — pool slots, buffer entries, licences, in-flight request budget. A **binary semaphore** is capped at one permit and models a single resource or an on/off condition. The initial value tells you what you are modelling: start at N for "N units available"; start at 1 for mutual exclusion; start at 0 for signalling, where the waiter blocks until another thread signals. Crucially a semaphore has **no owner** — the thread that releases need not be the one that acquired — which is what makes it usable as a cross-thread signal, not just as a lock.
code
text · 13 linessem = Semaphore(permits = 3)
# limiting: at most 3 threads inside
sem.acquire() # blocks while permits == 0
try:
use_resource()
finally:
sem.release() # always give the permit back
# signalling: init 0, waiter blocks until someone signals
done = Semaphore(permits = 0)
# thread A: done.acquire() -> blocks
# thread B: done.release() -> unblocks Ago deeper
Be able to state the counter-plus-two-atomic-operations definition, what the initial value means, and that counting holds N permits while binary holds at most one.
Add the invariant (in-flight holders ≤ initial permits), the three canonical initial values (N / 1 / 0), and the fact that there is no owner so release can come from another thread.
Discuss fairness versus barging, what happens on unbalanced release, and where a semaphore stops being enough (arbitrary predicates need condition variables).
Frame the semaphore as the minimal primitive that expresses a concurrency bound, and be explicit about what it deliberately does not encode — ownership, priority, queue length, or timeouts — so the surrounding design has to supply those.
## The primitive A semaphore, introduced by Edsger Dijkstra, is one of the oldest synchronization primitives. Conceptually it is an integer counter of **permits** together with a queue of blocked threads, manipulated only through two operations that are atomic with respect to each other: - **acquire** (historically `P`, from Dutch *proberen*; also called *wait* or *down*): if the count is greater than zero, decrement it and return; otherwise block the calling thread until a permit becomes available. - **release** (historically `V`, *verhogen*; also *signal* or *up*): increment the count and, if any thread is blocked, wake one of them so it can consume the permit. Atomicity matters: two threads acquiring simultaneously when one permit remains must not both succeed. Implementations achieve this with an atomic compare-and-swap on the counter and a kernel or runtime wait queue for the blocked threads. ## The invariant The useful property is a counting invariant: at any moment, `permits_now = initial_permits + total_releases - successful_acquires` and `permits_now >= 0`. Therefore the number of threads that have acquired but not yet released can never exceed `initial_permits` (assuming nobody releases without acquiring). That single inequality is the entire safety guarantee a semaphore gives you — it bounds concurrency, nothing more. ## Counting versus binary A **counting semaphore** is initialised to some N ≥ 0 and represents N interchangeable units: slots in a bounded buffer, connections in a pool, concurrent calls allowed to a dependency, seats in a room. Threads acquire when they take a unit and release when they give it back. A **binary semaphore** saturates at one permit. It represents either a single indivisible resource or a boolean condition ("the event has happened"). In most classic formulations releasing an already-full binary semaphore is a no-op or an error rather than pushing the count to two, which is a real behavioural difference from a counting semaphore initialised to one, where a stray double release silently raises the limit to two. ## The initial value is the design The initial permit count encodes the intent: - **init = N** — resource limiting / throttling. At most N threads inside the guarded region. - **init = 1** — mutual exclusion (a lock-like use, though not a mutex; see the ownership section). - **init = 0** — signalling or rendezvous. The waiter calls acquire and blocks immediately; another thread calls release when the awaited event occurs. This is how you build "wait until the worker has finished" without shared condition predicates. ## No ownership Unlike a mutex, a semaphore has no notion of an owning thread. Thread A may acquire and thread B may release. This is a deliberate feature: it is what allows a semaphore to be used as a directed signal between threads, and it is what allows a producer to hand a consumer a permit for the item it just enqueued. It also means the runtime cannot detect "released without acquiring", cannot support recursive acquisition, and cannot implement priority inheritance. ## Negative counts Some textbooks define the counter so it may go negative, where a value of −k means k threads are waiting. Practical implementations keep the count at zero or above and maintain a separate waiter queue. The two formulations are behaviourally equivalent; do not be thrown if an interviewer uses the negative-count model. ## Fairness Nothing in the definition says which blocked thread gets the permit. Unfair (barging) semaphores let a thread that calls acquire at just the right moment take a permit ahead of threads already queued — this is faster under contention but can starve a waiter indefinitely. Fair semaphores hand permits out in FIFO order at the cost of extra hand-off latency. If you need a bound on waiting time you must ask for fairness explicitly; the primitive does not promise it. ## What a semaphore does not do It does not protect data. It bounds how many threads are in a region; the data inside still needs its own mutual exclusion if more than one permit exists. It does not let you wait on an arbitrary predicate ("wait until the queue is non-empty *and* the connection is open") — that is what monitors with condition variables are for. It has no reentrancy and no owner-based error checking. ## Pseudocode ``` acquire(): atomically: while count == 0: block on queue count = count - 1 release(): atomically: count = count + 1 if queue non-empty: wake one waiter ```
- Can the permit count go negative, and what would a negative value mean?In the classic textbook formulation the counter is allowed to go negative, and a value of −k means k threads are currently blocked waiting. Practical implementations instead clamp the count at zero and keep an explicit wait queue, which is behaviourally equivalent. Either way, the externally visible rule is the same: acquire blocks whenever no permit is available.
- What happens if a thread calls release without ever having acquired?Nothing stops it — a semaphore has no owner, so the release simply adds a permit. On a counting semaphore that permanently raises the effective concurrency limit above what you configured, which is a silent correctness bug: your limiter of 10 quietly becomes a limiter of 11. Classic binary semaphores saturate at one permit, so the same mistake is absorbed there, which is one practical argument for using the binary form when you only ever want one holder.
- Does a semaphore guarantee that waiting threads are served in order?No. The base definition says nothing about which blocked thread receives a released permit. Unfair implementations let a newly arriving thread barge ahead of queued waiters, which improves throughput but permits indefinite starvation. If bounded waiting matters, you must select a fair (FIFO) semaphore and accept the extra hand-off cost.
A bowl of N identical cloakroom tokens. You take a token to enter, drop it back when you leave, and wait by the door when the bowl is empty. Nobody records which token was yours — any returned token unblocks the next person.
saying these in an interview costs you the question
- Saying a semaphore "is just a lock" and ignoring that it has no owning thread
- Believing acquire always blocks — it returns immediately whenever a permit is free
- Assuming the count cannot exceed its initial value; extra releases inflate a counting semaphore's limit
- Claiming semaphores serve waiters in FIFO order by default
- Thinking a semaphore protects the data inside the guarded region when N > 1