From a lock to a counter you can count with
In the last guide you built a mutex lock on top of a hardware atomic instruction, and you saw the difference between a spinlock that burns CPU spinning and a blocking lock that puts the waiter to sleep. A lock answers exactly one question: is this one thing free or taken? That is enough to protect a critical section, but a lot of real coordination needs a slightly richer answer. How many identical printers are free right now? Has the producer put anything in the buffer yet for the consumer to take? The semaphore, invented by Edsger Dijkstra, is the clean generalization that answers those questions too — and it does it with a single integer.
Picture the tray of buzzers at a busy restaurant. There are, say, three buzzers on the tray. When a party arrives they take one buzzer and walk off to wait; when none are left, the next party simply has to wait by the desk until a buzzer comes back. A returning party drops their buzzer on the tray, and if anyone is waiting, the host can hand it straight over. The tray never tells you who has which buzzer — it only ever cares about the count of buzzers available. A semaphore is exactly that tray: an integer that can never go below zero, touched only through two operations.
Those two operations are wait and signal (Dijkstra called them P and V, from Dutch words, and you will still see those letters in books). wait(S) is asking for a buzzer: it tries to take one, which decreases the count by one; if the count is already zero there is nothing to take, so the caller must wait. signal(S) is returning a buzzer: it gives one back, increasing the count by one, and if someone was waiting, it wakes one of them. The crucial promise, inherited straight from the hardware work of the previous guide, is that each of these two operations happens atomically — indivisibly, with no other thread able to slip in halfway. Without that promise the count itself would suffer the very race condition this whole rung began with.
Two flavors: binary and counting
The single difference that splits semaphores into two kinds is just how high the count is allowed to start. A binary semaphore starts at 1 and so only ever sits at 0 or 1 — a tray with exactly one buzzer. That is, in effect, a mutex lock: wait(S) is locking, signal(S) is unlocking, and only one thread can be inside the critical section at a time. A counting semaphore starts at some N greater than one — a tray with N buzzers — and lets up to N threads through at once before the (N+1)th must wait. The mechanism is identical; only the starting number changes.
When does the counting flavor earn its keep? Whenever you have a pool of several identical, interchangeable resources. Suppose a print server owns three real printers. Initialize the semaphore to 3, make every job do wait(S) before printing and signal(S) after, and the count does the bookkeeping for free: the first three jobs each pull the count down (3, 2, 1) and print in parallel, the fourth finds it at 0 and waits, and the instant any job finishes and calls signal(S) the count ticks back up and the waiting job is released onto the freed printer. You never wrote any if-statements about who-gets-which; the counter and its two atomic operations carried the whole logic.
wait(S): signal(S):
S.count = S.count - 1 S.count = S.count + 1
if S.count < 0: if S.count <= 0:
block this thread wake one blocked thread
(add to S's wait queue) (remove it from S's queue)
(each box runs atomically -- no other thread interleaves inside it)Spin or sleep? Two honest implementations
There are two ways to make a thread "wait" when the count hits zero, and they are exactly the spinlock-versus-blocking trade-off you already met, now applied to the semaphore. The simple version uses busy waiting: a thread that cannot proceed sits in a tight loop checking the count over and over, like a person standing at the desk repeatedly asking "any buzzer yet? any buzzer yet?" This wastes a CPU core doing nothing useful, and is only tolerable when the wait is expected to be extremely short — a few instructions — because then the cost of going to sleep would be larger than the wait itself.
The grown-up version is blocking. Instead of spinning, a thread that cannot proceed takes itself off the CPU entirely: it changes its own state to waiting, joins a queue hanging off the semaphore, and asks the scheduler to run something else. This is why the count in the sketch above is allowed to go negative — a count of -2 means the tray is empty and two threads are asleep in the queue behind it. Later, signal(S) does the reverse: it bumps the count and, if the count is still zero or below, picks one sleeper from the queue and moves it back to the ready queue so the scheduler can run it. No CPU is burned while waiting; the price is the small cost of the two context switches (out to sleep, back to wake).
Counting as a signal: the producer and the consumer
So far the semaphore has guarded access. Its other, equally important job is signaling: one thread telling another that an event has happened. The classic stage for this is the producer-consumer problem. One or more producer threads put items into a shared, fixed-size buffer; one or more consumer threads take items out. Two things can go wrong by waiting: a producer should pause when the buffer is full (no empty slot to fill), and a consumer should pause when the buffer is empty (no item to take). Notice these are two different counts, so we use two separate counting semaphores.
Let empty start at N (the buffer holds N slots, all empty at first) and full start at 0 (no items yet). A producer does wait(empty) to claim a free slot — which decreases the empty count and blocks if there are none — then puts its item in, then does signal(full) to announce one more item is ready, which can wake a sleeping consumer. A consumer mirrors it exactly: wait(full) to claim an item (blocking on an empty buffer), take it out, then signal(empty) to announce a slot just freed up, which can wake a sleeping producer. The two counts breathe in and out against each other, and a thread that would otherwise spin uselessly is simply put to sleep until the matching event arrives.
Honest limits: a sharp tool that does not check itself
The semaphore is powerful precisely because it is so unstructured — and that is also its danger. It protects shared data only if every single thread agrees to call wait before touching the data and signal after, every time. The compiler does not enforce this; the semaphore has no idea which variables it is supposed to be guarding. One thread that reads the shared data without ever calling wait sails right past the guard and brings the race condition back, and the bug will be intermittent and maddening to find. A semaphore is a convention everyone must honor, not a wall that stops trespassers.
The mistakes are easy to make and easy to picture. Forget the matching signal (or take an early return that skips it) and the count never recovers — a buzzer that left and never came back — so sooner or later everyone waiting is stuck forever. Swap the two calls by accident, doing signal then wait, and you can let two threads into a one-at-a-time critical section, quietly breaking mutual exclusion with no error message at all. Two threads each holding one semaphore and each waiting for the other's is, again, a textbook deadlock. None of these raises an alarm; the program simply hangs or corrupts data.
There is one more trap that has nothing to do with mistakes in your code. Suppose a low-priority thread holds a semaphore that a high-priority thread now needs. The high-priority thread blocks, politely waiting — but a steady stream of medium-priority threads keeps preempting the low-priority holder, so it never gets the CPU to finish and call signal. The result is priority inversion: a high-priority thread effectively stalled by lower-priority ones, sometimes for a dangerously long time. This is not a toy concern. A famous case nearly doomed NASA's Mars Pathfinder mission in 1997, which kept resetting itself until engineers diagnosed exactly this and enabled the standard fix, priority inheritance — temporarily lending the holder the waiter's high priority so it can finish and release the semaphore fast.
So the semaphore is a beautifully general primitive: one integer, two atomic operations, and from those you can build a mutex, a resource counter, and an event signal. But its very generality means the correctness lives in your discipline, not in the tool. That discomfort is exactly why language designers wrapped these ideas in something safer and more structured — the condition variable and the monitor — which is where the final guide of this rung takes you next.