Loading learning content...
While binary semaphores (with values 0 or 1) provide mutual exclusion, counting semaphores unlock the full power of Dijkstra's invention: the ability to manage multiple identical resources, coordinate multiple concurrent accessors, and implement sophisticated producer-consumer patterns.
A counting semaphore is initialized to an integer N ≥ 0, where N represents the number of available resources or permits. Each P operation decrements this count, and each V operation increments it. When the count reaches zero, subsequent P operations block until V operations make resources available again.
This page explores counting semaphores in depth: their semantics, canonical use cases, implementation considerations, and the patterns that make them indispensable for resource management in concurrent systems.
By the end of this page, you will be able to: (1) Explain how counting semaphores differ from binary semaphores, (2) Identify scenarios where counting semaphores are the appropriate choice, (3) Implement resource pools and bounded buffers using counting semaphores, (4) Reason about counting semaphore invariants and correctness, and (5) Recognize the relationship between counting semaphores and modern concurrency constructs.
A counting semaphore is a semaphore whose value can range from 0 to any non-negative integer (limited only by system constraints, typically INT_MAX or implementation-specific bounds).
Formally:
This invariant means the semaphore value exactly tracks the difference between resources released and resources acquired, starting from the initial allocation.
The most intuitive way to understand counting semaphores is as resource counters:
This model applies to any scenario with multiple identical, interchangeable resources.
| Aspect | Binary Semaphore | Counting Semaphore |
|---|---|---|
| Value range | 0 or 1 only | 0 to MAX (conceptually unbounded) |
| Initial value | 0 or 1 | Any non-negative integer N |
| Primary use | Mutual exclusion, signaling | Resource counting, bounded concurrency |
| Concurrent holders | At most 1 | At most N |
| Mental model | Lock/unlock, yes/no | Pool of N permits/resources |
| V beyond 1? | Error or capped at 1 | Increases count (may allow more P) |
At any program point, the semaphore value satisfies:
S.value = S.initial + completed_V_operations - completed_P_operations
Where:
S.initial is the initialization valuecompleted_V_operations counts all V calls that have finishedcompleted_P_operations counts all P calls that have successfully decremented (not those still blocked)This equation is a powerful reasoning tool. If you track P and V calls in your program, you can deduce the semaphore value at any point and verify that invariants hold.
Counting semaphores obey a conservation law: resources are neither created nor destroyed, only transferred. If you start with N resources and never call V more than P, you always have exactly N resources in the system—some held by threads (P completed), some in the semaphore (S.value). This conservation makes reasoning about correctness tractable.
Counting semaphores excel in specific, well-defined scenarios. Understanding these canonical uses helps you recognize when counting semaphores are the right tool.
When you have N identical resources that can be used by any thread, a counting semaphore is the natural choice.
Example: Database Connection Pool
A server has 10 database connections. Each request needs one connection. We want to allow up to 10 concurrent database operations, blocking additional requests until a connection is freed.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
#define POOL_SIZE 10 // Pool resourcesconnection_t connections[POOL_SIZE];int available[POOL_SIZE]; // 1 = available, 0 = in use // Counting semaphore: counts available connectionssemaphore_t pool_sem;// Mutex to protect available[] arraysemaphore_t pool_mutex; void init_pool() { sem_init(&pool_sem, POOL_SIZE); // 10 resources available sem_init(&pool_mutex, 1); // Binary for mutual exclusion for (int i = 0; i < POOL_SIZE; i++) { connections[i] = create_connection(); available[i] = 1; }} connection_t* acquire_connection() { // Wait for a connection to be available P(&pool_sem); // Blocks if all 10 are in use // Connection is available; find which one P(&pool_mutex); connection_t *conn = NULL; for (int i = 0; i < POOL_SIZE; i++) { if (available[i]) { available[i] = 0; conn = &connections[i]; break; } } V(&pool_mutex); return conn; // Guaranteed non-null (semaphore protected)} void release_connection(connection_t *conn) { P(&pool_mutex); int idx = conn - connections; // Calculate index available[idx] = 1; V(&pool_mutex); V(&pool_sem); // Signal: one more connection available}Key insight: The counting semaphore (pool_sem) tracks availability count, while the binary mutex (pool_mutex) protects the selection of which specific resource to use. The semaphore guarantees we never try to use an unavailable resource; the mutex ensures we don't race on the selection.
Limit the number of threads that can be active in a region simultaneously.
Example: API Rate Limiter
Allow at most N concurrent API requests to a backend service to prevent overload.
1234567891011121314151617181920212223242526272829303132
#define MAX_CONCURRENT_REQUESTS 100 semaphore_t api_limiter; void init_limiter() { sem_init(&api_limiter, MAX_CONCURRENT_REQUESTS);} response_t make_api_call(request_t *req) { // Acquire permit (at most 100 active) P(&api_limiter); // Make the actual API call response_t resp = call_backend(req); // Release permit for next caller V(&api_limiter); return resp;} // With timeout variant for responsivenessresponse_t make_api_call_with_timeout(request_t *req, int timeout_ms) { if (!P_timed(&api_limiter, timeout_ms)) { return error_response(429, "Too Many Requests"); } response_t resp = call_backend(req); V(&api_limiter); return resp;}Counting semaphores are not ideal when: (1) Resources are not identical (different connections have different capabilities), (2) Fairness beyond FIFO is needed (priority queues, aging), (3) Complex conditions determine availability (use condition variables), or (4) You need ownership tracking (use tickets, handles, or object references instead).
The bounded buffer (also called the producer-consumer problem) is the quintessential counting semaphore application. It demonstrates how two counting semaphores can coordinate producers and consumers sharing a fixed-size buffer.
We use two counting semaphores:
empty: Counts empty slots (producer's resource) — initialized to Nfull: Counts full slots (consumer's resource) — initialized to 0Plus a binary semaphore for mutual exclusion on buffer manipulation.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
#define BUFFER_SIZE 10 item_t buffer[BUFFER_SIZE];int in_index = 0; // Producer inserts hereint out_index = 0; // Consumer removes here // Counting semaphores for coordinationsemaphore_t empty; // Counts empty slotssemaphore_t full; // Counts full slotssemaphore_t mutex; // Binary: protects buffer/indices void init_buffer() { sem_init(&empty, BUFFER_SIZE); // All slots empty initially sem_init(&full, 0); // No items initially sem_init(&mutex, 1); // Mutual exclusion} void producer(item_t item) { // Wait for empty slot P(&empty); // Decrements empty count; blocks if 0 // Mutual exclusion for buffer access P(&mutex); // Insert item buffer[in_index] = item; in_index = (in_index + 1) % BUFFER_SIZE; V(&mutex); // Signal item is available V(&full); // Increments full count; may wake consumer} item_t consumer() { // Wait for item P(&full); // Decrements full count; blocks if 0 // Mutual exclusion for buffer access P(&mutex); // Remove item item_t item = buffer[out_index]; out_index = (out_index + 1) % BUFFER_SIZE; V(&mutex); // Signal slot is empty V(&empty); // Increments empty count; may wake producer return item;}Invariant 1: Buffer never overflows
Invariant 2: Buffer never underflows
Invariant 3: At any time, empty + full = BUFFER_SIZE
The producer must call P(&empty) BEFORE P(&mutex). If reversed: (1) Producer acquires mutex, (2) Buffer is full (empty=0), (3) Producer calls P(&empty) and blocks WHILE HOLDING MUTEX, (4) Consumer tries P(&mutex) and blocks → DEADLOCK! Always acquire resource semaphores before mutex semaphores.
| Semaphore | Initial Value | P by | V by | Represents |
|---|---|---|---|---|
| empty | BUFFER_SIZE | Producer | Consumer | Available slots for writing |
| full | 0 | Consumer | Producer | Available items for reading |
| mutex | 1 | Both | Both | Exclusive access to buffer |
Implementing counting semaphores raises considerations beyond the basic P/V semantics.
Real implementations cannot have truly unbounded values:
What happens when V would exceed the maximum?
// POSIX behavior
int sem_post(sem_t *sem) {
// If value would exceed SEM_VALUE_MAX:
// Returns -1, sets errno = EOVERFLOW
// Semaphore value unchanged
}
This overflow check prevents infinite resource inflation from programming errors.
Some implementations allow the semaphore value to go negative, using the negative value to count waiting processes:
Standard semantics (value ≥ 0):
Negative value semantics:
Semaphore S, initial value 2:
- P() by T1: value = 1, T1 proceeds
- P() by T2: value = 0, T2 proceeds
- P() by T3: value = -1, T3 blocks (the -1 means 1 waiter)
- P() by T4: value = -2, T4 blocks (the -2 means 2 waiters)
- V() by T1: value = -1, wake one waiter
- V() by T2: value = 0, wake one waiter
Both models are mathematically equivalent; the difference is implementation bookkeeping.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
// Counting semaphore implementation with wait count trackingtypedef struct counting_semaphore { int value; // Resource count (can be any non-negative integer) int waiting; // Number of blocked waiters spinlock_t lock; wait_queue_t queue;} counting_sem_t; void counting_sem_init(counting_sem_t *s, int initial_value) { assert(initial_value >= 0); s->value = initial_value; s->waiting = 0; spin_lock_init(&s->lock); wait_queue_init(&s->queue);} void counting_P(counting_sem_t *s) { spin_lock(&s->lock); s->value--; // Optimistically decrement if (s->value < 0) { // We took one we didn't have; must wait s->waiting++; // Block until value becomes positive block_on_queue(&s->queue, &s->lock); // Releases lock while blocked s->waiting--; // Lock reacquired when we wake } spin_unlock(&s->lock);} void counting_V(counting_sem_t *s) { spin_lock(&s->lock); s->value++; // Release one resource if (s->waiting > 0) { // Waiters exist; wake one // The negative value we incremented from means we owe a wakeup wake_one(&s->queue); } spin_unlock(&s->lock);}Some implementations support bulk operations: P(S, n) to acquire n resources atomically, V(S, n) to release n at once. This is useful for operations that need multiple resources (e.g., allocating 4KB pages at once). Java's Semaphore supports this: acquire(int permits) and release(int permits).
Let's examine how counting semaphores are used in real systems and production code.
Java provides a full-featured counting semaphore:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
import java.util.concurrent.Semaphore; public class ConnectionPool { private static final int MAX_CONNECTIONS = 10; private final Semaphore available; private final Connection[] connections; private final boolean[] used; public ConnectionPool() { // Fair semaphore: FIFO ordering for waiting threads this.available = new Semaphore(MAX_CONNECTIONS, true); this.connections = new Connection[MAX_CONNECTIONS]; this.used = new boolean[MAX_CONNECTIONS]; for (int i = 0; i < MAX_CONNECTIONS; i++) { connections[i] = createConnection(); used[i] = false; } } public Connection acquire() throws InterruptedException { // Block until permit available (or interrupt) available.acquire(); // Decrements permits return getNextAvailable(); } public Connection tryAcquire(long timeout, TimeUnit unit) throws InterruptedException { // Try with timeout if (!available.tryAcquire(timeout, unit)) { return null; // Timeout } return getNextAvailable(); } public void release(Connection conn) { if (markAsUnused(conn)) { available.release(); // Increments permits } } // Bulk operations public Connection[] acquireBatch(int count) throws InterruptedException { available.acquire(count); // Atomic multi-acquire // Get 'count' connections... } public void releaseBatch(Connection[] conns) { // Mark as unused... available.release(conns.length); // Atomic multi-release } // Inspection (useful for monitoring) public int availablePermits() { return available.availablePermits(); // Current count } public int getQueueLength() { return available.getQueueLength(); // Approximate waiting threads }}The Linux kernel uses counting semaphores for various purposes:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
// Linux kernel counting semaphore usage #include <linux/semaphore.h> // Define a counting semaphorestruct semaphore resource_sem; // Initialize with count (e.g., 5 resources)void init_resources(void) { sema_init(&resource_sem, 5); // 5 permits initially} // Acquire one resource (blocking)int use_resource(void) { // down() can sleep - use down_interruptible() for killable waits if (down_interruptible(&resource_sem)) { return -EINTR; // Interrupted by signal } // Got the resource, do work... do_work_with_resource(); // Release up(&resource_sem); return 0;} // Non-blocking tryint try_use_resource(void) { if (down_trylock(&resource_sem)) { return -EBUSY; // Resource not available } // Got it do_quick_work(); up(&resource_sem); return 0;} // Common kernel patterns:// - Limiting concurrent I/O operations// - Managing pool of DMA buffers// - Controlling driver instances// - Rate limiting in subsystems| Feature | Java Semaphore | POSIX sem_t | Linux Kernel |
|---|---|---|---|
| Initialize | new Semaphore(n) | sem_init(&s, 0, n) | sema_init(&s, n) |
| P (blocking) | acquire() | sem_wait() | down() |
| P (interruptible) | acquireInterruptibly() | Implicit (EINTR) | down_interruptible() |
| P (non-blocking) | tryAcquire() | sem_trywait() | down_trylock() |
| P (timeout) | tryAcquire(time, unit) | sem_timedwait() | down_timeout() |
| V | release() | sem_post() | up() |
| Bulk P | acquire(n) | N/A (loop) | N/A |
| Bulk V | release(n) | N/A (loop) | N/A |
| Get value | availablePermits() | sem_getvalue() | N/A (internal) |
POSIX distinguishes unnamed semaphores (sem_init, shared via memory) from named semaphores (sem_open, identified by filesystem path, usable across unrelated processes). Counting behavior is identical; the difference is scope and lifetime. Named semaphores persist until explicitly unlinked (sem_unlink) or system reboot.
Counting semaphores, like any tool, can be used well or poorly. Let's examine proven patterns and common mistakes.
Limit concurrent access to a shared subsystem:
12345678910111213141516171819202122
// Pattern: Limit concurrent downloads to prevent resource exhaustion#define MAX_CONCURRENT_DOWNLOADS 5 semaphore_t download_limiter; void init() { sem_init(&download_limiter, MAX_CONCURRENT_DOWNLOADS);} void download_file(const char *url, const char *path) { P(&download_limiter); // Wait for capacity // Only 5 concurrent downloads max download_from_network(url, path); V(&download_limiter); // Release capacity} // Benefits:// - Simple, clear limiting logic// - Self-balancing under load// - No manual queue managementCoordinate N threads reaching a checkpoint before any proceed:
123456789101112131415161718192021222324252627282930313233
// Pattern: Simple barrier using counting semaphores// All N threads must arrive before any continue #define THREAD_COUNT 4 semaphore_t barrier_count; // Counts arrivalssemaphore_t barrier_release; // Released when all arriveint arrived = 0;semaphore_t count_mutex; // Protects 'arrived' void init_barrier() { sem_init(&barrier_count, 0); sem_init(&barrier_release, 0); sem_init(&count_mutex, 1); arrived = 0;} void barrier_wait() { P(&count_mutex); arrived++; if (arrived == THREAD_COUNT) { // Last one to arrive: release all waiters for (int i = 0; i < THREAD_COUNT - 1; i++) { V(&barrier_release); // Release each waiting thread } } V(&count_mutex); if (arrived < THREAD_COUNT) { P(&barrier_release); // Wait for last thread } // Now all threads proceed together}When using a counting semaphore, always be able to clearly answer: 'What does the value COUNT?' If you can't answer clearly (e.g., 'available buffer slots' or 'unused connections'), you may be using the wrong abstraction. Vague semantics lead to subtle bugs.
Counting semaphores are foundational, but modern languages and libraries often provide higher-level abstractions. Understanding the relationship helps you choose the right tool.
Go's buffered channels provide counting-semaphore-like behavior:
123456789101112131415161718192021222324252627282930313233343536373839
// Go: Buffered channel as counting semaphorepackage main // Semaphore via buffered channeltype Semaphore chan struct{} func NewSemaphore(n int) Semaphore { return make(chan struct{}, n) // Buffer size = permit count} func (s Semaphore) Acquire() { s <- struct{}{} // Blocks if buffer full} func (s Semaphore) TryAcquire() bool { select { case s <- struct{}{}: return true default: return false }} func (s Semaphore) Release() { <-s // Remove from buffer, never blocks} // Usagefunc main() { sem := NewSemaphore(3) // 3 permits sem.Acquire() // Got permit 1 sem.Acquire() // Got permit 2 sem.Acquire() // Got permit 3 // sem.Acquire() would block here sem.Release() // Return one sem.Acquire() // Got it back}Python provides counting semaphores with a Pythonic interface:
123456789101112131415161718192021222324252627
import threadingfrom concurrent.futures import ThreadPoolExecutor # Counting semaphore with 5 permitsdb_connections = threading.Semaphore(5) def query_database(query): with db_connections: # Context manager: acquire on enter, release on exit # At most 5 queries execute concurrently return execute_query(query) # BoundedSemaphore prevents releasing more than acquiredbounded = threading.BoundedSemaphore(3) def safe_operation(): bounded.acquire() try: do_work() finally: bounded.release() # ValueError if released more than acquired # asyncio version for async codeimport asyncio async def async_query(query): async with asyncio.Semaphore(10): # Async-aware semaphore return await async_execute(query)| Use Case | Counting Semaphore | Alternative | Prefer Alternative When |
|---|---|---|---|
| Resource pool | Natural fit | Object pool pattern | Need complex resource lifecycle |
| Rate limiting | Works well | Token bucket, sliding window | Need burst handling, time-based |
| Bounded buffer | Classic solution | BlockingQueue (Java), channel | Language provides better abstraction |
| Concurrency limit | Simple and clear | ExecutorService, worker pools | Need task management features |
| Event counting | Possible | AtomicInteger, CountDownLatch | No blocking needed, or one-shot |
Use counting semaphores when you need simple resource counting with blocking. Use language-specific abstractions (BlockingQueue, channels, Executor) when they provide safer, more expressive APIs. Understand semaphores so you can implement and debug higher-level constructs, but prefer higher-level constructs for application code when available.
We have explored counting semaphores comprehensively—their semantics, use cases, implementation considerations, and relationship to modern constructs. Let's consolidate the key insights before examining binary semaphores:
You now understand counting semaphores deeply—their power for resource management and coordination patterns. The next page examines binary semaphores—the special case where the value is restricted to 0 or 1, providing mutual exclusion semantics and the foundation for locks.