Prompt and context
Implement an asynchronous semaphore for a connection pool or task executor. It starts with capacity N; acquire() queues when no permit is available, and release() returns one. A waiter may time out or be cancelled. Cancellation must not leave a ghost queue entry or prevent another waiter from progressing. Define duplicate releases, close behavior, and fairness.
This fits concurrency, runtime, and backend-infrastructure interviews. Oracle’s Semaphore API defines permits, optional fair FIFO selection, and interruptible acquisition. Python’s asyncio documentation describes a counter that decreases on acquire and increases on release, and distinguishes ordinary from bounded semaphores. Public interview discussions list counting semaphores and concurrency limits as operating-system interview topics. These sources support representativeness, but do not establish a fixed company prompt or frequency. The category is coding because the core skills are state invariants, queue cleanup, cancellation races, and verifiable concurrent implementation.
What interviewers evaluate
First, does the candidate define permit ownership? A successful acquire must create a token that can be returned exactly once. A cancelled or timed-out request has no token and must not call release.
Second, is fairness real? Once the queue is non-empty, a new release must not let a later fast path bypass the head; otherwise high load can starve an old waiter. FIFO fairness requires checking the queue, assigning a permit, and waking a waiter within one synchronization boundary.
Third, can they handle cancellation racing with wakeup? A waiter may already be selected by release and then time out, or it may time out before release removes it. Both paths must compete on one state transition and complete a waiter at most once.
Finally, do tests check the concurrency limit, FIFO order, timeout cleanup, progress after cancellation, duplicate release, close, and task failure rather than only sequential acquire/release?
Clarifying questions to ask first
- Is fairness strict FIFO or best effort? Strict FIFO avoids starvation but can sacrifice throughput.
- What does acquire return? A release token or lease binds ownership to one successful acquisition and reduces accidental release.
- What if cancellation happens after a permit is assigned? Define completion precedence; once the promise resolves, the caller owns the lease and cancellation only affects later work.
- Is release more times than acquire an error? A bounded semaphore should reject or report it; silently increasing the count violates capacity.
- How does close finish waiters? Close rejects new requests and ends queued waiters with a clear Closed error; held leases can still release safely.
30-second answer framework
“I maintain available, a FIFO waiter queue, and a closed state, with every mutation in one critical section. Acquire can take the fast path only when the queue is empty; once waiters exist, later callers queue. Release finds the first live waiter, transfers one permit, and completes it once; only when no live waiter exists does it increment available. Each waiter has cancellation state and a one-shot completion. Timeout and release race on that same state. Successful acquire returns a lease that can release once. Tests force FIFO, cancellation and release at the same boundary, permit recovery after timeout, duplicate release, close, and the concurrency cap.”
Deep-dive answer
1. State the core invariant
For capacity N, maintain available + held + reserved = N. available can be assigned immediately, held belongs to callers through leases, and reserved has moved from available to a selected waiter whose callback has not completed yet.
Each waiter has exactly one terminal state: pending, fulfilled, or cancelled. A cancelled waiter owns no permit; a fulfilled waiter must produce a lease. Closing does not reclaim held leases, but it prevents new acquisitions.
2. Fair fast path and queue
When waiters is empty and the semaphore is open, acquire may consume available directly. When the queue is non-empty, even if available > 0, a new caller queues; otherwise it bypasses an older caller. Acquire and release must check the queue under the same synchronization boundary.
A queue node stores the waiter promise, cancellation state, timer handle, and one-shot completion function. Remove completed or cancelled nodes, or retain tombstones that release skips lazily at the head. Either strategy needs a proof that a live waiter cannot remain permanently behind invalid nodes.
3. Transfer permits in release
Release first verifies that the lease has not already been released, then gives the permit to the first live waiter. The permit changes from held to reserved and the waiter completion is invoked; do not increment available and search asynchronously, because a new acquire could cut in line.
If the head is cancelled, skip and clean it, continuing to the next waiter. Only if no live waiter exists should available += 1. A bounded semaphore rejects releases beyond N so a caller bug cannot hide a leak or double return.
4. Cancellation and timeout races
Cancellation and release can both try to finish the same waiter. Use a one-shot CAS, an in-lock state check, or an equivalent mechanism so only one wins. If cancellation wins, remove the waiter without changing available because it never owned a permit. If release has already reserved a permit, cancellation cannot both return it and let release complete the same waiter.
A simple rule is for release to mark the waiter fulfilled inside the critical section before resolving it. Once fulfilled, a timeout can only record that the caller abandoned later work; the caller still releases the lease it receives. A more elaborate design may reclaim an undelivered reservation, but that reclaim belongs in the same state machine rather than being inferred from a rejected promise.
5. Lease and duplicate release
Return a lease with a released flag. lease.release() may transition false to true once. A duplicate call returns an idempotent result or a clear error; it cannot add two permits. Exposing a bare release method to arbitrary callers loses ownership association unless the API explicitly uses a caller-owned counting model.
6. Close, failure, and backpressure
After close, reject new acquires and finish queued waiters with Closed. Tasks holding leases may finish and release; release must not discard permits merely because the semaphore is closed, or the held count becomes unexplained. Task failures still release in finally.
A semaphore limits concurrency, not queue length. An unbounded waiter queue turns backpressure into memory growth. Production code should set a maximum wait count, timeout, or rejection policy, and record wait duration, cancellation rate, and queue depth.
7. Control races with a scheduler
Do not prove races with real sleeps. Use a manual clock and controllable scheduler to pause at queueing, release selecting a waiter, and a timeout callback being queued but not yet executed. At each step assert available, held, live waiter count, and lease ownership.
Cover invalid N=0 initialization, strict FIFO with N=1, multiple permits, cancellation of the head and a middle waiter, timeout and release at the same boundary, duplicate release, acquire before and after close, task failure, and the absence of starvation for a long-waiting caller.
High-quality sample answer
“I encapsulate permit ownership in a lease. The semaphore stores available, FIFO waiters, and closed state, and all transitions share one synchronization boundary. Acquire takes the fast path only when the queue is empty; once a waiter exists, later calls queue.
Release verifies the lease is released once, finds the first live waiter, transfers held to that waiter’s reservation, and completes it once. It skips and cleans cancelled heads; only with no live waiter does it increase available. Cancellation and timeout race with release on the same waiter state, and a one-shot transition chooses the winner. A cancellation before acquire owns no permit, while a completed acquire gives the caller a lease that cancellation cannot replace.
Close rejects new requests and finishes queued waiters, while held leases can still release. Tests use a manual clock and scheduler to force FIFO, head and middle cancellation, timeout and release together, duplicate release, finally cleanup after failure, and the concurrency cap. The counter invariant proves that no permit is lost or created.”
Common mistakes
- Take the fast path while the queue is non-empty → new callers bypass old ones and starve them → queue every caller while waiters exist.
- Increment available when a waiter cancels → release may already have reserved its permit → race cancellation and release on one one-shot state.
- Expose an ownerless release → duplicate calls create permits → return a lease that can release once.
- Increment available before waking the head → a new caller can cut in line → transfer directly under the same critical section.
- Treat timeout as rollback of a delivered lease → the task may still be running → distinguish waiting cancellation from an acquired permit.
- Allow an unbounded queue → the concurrency limit becomes a memory leak → set a queue cap, timeout, or rejection policy.
- Test only sequential calls → cancellation races and duplicate release are missing → force interleavings with a controllable scheduler.
- Discard held permits on close → resource counts cannot converge → let held leases release in finally.
Follow-up questions and answers
Is FIFO fairness always better?
No. FIFO prevents starvation and is easy to explain, but a long-running or soon-to-time-out head can create head-of-line blocking. A throughput-first implementation may allow a non-fair fast path, but starvation, maximum wait time, and priority must be explicit contract choices rather than assumed properties.
How would you acquire multiple permits at once?
Record each waiter’s requested count and fulfill it only when available is large enough. Strict FIFO can cause one-permit requests behind a multi-permit head to wait; allowing bypass sacrifices fairness. Choose one policy and count reserved permits, not waiter objects, in the invariant.
What if a task is cancelled halfway through its work?
The semaphore owns permits, not task interruption. The caller should stop work on cancellation and release the lease in finally; if work cannot be interrupted, it must finish before releasing. The semaphore must not reclaim a permit that is still in use.
What is the boundary between a semaphore and a mutex?
A semaphore represents a count of available resources, and different actors may acquire and release permits. A mutex represents exclusive ownership and normally requires the owner to unlock. A value-one semaphore may mimic exclusion while losing ownership checks and priority semantics, so choose the primitive that matches the API contract.