Free lesson · Operating Systems

Signaling with a semaphore - Thread B tells Thread A that data is ready

Easy12 min readoperating-systemsosconcurrency

Beyond One at a Time

A mutex allows exactly one thread into the critical section. For many problems - incrementing a counter, updating a balance, modifying a linked list - that is exactly right. But some problems need a different constraint: not "only one thread at a time," but "at most N threads at a time."

Consider a database connection pool with 10 connections. You do not want to limit access to one thread - that would serialize your entire application. You want to let up to 10 threads each grab a connection and work concurrently, but block the 11th thread until a connection is returned. Or consider a parking garage with 500 spaces. The gate should let cars in as long as spaces are available and block them when the garage is full. The constraint is not mutual exclusion - it is bounded concurrency.

A semaphore is a synchronization primitive that generalizes the mutex to solve this class of problems. Where a mutex is a binary switch (locked or unlocked), a semaphore is a counter. The counter represents the number of available resources (or available permits). Threads decrement the counter to acquire a permit and increment it to release one. When the counter reaches zero, the next thread that tries to acquire blocks until another thread releases.

Semaphores were invented by Edsger Dijkstra in 1965 - they are one of the oldest synchronization primitives in computer science, and they remain one of the most important. The names Dijkstra gave to the operations - P (from the Dutch "proberen," to test) and V (from "verhogen," to increment) - are still used in academic literature, though most practical APIs use wait/signal or acquire/release instead.

How a Semaphore Works

A semaphore is a data structure with two components:

A counter - a non-negative integer that represents the number of available permits. The initial value of the counter is set when the semaphore is created and represents the maximum concurrency allowed.

A wait queue - a list of threads that tried to acquire when the counter was zero and are now sleeping.

The two operations are:

Wait (P / acquire / down): If the counter is greater than zero, decrement it and return immediately - the thread has acquired a permit. If the counter is zero, add the thread to the wait queue and put it to sleep. The thread does not return from the wait call until a permit is available.

Signal (V / release / up): Increment the counter. If any threads are in the wait queue, wake one of them up - that thread's pending wait call will now succeed (and the counter stays at zero because the just-released permit goes directly to the woken thread).

Both operations must be atomic - the check-and-decrement in wait, and the increment-and-wake in signal, must each execute without interruption. This is implemented using the same hardware atomic instructions (CAS, test-and-set) and OS scheduling that mutexes use.

sequenceDiagram
    participant T1 as Thread 1
    participant S as Semaphore<br/>(count = 2)
    participant T2 as Thread 2
    participant T3 as Thread 3
    
    T1->>S: wait() - count: 2 → 1
    Note over T1: Acquired permit
    
    T2->>S: wait() - count: 1 → 0
    Note over T2: Acquired permit
    
    T3->>S: wait() - count = 0
    Note over T3: BLOCKED (sleeping)
    
    T1->>S: signal() - count: 0 → 0 (wake T3)
    Note over T1: Released permit
    
    Note over T3: Woken up - acquired permit
    
    T2->>S: signal() - count: 0 → 1
    Note over T2: Released permit
    
    T3->>S: signal() - count: 1 → 2
    Note over T3: Released permit

This sequence diagram shows a semaphore with an initial count of 2. Thread 1 calls wait, decrementing the count from 2 to 1 and acquiring a permit. Thread 2 calls wait, decrementing from 1 to 0. Thread 3 calls wait, but the count is 0, so Thread 3 is blocked and put to sleep. When Thread 1 calls signal, instead of incrementing the count, the semaphore wakes Thread 3, which acquires the released permit. Thread 2 and Thread 3 later signal, incrementing the count back toward 2.

Binary Semaphores vs Counting Semaphores

There are two types of semaphores, distinguished by their initial count and intended use:

Binary semaphore - initialized to 1. It can only be 0 or 1. When it is 1, one thread can acquire it. When it is 0, any acquiring thread blocks. This behaves almost identically to a mutex.

Counting semaphore - initialized to N (where N > 1). It allows up to N threads to hold permits simultaneously. This is the generalization that handles the connection pool and parking garage scenarios.

Binary Semaphore vs Mutex: They Are Not the Same

A binary semaphore and a mutex both enforce mutual exclusion, but they have an important conceptual difference:

A mutex has an owner. The thread that locks a mutex must be the thread that unlocks it. This is enforced (at least by convention, and sometimes by the implementation). A mutex is like a key to a room - whoever takes the key is the one who must return it.

A semaphore has no owner. Any thread can signal a semaphore, regardless of which thread last called wait. A semaphore is like a ticket counter - anyone can take a ticket, and anyone can add a ticket back. This makes semaphores more flexible but also more error-prone.

This difference matters for one critical use case: signaling between threads. A semaphore initialized to 0 can be used as a signaling mechanism - one thread waits on it, and another thread signals it when an event occurs. A mutex cannot do this because the thread that would need to "unlock" is not the thread that "locked."

# Signaling with a semaphore - Thread B tells Thread A that data is ready
import threading

data_ready = threading.Semaphore(0)  # Initially 0 - no data yet
shared_data = None

def producer():
    global shared_data
    shared_data = compute_data()     # Produce data
    data_ready.release()              # Signal: data is ready (0 → 1)

def consumer():
    data_ready.acquire()              # Wait until data is ready (blocks until signal)
    process(shared_data)              # Use data - guaranteed to be ready

This signaling pattern is the foundation of producer-consumer coordination, and it is something a mutex cannot do cleanly.

Property	Mutex	Binary Semaphore	Counting Semaphore
Max concurrent holders	1	1	N
Has owner	Yes	No	No
Must be released by acquirer	Yes	No	No
Can be used for signaling	No	Yes	Yes
Recursive locking	Some implementations	No	No
Priority inheritance	Some implementations	Rarely	No

Using Semaphores in Practice

Connection Pool Limiter

The most intuitive use of a counting semaphore: limiting access to a pool of N identical resources.

import threading
import time
import random

# Simulate a database connection pool with 3 connections
pool_semaphore = threading.Semaphore(3)
active_connections = []
log_lock = threading.Lock()

def log(msg):
    with log_lock:
        print(msg)

def database_query(thread_id):
    log(f"Thread {thread_id}: Waiting for connection...")
    
    pool_semaphore.acquire()  # Block if all 3 connections are in use
    
    with log_lock:
        active_connections.append(thread_id)
        log(f"Thread {thread_id}: Got connection. Active: {list(active_connections)}")
    
    # Simulate query work
    time.sleep(random.uniform(0.1, 0.3))
    
    with log_lock:
        active_connections.remove(thread_id)
        log(f"Thread {thread_id}: Released connection. Active: {list(active_connections)}")
    
    pool_semaphore.release()  # Return connection to pool

threads = [threading.Thread(target=database_query, args=(i,)) for i in range(6)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print("\nAll queries complete.")

Notice that at any point, the active_connections list never has more than 3 entries. The semaphore enforces this invariant without any explicit counting logic in the application code.

Rate Limiter

A counting semaphore can limit the number of concurrent requests to an external service - preventing your application from overwhelming an API endpoint.

import threading

# Allow at most 5 concurrent API calls
api_limiter = threading.Semaphore(5)

def call_external_api(request):
    api_limiter.acquire()
    try:
        response = http_client.post(api_url, data=request)
        return response
    finally:
        api_limiter.release()  # Always release, even on error

Producer-Consumer with Bounded Buffer

The producer-consumer problem is the classic semaphore use case. A producer thread generates data and puts it into a shared buffer. A consumer thread takes data from the buffer and processes it. The buffer has a fixed size - the producer must wait when the buffer is full, and the consumer must wait when the buffer is empty.

This requires two semaphores:

empty - initialized to the buffer size (N). Represents the number of empty slots. The producer waits on empty before adding an item (blocks if the buffer is full). The consumer signals empty after removing an item (frees a slot).
full - initialized to 0. Represents the number of filled slots. The consumer waits on full before removing an item (blocks if the buffer is empty). The producer signals full after adding an item (adds a filled slot).

A mutex protects the buffer itself from concurrent access by multiple producers or consumers.

import threading
import time
import random

BUFFER_SIZE = 5
buffer = []
mutex = threading.Lock()
empty = threading.Semaphore(BUFFER_SIZE)  # 5 empty slots initially
full = threading.Semaphore(0)             # 0 filled slots initially

def producer(producer_id, num_items):
    for i in range(num_items):
        item = f"P{producer_id}-Item{i}"
        
        empty.acquire()          # Wait for an empty slot
        with mutex:              # Protect buffer access
            buffer.append(item)
            print(f"Produced: {item} | Buffer: {list(buffer)}")
        full.release()           # Signal that a slot is now filled
        
        time.sleep(random.uniform(0.05, 0.15))

def consumer(consumer_id, num_items):
    for i in range(num_items):
        full.acquire()           # Wait for a filled slot
        with mutex:              # Protect buffer access
            item = buffer.pop(0)
            print(f"Consumed: {item} | Buffer: {list(buffer)}")
        empty.release()          # Signal that a slot is now empty
        
        time.sleep(random.uniform(0.05, 0.2))

# 2 producers making 4 items each, 2 consumers taking 4 items each
threads = [
    threading.Thread(target=producer, args=(1, 4)),
    threading.Thread(target=producer, args=(2, 4)),
    threading.Thread(target=consumer, args=(1, 4)),
    threading.Thread(target=consumer, args=(2, 4)),
]

for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"\nFinal buffer: {buffer} (should be empty)")

This is the canonical semaphore example in OS textbooks and interviews. The two semaphores form a dual constraint: empty prevents the producer from overflowing the buffer, and full prevents the consumer from underflowing it. The mutex prevents two producers (or two consumers) from corrupting the buffer simultaneously.

graph TD
    subgraph PRODUCER["Producer Thread"]
        P1["Produce item"]
        P2["wait(empty)<br/>Block if buffer full"]
        P3["lock(mutex)"]
        P4["Add item to buffer"]
        P5["unlock(mutex)"]
        P6["signal(full)<br/>Notify consumers"]
    end
    
    subgraph BUFFER["Shared Buffer (size N)"]
        BUF["Items: [...]"]
    end
    
    subgraph CONSUMER["Consumer Thread"]
        C1["wait(full)<br/>Block if buffer empty"]
        C2["lock(mutex)"]
        C3["Remove item from buffer"]
        C4["unlock(mutex)"]
        C5["signal(empty)<br/>Notify producers"]
        C6["Process item"]
    end
    
    P1 --> P2 --> P3 --> P4 --> P5 --> P6
    C1 --> C2 --> C3 --> C4 --> C5 --> C6
    
    P4 -.->|"writes"| BUF
    BUF -.->|"reads"| C3

This diagram shows the producer-consumer workflow with semaphores. The producer thread produces an item, waits on the empty semaphore to ensure there is space in the buffer, locks the mutex, adds the item to the shared buffer, unlocks the mutex, and signals the full semaphore. The consumer thread waits on the full semaphore to ensure there is data in the buffer, locks the mutex, removes an item from the buffer, unlocks the mutex, signals the empty semaphore, and processes the item. The two semaphores coordinate the flow: empty prevents overflow and full prevents underflow.

Common Mistakes with Semaphores

Semaphores are powerful but unforgiving. Because they have no owner and no built-in error checking, mistakes are easy to make and hard to debug.

Forgetting to Signal

If a thread acquires a semaphore permit and then encounters an exception or early return without signaling, the permit is permanently lost. The semaphore count is reduced by one forever, and eventually the system runs out of permits and deadlocks.

# BROKEN - exception before signal
pool_semaphore.acquire()
result = risky_operation()   # If this throws, permit is lost
pool_semaphore.release()

# FIXED - try/finally guarantees signal
pool_semaphore.acquire()
try:
    result = risky_operation()
finally:
    pool_semaphore.release()

This is the same pattern as forgetting to unlock a mutex, and the fix is the same: use language-level guarantees (try/finally, with, defer) to ensure the signal always happens.

Incorrect Semaphore Ordering

In the producer-consumer example, the order of operations matters. If you lock the mutex before waiting on the semaphore, you can deadlock: the thread holds the mutex and sleeps on the semaphore, but the thread that needs to signal the semaphore cannot acquire the mutex.

# DEADLOCK - wrong order
mutex.acquire()         # Hold the mutex
empty.acquire()         # Sleep if buffer is full - but we're holding the mutex!
# The consumer needs the mutex to remove an item and signal(empty),
# but we're holding the mutex. Nobody can make progress.

# CORRECT - semaphore first, then mutex
empty.acquire()         # Wait for space (might sleep - but we don't hold the mutex)
mutex.acquire()         # Now lock the buffer (short duration)
# ... modify buffer ...
mutex.release()
full.release()

The rule is: always acquire semaphores before mutexes. Semaphore waits can be long (waiting for a resource to become available). Mutex waits should be short (just protecting the data access). If you hold a mutex while waiting on a semaphore, you are holding a short-term lock during a long-term wait, which is a deadlock recipe.

Signaling Too Many Times

Because any thread can signal a semaphore (unlike a mutex, where only the owner can unlock), it is possible to signal more times than you acquired. This inflates the semaphore count beyond its intended maximum, breaking the concurrency limit.

# Bug: Semaphore initialized to 3, but after erroneous extra signals,
# the count might grow to 5 - allowing 5 concurrent accesses
# to a 3-connection pool
pool = threading.Semaphore(3)

def worker():
    pool.acquire()
    try:
        use_connection()
    finally:
        pool.release()
        pool.release()   # BUG: double release! Count goes above 3

Python's threading.BoundedSemaphore prevents this - it raises a ValueError if you release more times than the initial count. Use BoundedSemaphore whenever the semaphore represents a fixed number of resources.

Semaphore Implementation at the OS Level

Understanding how the OS implements semaphores helps you reason about their performance and behavior.

At the lowest level, a semaphore's wait and signal operations are implemented using hardware atomic instructions and the kernel scheduler:

// Simplified kernel implementation of semaphore operations

typedef struct {
    int count;                    // Permit counter
    spinlock_t guard;             // Protects count and wait_queue
    queue_t wait_queue;           // Sleeping threads
} semaphore_t;

void sem_wait(semaphore_t *sem) {
    spin_lock(&sem->guard);       // Brief spin to protect internal state
    if (sem->count > 0) {
        sem->count--;             // Permit available - take it
        spin_unlock(&sem->guard);
    } else {
        enqueue(&sem->wait_queue, current_thread);
        spin_unlock(&sem->guard);
        block_current_thread();   // Put this thread to sleep
    }
}

void sem_signal(semaphore_t *sem) {
    spin_lock(&sem->guard);
    if (!queue_empty(&sem->wait_queue)) {
        thread_t *t = dequeue(&sem->wait_queue);
        wake_thread(t);           // Wake a sleeping thread
    } else {
        sem->count++;             // No waiters - increment count
    }
    spin_unlock(&sem->guard);
}

Notice that the implementation uses a spinlock internally - but only to protect the semaphore's own data structure (count and queue), which takes nanoseconds. The actual waiting (when the count is zero) uses the OS scheduler to put the thread to sleep, avoiding the CPU waste of spinning on the application-level wait.

Semaphores vs Mutexes: When to Use Which

The decision between a semaphore and a mutex is straightforward once you understand their fundamental difference:

Use a mutex when the constraint is "one at a time." A mutex is simpler, has ownership semantics (which helps with debugging), supports priority inheritance (which prevents priority inversion), and is the right tool for protecting a single shared resource.

Use a counting semaphore when the constraint is "at most N at a time." Connection pools, thread pools, rate limiters, bounded buffers - any scenario where you need to limit concurrency to a fixed number.

Use a binary semaphore (count = 1) when you need signaling between threads. One thread waits for an event, another thread signals it. This is something a mutex cannot do because the signaler is not the thread that "locked" the semaphore.

Interview: "Explain the difference between a mutex and a semaphore."

"A mutex provides mutual exclusion - only one thread can hold it at a time. It has an owner: the thread that locks it must be the one that unlocks it. A semaphore is a counter that allows up to N threads to hold permits simultaneously. It has no owner - any thread can signal it.

A binary semaphore (initialized to 1) can provide mutual exclusion like a mutex, but without ownership. The practical differences are: mutexes support priority inheritance (preventing priority inversion), mutexes can be recursive (re-lockable by the owner), and mutexes provide better debugging because the owner is tracked.

I use mutexes for protecting shared data (one writer at a time). I use counting semaphores for limiting concurrency (connection pools, rate limiters). I use binary semaphores for signaling between threads (producer-consumer coordination)."

Common follow-up: "Can you implement a mutex using semaphores, or vice versa?"

"A binary semaphore initialized to 1 behaves like a mutex for mutual exclusion, though it lacks ownership semantics. Going the other direction, you can implement a counting semaphore using a mutex and a condition variable - the mutex protects the count, and the condition variable handles the wait/signal logic. This is actually how some systems implement semaphores internally."

Exercise: Starter: Using Python's threading.Semaphore, implement a print rate limiter. Create 20 threads that each want to print a message, but only 3 should be able to print at any given moment. Use time.sleep(0.5) to simulate print time. Verify that the output shows at most 3 prints happening in each half-second window.

Intermediate: Implement the bounded-buffer producer-consumer problem from scratch (without looking at the example in this topic). Use two semaphores (empty and full) and one mutex. Create 3 producer threads and 2 consumer threads. Each producer generates 10 items. Verify that all 30 items are consumed, none are duplicated, and the buffer never exceeds its capacity.

Advanced: Implement the Readers-Writers problem using semaphores. Multiple readers can read simultaneously, but a writer needs exclusive access. Use a counting semaphore, a binary semaphore, and an integer counter to coordinate access. Implement the "writers-preferred" variant where, once a writer is waiting, no new readers are allowed to start. Test with 8 reader threads and 2 writer threads, and verify that writers are never starved.

Back to Operating Systems