Semaphores
A semaphore is an integer variable used to control access to a shared resource among multiple processes or threads, accessed only through two atomic operations. The wait operation decrements the value and blocks the caller if it would go negative, while the signal operation increments it and wakes a blocked process. Semaphores come in binary and counting forms.
A semaphore is a synchronization primitive built specifically to be simple, general-purpose, and safe to use directly, unlike hand-rolled algorithms such as Peterson's Solution, semaphores are meant to be a practical tool real software actually uses, not just a theoretical proof.
The core idea
A semaphore is an integer variable that can only ever be manipulated through two specific operations, both guaranteed by the OS to be atomic (uninterruptible, so no race condition can occur on the semaphore's own value):
wait(S)(also called P ordown): decrements the semaphore's value; if the result would be negative, the calling process blocks until another process signals.signal(S)(also called V orup): increments the semaphore's value, and if any processes are currently blocked waiting, one of them is woken up.
Two flavors of semaphore
A binary semaphore only ever holds the value 0 or 1, and is used exactly like a lock: 1 means the resource is free, 0 means it's taken, wait acquires it, signal releases it. This is functionally a mutex.
A counting semaphore can hold any non-negative integer value, and is used to manage a pool of multiple identical resources, its value represents how many units of that resource are currently available. wait is called before using a unit (decrementing the count, blocking if none are left), signal is called after releasing a unit (incrementing the count, waking a waiter if one exists).
A worked example, mutual exclusion with a binary semaphore
semaphore mutex = 1; // 1 means the resource is currently free
wait(mutex); // decrement to 0; if it were already 0, this call blocks
// --- critical section: safe, exclusive access ---
signal(mutex); // increment back to 1, waking a waiter if one exists
If Process A calls wait(mutex) first, it decrements the semaphore from 1 to 0 and proceeds into its critical section. If Process B then calls wait(mutex) while A is still inside, B's decrement would take the value to -1, which blocks B until A calls signal(mutex), incrementing it back to 0 and waking B up, which then lets B's own wait call complete and proceed.
A worked example, a counting semaphore for a resource pool
Suppose a print server has 3 identical printers available: semaphore printers = 3;. Every process that wants to print calls wait(printers) first, if 3 processes try to print at once, all three succeed (count drops from 3 to 0), and a fourth process calling wait(printers) blocks, since the count would go negative, until one of the first three finishes and calls signal(printers), incrementing the count and waking the waiting fourth process.
Where this matters in real systems
Semaphores (or very closely related primitives, mutexes and condition variables) are built directly into every mainstream OS and programming language's concurrency support: POSIX semaphores on Linux, Windows semaphore objects, Java's Semaphore class, Python's threading.Semaphore. Connection pools (a fixed number of available database connections shared across many requests) are a real, extremely common use of a counting semaphore in production backend systems: the semaphore's count is exactly the number of free connections, and a request that can't get one waits until another request finishes and releases its connection back to the pool.
What interviewers actually ask about semaphores
- "What is a semaphore, and what two operations does it support?" An integer variable manipulated only through atomic
wait(decrement, block if negative) andsignal(increment, wake a waiter) operations, used to control access to shared resources. - "What's the difference between a binary and a counting semaphore?" A binary semaphore only holds 0 or 1 and acts like a lock; a counting semaphore holds any non-negative value and manages a pool of multiple identical resources.
- "Why must
waitandsignalbe atomic?" Because if two processes could interleave in the middle of incrementing or decrementing the semaphore's own value, the semaphore itself would be subject to the exact race condition it's meant to prevent on other shared data. - "Give a real, practical use of a counting semaphore." A database connection pool, where the semaphore's count tracks how many connections are currently free, and requests block via
waitwhen none are available.
Key takeaways
- A semaphore is an integer manipulated only through atomic
wait(decrement, block if negative) andsignal(increment, wake a waiter) operations. - Binary semaphores act like a simple lock (0 or 1); counting semaphores manage a pool of multiple identical resources.
- The atomicity of
wait/signalthemselves is essential, otherwise the semaphore would be vulnerable to the same race conditions it's meant to prevent. - Real systems use semaphores directly for things like connection pools, and every mainstream OS/language provides them as a built-in primitive.
More in Process Synchronization
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
What is a semaphore, and what two operations does it support?
An integer variable manipulated only through atomic `wait` (decrement, block if negative) and `signal` (increment, wake a waiter) operations, used to control access to shared resources.
What's the difference between a binary and a counting semaphore?
A binary semaphore only holds 0 or 1 and acts like a lock; a counting semaphore holds any non-negative value and manages a pool of multiple identical resources.
Why must `wait` and `signal` be atomic?
Because if two processes could interleave in the middle of incrementing or decrementing the semaphore's own value, the semaphore itself would be subject to the exact race condition it's meant to prevent on other shared data.
Give a real, practical use of a counting semaphore.
A database connection pool, where the semaphore's count tracks how many connections are currently free, and requests block via `wait` when none are available.