Counting Semaphores — Semaphore Concepts | OneNoughtOne

0/105

Operating SystemsSemaphore Concepts

Semaphore Concepts

LevelIntermediate

Duration90 mins

TopicSemaphore Concepts

4 / 5

Counting Semaphores

Beyond Binary: Managing Multiple Resources

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 \geq 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.

Learning Objectives

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.

Fundamental Concepts

The Counting Semaphore Identity 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: Domain: S.value ∈ {0, 1, 2, ..., MAX_VALUE} Initial value: S.value = N, where N represents initial resources/permits Invariant: At any point, S.value = N + (number of V operations) - (number of completed P operations) This invariant means the semaphore value exactly tracks the difference between resources released and resources acquired, starting from the initial allocation. The Resource Counting Model The most intuitive way to understand counting semaphores is as resource counters: Initial value N: N identical resources are available P operation: Request one resource. If available (count > 0), take it (count--). If not (count = 0), wait. V operation: Return one resource (count++), potentially waking a waiter. This model applies to any scenario with multiple identical, interchangeable resources.

Counting Semaphore vs. Binary Semaphore
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)

The Semaphore Value Equation At any program point, the semaphore value satisfies: S.value = S.initial + completed_V_operations - completed_P_operations Where: S.initial is the initialization value completed_V_operations counts all V calls that have finished completed_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.

The Conservation Law

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.

Canonical Use Cases

Counting semaphores excel in specific, well-defined scenarios. Understanding these canonical uses helps you recognize when counting semaphores are the right tool. Use Case 1: Resource Pool Management 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.

connection_pool.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define POOL_SIZE 10
 
// Pool resources
connection_t connections[POOL_SIZE];
int available[POOL_SIZE];  // 1 = available, 0 = in use
 
// Counting semaphore: counts available connections
semaphore_t pool_sem;
// Mutex to protect available[] array
semaphore_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. Use Case 2: Bounded Concurrency (Rate Limiting) 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.

rate_limiter.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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 responsiveness
response_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;
}

More Counting Semaphore Use Cases

•Thread Pool Size Control — Start N threads; semaphore counts available workers
•Print Queue Capacity — Printer buffers N pages; semaphore tracks buffer space
•Parking Lot Management — N spots; semaphore allows N entries before blocking
•License Key Management — N floating licenses; semaphore enforces limit
•Memory Pool Allocation — N fixed-size blocks; semaphore tracks free blocks
•Batch Processing Limit — Process at most N items concurrently

When NOT to Use Counting Semaphores

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 Pattern

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. The Problem Statement Producers generate items and place them in a buffer Consumers remove items from the buffer and process them The buffer has fixed capacity N Producers must wait if the buffer is full Consumers must wait if the buffer is empty No item should be lost or duplicated The Two-Semaphore Solution We use two counting semaphores: empty : Counts empty slots (producer's resource) — initialized to N full : Counts full slots (consumer's resource) — initialized to 0 Plus a binary semaphore for mutual exclusion on buffer manipulation.

bounded_buffer.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define BUFFER_SIZE 10
 
item_t buffer[BUFFER_SIZE];
int in_index = 0;   // Producer inserts here
int out_index = 0;  // Consumer removes here
 
// Counting semaphores for coordination
semaphore_t empty;  // Counts empty slots
semaphore_t full;   // Counts full slots
semaphore_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;
}

Correctness Analysis Invariant 1: Buffer never overflows Producer calls P(&empty) before inserting If buffer is full (empty = 0), producer blocks Only after successful P (decrementing empty) can producer insert Therefore: insertions \leq initial_empty + consumer V(&empty) calls = exactly the number of available slots Invariant 2: Buffer never underflows Consumer calls P(&full) before removing If buffer is empty (full = 0), consumer blocks Only after successful P (decrementing full) can consumer remove Therefore: removals \leq producer V(&full) calls = exactly the number of inserted items Invariant 3: At any time, empty + full = BUFFER_SIZE Initially: empty = N, full = 0 \to sum = N Producer: P(empty), V(full) \to (empty-1) + (full+1) = N ✓ Consumer: P(full), V(empty) \to (empty+1) + (full-1) = N ✓ Conservation law holds!

Critical: P Order Matters!

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 \to DEADLOCK! Always acquire resource semaphores before mutex semaphores.

Bounded Buffer Semaphore Roles
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

Implementation Considerations

Implementing counting semaphores raises considerations beyond the basic P/V semantics. Maximum Value Bounds Real implementations cannot have truly unbounded values: POSIX: SEM_VALUE_MAX (at least 32767, often INT_MAX) Linux kernel: Typically signed int (2^31 - 1) Java: Uses int permits (2^31 - 1) 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.

Negative Value Semantics Some implementations allow the semaphore value to go negative, using the negative value to count waiting processes: Standard semantics (value \geq 0): Value represents available resources Waiters counted separately in queue Negative value semantics: Positive value: available resources Zero: no resources, no waiters Negative value: no resources, |value| waiters 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.

counting_sem_implementation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Counting semaphore implementation with wait count tracking
typedef 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);
}

Bulk Operations

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).

Counting Semaphores in Practice

Let's examine how counting semaphores are used in real systems and production code. Java's Semaphore Class Java provides a full-featured counting semaphore:

JavaSemaphoreExample.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
    }
}

Linux Kernel Counting Semaphores The Linux kernel uses counting semaphores for various purposes:

linux_counting_sem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Linux kernel counting semaphore usage
 
#include <linux/semaphore.h>
 
// Define a counting semaphore
struct 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 try
int 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

Counting Semaphore APIs Comparison
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)

Unnamed vs. Named Semaphores

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.

Patterns and Anti-patterns

Counting semaphores, like any tool, can be used well or poorly. Let's examine proven patterns and common mistakes. Pattern: Semaphore as Capacity Limiter Limit concurrent access to a shared subsystem:

capacity_limiter.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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 management

Pattern: Semaphore for Synchronization Barrier Coordinate N threads reaching a checkpoint before any proceed:

barrier_semaphore.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Pattern: Simple barrier using counting semaphores
// All N threads must arrive before any continue
 
#define THREAD_COUNT 4
 
semaphore_t barrier_count;     // Counts arrivals
semaphore_t barrier_release;   // Released when all arrive
int 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
}

Good Patterns

•Fixed-size pools — Known max resources, clear acquire/release
•Rate limiting — Bounded concurrent operations
•Producer-consumer — Bounded buffer with empty/full tracking
•Readers counting — Track active readers (first/last special handling)
•Thread coordination — N threads must reach checkpoint

Anti-patterns

•Unbounded counting — Value grows without limit (leak)
•Non-matching P/V — Different threads P and V without clear protocol
•Semaphore as condition — Use condition variables for complex conditions
•Priority with semaphores — Semaphores don't naturally express priority
•Global semaphores for local state — Overuse of shared synchronization

The 'Counting What?' Question

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.

Relationship to Modern Constructs

Counting semaphores are foundational, but modern languages and libraries often provide higher-level abstractions. Understanding the relationship helps you choose the right tool. Channel Buffers (Go) Go's buffered channels provide counting-semaphore-like behavior:

go_channel_as_semaphore.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Go: Buffered channel as counting semaphore
package main
 
// Semaphore via buffered channel
type 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
}
 
// Usage
func 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's threading.Semaphore Python provides counting semaphores with a Pythonic interface:

python_semaphore.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import threading
from concurrent.futures import ThreadPoolExecutor
 
# Counting semaphore with 5 permits
db_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 acquired
bounded = threading.BoundedSemaphore(3)
 
def safe_operation():
    bounded.acquire()
    try:
        do_work()
    finally:
        bounded.release()  # ValueError if released more than acquired
 
# asyncio version for async code
import asyncio
 
async def async_query(query):
    async with asyncio.Semaphore(10):  # Async-aware semaphore
        return await async_execute(query)

Counting Semaphores vs. Alternatives
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

Choosing the Right Abstraction

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.

Operating SystemsSemaphore Concepts

Semaphore Concepts

LevelIntermediate

Duration90 mins

TopicSemaphore Concepts

4 / 5

Counting Semaphores

Beyond Binary: Managing Multiple Resources

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 \geq 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.

Learning Objectives

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.

Fundamental Concepts

The Counting Semaphore Identity 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: Domain: S.value ∈ {0, 1, 2, ..., MAX_VALUE} Initial value: S.value = N, where N represents initial resources/permits Invariant: At any point, S.value = N + (number of V operations) - (number of completed P operations) This invariant means the semaphore value exactly tracks the difference between resources released and resources acquired, starting from the initial allocation. The Resource Counting Model The most intuitive way to understand counting semaphores is as resource counters: Initial value N: N identical resources are available P operation: Request one resource. If available (count > 0), take it (count--). If not (count = 0), wait. V operation: Return one resource (count++), potentially waking a waiter. This model applies to any scenario with multiple identical, interchangeable resources.

Counting Semaphore vs. Binary Semaphore
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)

The Semaphore Value Equation At any program point, the semaphore value satisfies: S.value = S.initial + completed_V_operations - completed_P_operations Where: S.initial is the initialization value completed_V_operations counts all V calls that have finished completed_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.

The Conservation Law

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.

Canonical Use Cases

Counting semaphores excel in specific, well-defined scenarios. Understanding these canonical uses helps you recognize when counting semaphores are the right tool. Use Case 1: Resource Pool Management 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.

connection_pool.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define POOL_SIZE 10
 
// Pool resources
connection_t connections[POOL_SIZE];
int available[POOL_SIZE];  // 1 = available, 0 = in use
 
// Counting semaphore: counts available connections
semaphore_t pool_sem;
// Mutex to protect available[] array
semaphore_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. Use Case 2: Bounded Concurrency (Rate Limiting) 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.

rate_limiter.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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 responsiveness
response_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;
}

More Counting Semaphore Use Cases

•Thread Pool Size Control — Start N threads; semaphore counts available workers
•Print Queue Capacity — Printer buffers N pages; semaphore tracks buffer space
•Parking Lot Management — N spots; semaphore allows N entries before blocking
•License Key Management — N floating licenses; semaphore enforces limit
•Memory Pool Allocation — N fixed-size blocks; semaphore tracks free blocks
•Batch Processing Limit — Process at most N items concurrently

When NOT to Use Counting Semaphores

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 Pattern

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. The Problem Statement Producers generate items and place them in a buffer Consumers remove items from the buffer and process them The buffer has fixed capacity N Producers must wait if the buffer is full Consumers must wait if the buffer is empty No item should be lost or duplicated The Two-Semaphore Solution We use two counting semaphores: empty : Counts empty slots (producer's resource) — initialized to N full : Counts full slots (consumer's resource) — initialized to 0 Plus a binary semaphore for mutual exclusion on buffer manipulation.

bounded_buffer.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define BUFFER_SIZE 10
 
item_t buffer[BUFFER_SIZE];
int in_index = 0;   // Producer inserts here
int out_index = 0;  // Consumer removes here
 
// Counting semaphores for coordination
semaphore_t empty;  // Counts empty slots
semaphore_t full;   // Counts full slots
semaphore_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;
}

Correctness Analysis Invariant 1: Buffer never overflows Producer calls P(&empty) before inserting If buffer is full (empty = 0), producer blocks Only after successful P (decrementing empty) can producer insert Therefore: insertions \leq initial_empty + consumer V(&empty) calls = exactly the number of available slots Invariant 2: Buffer never underflows Consumer calls P(&full) before removing If buffer is empty (full = 0), consumer blocks Only after successful P (decrementing full) can consumer remove Therefore: removals \leq producer V(&full) calls = exactly the number of inserted items Invariant 3: At any time, empty + full = BUFFER_SIZE Initially: empty = N, full = 0 \to sum = N Producer: P(empty), V(full) \to (empty-1) + (full+1) = N ✓ Consumer: P(full), V(empty) \to (empty+1) + (full-1) = N ✓ Conservation law holds!

Critical: P Order Matters!

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 \to DEADLOCK! Always acquire resource semaphores before mutex semaphores.

Bounded Buffer Semaphore Roles
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

Implementation Considerations

Implementing counting semaphores raises considerations beyond the basic P/V semantics. Maximum Value Bounds Real implementations cannot have truly unbounded values: POSIX: SEM_VALUE_MAX (at least 32767, often INT_MAX) Linux kernel: Typically signed int (2^31 - 1) Java: Uses int permits (2^31 - 1) 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.

Negative Value Semantics Some implementations allow the semaphore value to go negative, using the negative value to count waiting processes: Standard semantics (value \geq 0): Value represents available resources Waiters counted separately in queue Negative value semantics: Positive value: available resources Zero: no resources, no waiters Negative value: no resources, |value| waiters 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.

counting_sem_implementation.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Counting semaphore implementation with wait count tracking
typedef 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);
}

Bulk Operations

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).

Counting Semaphores in Practice

Let's examine how counting semaphores are used in real systems and production code. Java's Semaphore Class Java provides a full-featured counting semaphore:

JavaSemaphoreExample.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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
    }
}

Linux Kernel Counting Semaphores The Linux kernel uses counting semaphores for various purposes:

linux_counting_sem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Linux kernel counting semaphore usage
 
#include <linux/semaphore.h>
 
// Define a counting semaphore
struct 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 try
int 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

Counting Semaphore APIs Comparison
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)

Unnamed vs. Named Semaphores

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.

Patterns and Anti-patterns

Counting semaphores, like any tool, can be used well or poorly. Let's examine proven patterns and common mistakes. Pattern: Semaphore as Capacity Limiter Limit concurrent access to a shared subsystem:

capacity_limiter.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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 management

Pattern: Semaphore for Synchronization Barrier Coordinate N threads reaching a checkpoint before any proceed:

barrier_semaphore.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Pattern: Simple barrier using counting semaphores
// All N threads must arrive before any continue
 
#define THREAD_COUNT 4
 
semaphore_t barrier_count;     // Counts arrivals
semaphore_t barrier_release;   // Released when all arrive
int 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
}

Good Patterns

•Fixed-size pools — Known max resources, clear acquire/release
•Rate limiting — Bounded concurrent operations
•Producer-consumer — Bounded buffer with empty/full tracking
•Readers counting — Track active readers (first/last special handling)
•Thread coordination — N threads must reach checkpoint

Anti-patterns

•Unbounded counting — Value grows without limit (leak)
•Non-matching P/V — Different threads P and V without clear protocol
•Semaphore as condition — Use condition variables for complex conditions
•Priority with semaphores — Semaphores don't naturally express priority
•Global semaphores for local state — Overuse of shared synchronization

The 'Counting What?' Question

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.

Relationship to Modern Constructs

Counting semaphores are foundational, but modern languages and libraries often provide higher-level abstractions. Understanding the relationship helps you choose the right tool. Channel Buffers (Go) Go's buffered channels provide counting-semaphore-like behavior:

go_channel_as_semaphore.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Go: Buffered channel as counting semaphore
package main
 
// Semaphore via buffered channel
type 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
}
 
// Usage
func 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's threading.Semaphore Python provides counting semaphores with a Pythonic interface:

python_semaphore.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import threading
from concurrent.futures import ThreadPoolExecutor
 
# Counting semaphore with 5 permits
db_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 acquired
bounded = threading.BoundedSemaphore(3)
 
def safe_operation():
    bounded.acquire()
    try:
        do_work()
    finally:
        bounded.release()  # ValueError if released more than acquired
 
# asyncio version for async code
import asyncio
 
async def async_query(query):
    async with asyncio.Semaphore(10):  # Async-aware semaphore
        return await async_execute(query)

Counting Semaphores vs. Alternatives
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

Choosing the Right Abstraction

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.

Counting Semaphores

Beyond Binary: Managing Multiple Resources

Fundamental Concepts

The Counting Semaphore Identity

The Resource Counting Model

The Semaphore Value Equation

Canonical Use Cases

Use Case 1: Resource Pool Management

Use Case 2: Bounded Concurrency (Rate Limiting)

The Bounded Buffer Pattern

The Problem Statement

The Two-Semaphore Solution

Correctness Analysis

Implementation Considerations

Maximum Value Bounds

Negative Value Semantics

Counting Semaphores in Practice

Java's Semaphore Class

Linux Kernel Counting Semaphores

Patterns and Anti-patterns

Pattern: Semaphore as Capacity Limiter

Pattern: Semaphore for Synchronization Barrier

Relationship to Modern Constructs

Channel Buffers (Go)

Python's threading.Semaphore

There’s more to understand.

Counting Semaphores

Beyond Binary: Managing Multiple Resources

Fundamental Concepts

The Counting Semaphore Identity

The Resource Counting Model

The Semaphore Value Equation

Canonical Use Cases

Use Case 1: Resource Pool Management

Use Case 2: Bounded Concurrency (Rate Limiting)

The Bounded Buffer Pattern

The Problem Statement

The Two-Semaphore Solution

Correctness Analysis

Implementation Considerations

Maximum Value Bounds

Negative Value Semantics

Counting Semaphores in Practice

Java's Semaphore Class

Linux Kernel Counting Semaphores

Patterns and Anti-patterns

Pattern: Semaphore as Capacity Limiter

Pattern: Semaphore for Synchronization Barrier

Relationship to Modern Constructs

Channel Buffers (Go)

Python's threading.Semaphore

There’s more to understand.