Problem statement
Design a counting semaphore and a manager that hands out named semaphores. A semaphore holds a fixed number of permits guarding a limited resource pool (for instance N database connections); a caller acquires a permit before using the resource and releases it afterwards. The manager lets different subsystems share the same limit by name.
Operating context. One process, many threads. acquire(n) removes n permits, blocking until n are simultaneously free; release(n) returns them and wakes waiters that can now proceed. Callers want a timed tryAcquire that gives up at a deadline. The manager is a registry: the first caller to name a limit creates the semaphore with its permit count, and every later caller by that name gets the same instance. A fairness policy decides whether a fresh caller may barge ahead of an older waiter.
Out of scope. Distributed or cluster-wide semaphores, the resources the permits guard, permit leasing or expiry over a network, deadlock detection across several semaphores, and any persistence of permit state.
What to produce. The class model (the semaphore with its permit accounting and waiter queue, and the manager/registry), the public API of each, the state transitions from permits-available to exhausted to callers-queued, and the fairness seam. Be explicit about the permit-count invariant, all-or-nothing multi-permit acquire, and how the manager's get-or-create for a name is atomic.
Functional requirements
- acquire(n) removes n permits, blocking until n permits are simultaneously available.
- release(n) returns n permits and wakes waiters that can now be satisfied.
- tryAcquire(n, timeout) returns failure after a bounded wait instead of blocking forever.
- The manager vends a named semaphore, creating it once with its permit count and returning that same instance thereafter.
- Report the number of available permits and the number of queued waiters.
Non-functional requirements
- Permit invariant: available permits never go negative and never exceed the configured maximum.
- The fairness policy (FIFO versus barging) is pluggable without editing the permit-accounting core.
- acquire and release are O(1) excluding wait time, and a release wakes only waiters it can fully satisfy.
- Thread-safe: the permit count and waiter queue are guarded together so no permit is granted twice.
- The manager's get-or-create for a name is atomic, so concurrent first-callers observe exactly one semaphore.
- Deterministically testable by injecting the condition source and a clock, with no real threads or sleeps.
Topics
- System Design LLD
- Concurrency Synchronization
- Concurrency Fairness
- Patterns Registry
- Oop Interface-Design