Semaphore
A counter with wait/signal. Mutexes are semaphores of 1; producer-consumer uses more.
Level: intermediate
What is it?
A semaphore is a synchronization primitive with an integer state and atomic wait/decrement and signal/increment operations. A counting semaphore represents a number of available units; a binary semaphore has two logical states but does not necessarily have the same ownership rules as a mutex.
Why does it matter?
Semaphores coordinate both access to a limited number of resources and ordering between threads. Their flexibility also makes them easy to misuse: a missing signal can block progress, and an extra signal can break the intended count.
Mental model
Treat the semaphore value as permits. A successful wait consumes a permit; signal returns one. A thread sleeps when no permit is available rather than repeatedly checking in a tight loop.
How it works
- A counting semaphore initialized to N can represent N interchangeable resources.
- A binary semaphore can coordinate a one-at-a-time condition, but ownership semantics differ from an owner-tracking mutex.
- Producer-consumer designs often use an empty-slot count and a filled-slot count around a bounded buffer.
- Wait and signal operations must be atomic with respect to the semaphore state.
- Semaphore signals do not automatically protect every data structure access; the surrounding protocol must establish the required ordering.
Steps
- Initialize emptySlots to buffer capacity and fullSlots to zero.
- A producer waits on emptySlots, inserts an item under the buffer's protection, then signals fullSlots.
- A consumer waits on fullSlots, removes an item, then signals emptySlots.
- Check every control path to ensure each consumed permit is eventually handled as intended.
Real-world usage
- Implementing bounded producer-consumer queues.
- Limiting concurrent access to a fixed-size connection pool.
- Coordinating state transitions between threads and processes.
Common mistakes
- Signaling before the protected state is ready when the protocol requires the reverse order.
- Using a counting semaphore where a mutex's ownership semantics are needed.
- Failing to release a permit on an error path, causing eventual starvation.
Interview questions
What is the difference between binary and counting semaphores?
A binary semaphore has two logical states; a counting semaphore tracks multiple available permits or resource instances.
How do semaphores help a bounded buffer?
One count tracks empty slots and another tracks filled slots, blocking producers or consumers when their required condition is not available.