Synchronization Primitives: Coordinating Concurrent Access
Semaphores: Counting-Based Synchronization
A mutex is an all-or-nothing gate: one thread enters, all others wait. But what if you have a resource that can serve multiple clients simultaneously—just not unlimited?
Consider a database connection pool with 10 connections. It would be wasteful to limit access to a single thread when 10 could work in parallel. Yet allowing unlimited concurrent access would exhaust the pool. You need a synchronization mechanism that can count—one that permits up to N simultaneous holders.
Enter the semaphore. Invented by Edsger Dijkstra in 1965, semaphores are one of the most elegant and powerful synchronization abstractions in computer science. While mutexes answer "Is anyone using this?", semaphores answer "How many are using this, and is there still room?"
By completing this page, you will understand the semaphore abstraction, distinguish between binary and counting semaphores, implement classic synchronization patterns (producer-consumer, bounded buffer, dining philosophers), and apply semaphores to real-world problems like connection pooling, rate limiting, and resource management.
A semaphore is a synchronization object that maintains an integer counter representing available "permits" or "resources". It supports two fundamental operations, historically named by Dijkstra using Dutch words:
-
P (Proberen, "to test"): Also called
wait(),acquire(), ordown(). Attempts to decrement the counter. If the counter is zero, the calling thread blocks until a permit becomes available. -
V (Verhogen, "to increment"): Also called
signal(),release(), orup(). Increments the counter, potentially waking a blocked thread.
The Semaphore Invariant:
At all times, the semaphore maintains:
permits >= 0
permits = initial_permits - P_operations + V_operations
This invariant guarantees that if you initialize a semaphore with N permits, at most N threads can hold permits simultaneously.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
// Conceptual semaphore implementationclass Semaphore { private int permits; private Queue<Thread> waitQueue = new Queue<>(); Semaphore(int initialPermits) { if (initialPermits < 0) throw IllegalArgumentException(); this.permits = initialPermits; } // P operation - acquire a permit void acquire() { atomically { while (permits == 0) { // No permits available - wait waitQueue.enqueue(currentThread()); block(currentThread()); } permits--; // Consume one permit } } // V operation - release a permit void release() { atomically { permits++; // Add permit back if (!waitQueue.isEmpty()) { Thread waiting = waitQueue.dequeue(); unblock(waiting); // Wake one waiter } } } // Non-blocking try boolean tryAcquire() { atomically { if (permits > 0) { permits--; return true; } return false; } } // Available permits (snapshot, may change immediately) int availablePermits() { return permits; }}Dijkstra introduced semaphores in his seminal 1965 paper 'Cooperating Sequential Processes'. The metaphor was a railway semaphore signal—a flag or light indicating whether a track section was clear. Just as multiple trains approaching a single-track section must wait for the signal, multiple threads approaching a limited resource must wait for permits.
Semaphores come in two fundamental flavors, each suited to different synchronization needs:
- •Range: Only values 0 and 1
- •Behavior: Similar to a mutex
- •Use case: Mutual exclusion, signaling
- •Key difference from mutex: Any thread can release, not just the owner
- •Also called: Binary flag, mutex semaphore
- •Range: 0 to any positive integer
- •Behavior: Controls access to N resources
- •Use case: Resource pools, rate limiting
- •Key feature: Multiple threads can hold permits simultaneously
- •Also called: General semaphore, counting flag
Critical Distinction: Semaphore vs Mutex
While a binary semaphore and a mutex both provide mutual exclusion, they differ in one crucial aspect:
| Property | Mutex | Binary Semaphore |
|---|---|---|
| Ownership | Yes - only owner can unlock | No - any thread can release |
| Priority Inheritance | Often supported | Typically not |
| Recursive acquisition | Possible (reentrant) | Not applicable |
| Primary use | Protecting critical sections | Signaling between threads |
The lack of ownership in semaphores makes them suitable for signaling patterns where one thread produces a signal and another consumes it. A producer can release a permit that a consumer acquires—neither "owns" the semaphore.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
import java.util.concurrent.Semaphore; class SemaphoreTypes { // Binary semaphore for signaling // Thread A signals Thread B that work is ready static class SignalExample { private final Semaphore signal = new Semaphore(0); // Start with 0 void producer() { // Do work... prepareData(); // Signal that data is ready (any thread can release) signal.release(); // Permits: 0 -> 1 } void consumer() throws InterruptedException { // Wait for signal signal.acquire(); // Blocks until producer releases // Data is guaranteed to be ready processData(); } } // Counting semaphore for resource pool static class ConnectionPool { private static final int POOL_SIZE = 10; private final Semaphore available = new Semaphore(POOL_SIZE); private final Connection[] connections = new Connection[POOL_SIZE]; private final boolean[] inUse = new boolean[POOL_SIZE]; Connection acquire() throws InterruptedException { available.acquire(); // Wait for available slot return getNextAvailable(); } void release(Connection conn) { markAsAvailable(conn); available.release(); // Return permit to pool } private synchronized Connection getNextAvailable() { for (int i = 0; i < POOL_SIZE; i++) { if (!inUse[i]) { inUse[i] = true; return connections[i]; } } throw new IllegalStateException("No connection available"); } private synchronized void markAsAvailable(Connection conn) { for (int i = 0; i < POOL_SIZE; i++) { if (connections[i] == conn) { inUse[i] = false; return; } } } }}Several canonical problems in concurrent programming are elegantly solved with semaphores. Understanding these patterns equips you to recognize and solve similar problems in production systems.
The Producer-Consumer Problem (Bounded Buffer)
Producers generate data items and place them in a shared buffer. Consumers remove and process items. The buffer has limited capacity, requiring coordination:
- Producers must wait when the buffer is full
- Consumers must wait when the buffer is empty
- Access to the buffer must be thread-safe
This is the foundation of message queues, work queues, and pipeline architectures.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
import java.util.concurrent.Semaphore; class BoundedBuffer<T> { private final Object[] buffer; private int head = 0, tail = 0; // Three semaphores coordinate everything private final Semaphore empty; // Counts empty slots private final Semaphore full; // Counts filled slots private final Semaphore mutex; // Protects buffer access public BoundedBuffer(int capacity) { buffer = new Object[capacity]; empty = new Semaphore(capacity); // All slots empty full = new Semaphore(0); // No items yet mutex = new Semaphore(1); // Binary mutex } public void put(T item) throws InterruptedException { empty.acquire(); // Wait for empty slot (blocks if full) mutex.acquire(); // Exclusive buffer access try { buffer[tail] = item; tail = (tail + 1) % buffer.length; } finally { mutex.release(); } full.release(); // Signal item available } @SuppressWarnings("unchecked") public T take() throws InterruptedException { full.acquire(); // Wait for item (blocks if empty) mutex.acquire(); // Exclusive buffer access T item; try { item = (T) buffer[head]; buffer[head] = null; // Help GC head = (head + 1) % buffer.length; } finally { mutex.release(); } empty.release(); // Signal slot freed return item; }} // Usageclass ProducerConsumerExample { public static void main(String[] args) { BoundedBuffer<String> queue = new BoundedBuffer<>(10); // Producer thread new Thread(() -> { for (int i = 0; i < 100; i++) { try { queue.put("Item " + i); System.out.println("Produced: Item " + i); } catch (InterruptedException e) { break; } } }).start(); // Consumer thread new Thread(() -> { for (int i = 0; i < 100; i++) { try { String item = queue.take(); System.out.println("Consumed: " + item); } catch (InterruptedException e) { break; } } }).start(); }}The bounded buffer uses three semaphores: 'empty' counts available slots (producers wait), 'full' counts available items (consumers wait), and 'mutex' ensures atomic buffer manipulation. This pattern appears everywhere—connection pools, thread pools, message queues.
Semaphores solve countless practical problems in production systems. Here are patterns you'll encounter regularly:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.concurrent.*; /** * Token bucket rate limiter using semaphores. * Allows bursts up to bucket size, then enforces rate limit. */class TokenBucketRateLimiter { private final Semaphore tokens; private final int maxTokens; private final ScheduledExecutorService scheduler; /** * @param permitsPerSecond Steady-state rate limit * @param burstSize Maximum burst allowed */ public TokenBucketRateLimiter(double permitsPerSecond, int burstSize) { this.maxTokens = burstSize; this.tokens = new Semaphore(burstSize); // Start full this.scheduler = Executors.newSingleThreadScheduledExecutor(); // Refill tokens at steady rate long intervalMicros = (long)(1_000_000 / permitsPerSecond); scheduler.scheduleAtFixedRate( this::addToken, intervalMicros, intervalMicros, TimeUnit.MICROSECONDS ); } private void addToken() { if (tokens.availablePermits() < maxTokens) { tokens.release(); // Add one token } } /** * Acquire a permit, blocking if rate limit exceeded. */ public void acquire() throws InterruptedException { tokens.acquire(); } /** * Try to acquire without blocking. * @return true if acquired, false if rate limited */ public boolean tryAcquire() { return tokens.tryAcquire(); } /** * Try with timeout. */ public boolean tryAcquire(long timeout, TimeUnit unit) throws InterruptedException { return tokens.tryAcquire(timeout, unit); } public void shutdown() { scheduler.shutdown(); }} // Usage exampleclass RateLimiterExample { public static void main(String[] args) throws Exception { // 10 requests/second with burst of 5 TokenBucketRateLimiter limiter = new TokenBucketRateLimiter(10, 5); for (int i = 0; i < 20; i++) { limiter.acquire(); // Blocks when rate exceeded System.out.println("Request " + i + " at " + System.currentTimeMillis() % 10000); } limiter.shutdown(); }}Semaphores are powerful but can be misused. Understanding common mistakes helps you write correct concurrent code.
- •Forgetting to release: Unlike try-finally patterns with mutexes, it's easy to forget release() on error paths. Use try-finally religiously.
- •Releasing without acquiring: Since semaphores lack ownership, you can release() more than you acquire(), inflating permits beyond initial count. This silently breaks invariants.
- •Using semaphores for mutual exclusion when mutexes are better: Mutexes provide ownership tracking, priority inheritance, and deadlock detection. Use them for critical sections.
- •Permit count mismatches in resource pools: If pool size is 10 but semaphore initialized with 5, half the pool is wasted. They must match exactly.
- •Blocking indefinitely on acquire: Always consider timeouts with tryAcquire() for production code. Indefinite waits hide bugs and cause system hangs.
- •Release called without acquire
- •Permits grow beyond initial count
- •More concurrent access than intended
- •Resource exhaustion or corruption
12345678910111213141516
// BAD: Permit inflation bugSemaphore pool = new Semaphore(10); void doWork() { if (someCondition()) { pool.release(); // BUG: Released without acquire! return; // Now pool has 11 permits } pool.acquire(); try { work(); } finally { pool.release(); }}- •Early returns before acquire are fine
- •Release only in finally after acquire
- •Permit count stays bounded
- •Invariants preserved
123456789101112131415
// GOOD: Balanced acquire/releaseSemaphore pool = new Semaphore(10); void doWork() { if (someCondition()) { return; // Fine: no acquire yet } pool.acquire(); try { work(); } finally { pool.release(); // Always matches acquire }}Encapsulate semaphore pairs (acquire/release) in domain-specific classes like ConnectionPool or RateLimiter. The class manages the semaphore internally, making misuse impossible for callers. Public APIs should rarely expose raw semaphores.
Semaphore performance depends on contention patterns, implementation quality, and usage context. Here are key factors affecting throughput:
| Factor | Impact | Optimization |
|---|---|---|
| Contention level | High contention causes context switches | Increase permits or reduce hold time |
| Fairness mode | Fair semaphores have higher overhead | Use unfair unless ordering matters |
| tryAcquire vs acquire | tryAcquire is non-blocking | Use for fast-path optimization |
| Permit count | Higher counts reduce contention | Match actual resource availability |
| Wake-up policy | Thundering herd on mass release | Consider single-permit releases |
Fair vs Unfair Semaphores:
Most semaphore implementations offer a fairness option:
-
Unfair (default): Incoming threads may "jump the queue" if a permit is available when they arrive. Higher throughput, possible starvation.
-
Fair: Strict FIFO ordering. No starvation, but lower throughput due to queue management overhead.
In practice, unfair semaphores work well for most applications. Use fair semaphores when:
- Long wait times make starvation a real concern
- Ordering has business meaning (e.g., request priority)
- Debugging requires predictable behavior
123456789
// Java: Fair vs unfair semaphoresSemaphore unfair = new Semaphore(10); // Default: unfairSemaphore fair = new Semaphore(10, true); // Fair: FIFO ordering // Python: threading.Semaphore is always unfair (no fairness option)# Use queue.Queue for fair ordering if needed // C++20: std::counting_semaphore has implementation-defined fairness// Check your platform's documentationWe've explored semaphores from fundamental concepts through production patterns. Here are the key takeaways:
- •Semaphores generalize mutexes — They count permits rather than just locked/unlocked, enabling resource pool patterns
- •Binary semaphores differ from mutexes — No ownership means any thread can release; suited for signaling between threads
- •Classic problems teach patterns — Producer-consumer, readers-writers, and dining philosophers solutions transfer to real systems
- •Bounded buffer uses three semaphores — 'empty' for producers, 'full' for consumers, 'mutex' for safe access
- •Always balance acquire/release — Unlike owned locks, semaphores won't catch misuse; use try-finally religiously
- •Encapsulate in domain classes — ConnectionPool, RateLimiter abstractions prevent user errors with raw semaphores
What's Next:
Semaphores and mutexes provide low-level synchronization, but coordinating complex wait conditions requires more structure. The next page explores Monitors—a higher-level abstraction that combines mutual exclusion with condition variables, enabling sophisticated thread coordination patterns.
You now understand semaphores—their mechanics, variations, classic applications, and production patterns. You can implement bounded buffers, rate limiters, and resource pools with confidence. Next, we'll explore monitors and condition variables for complex coordination scenarios.