Semaphores

Drive up to a busy multi-storey car park and the first thing you meet is a big lit sign: SPACES: 42. Every time a car noses in, the number ticks down — 41, 40, 39. Every time a car leaves, it ticks back up. And the moment it reaches 0, the barrier stays down: the next driver simply waits at the entrance until someone drives out and the counter climbs to 1 again.

That sign is a semaphore, exactly. It is a single integer — a count of how many identical things (parking spaces) are still available — with two rules: taking one makes the count go down, returning one makes it go up, and you cannot take one when the count is already zero. Swap "parking space" for "database connection", "buffer slot" or "download permit" and you have one of the most useful synchronisation tools in all of concurrent programming.

A semaphore is the big brother of the mutex. A mutex lets one thread through; a semaphore lets N through, counts them, and — as we'll see — can even be used by one thread to send a signal to another. This page is about that one idea: a semaphore is a counter of permits, and everything it can do falls out of that.

Two operations: wait() and signal()

A semaphore holds a non-negative integer, the number of available permits, and offers exactly two operations. They travel under many names — pick whichever your language uses, they are the same two moves:

In our car park, wait() is a car taking a space (SPACES 42 → 41) and signal() is a car leaving (41 → 42). Take one when the sign reads 0 and you must queue at the barrier — that is wait() blocking. The count is never allowed to drop below zero; that invariant is the whole guarantee.

A neat way to read the count when it matters: if it is positive, it is the number of permits still free; conceptually, if it were allowed to go negative, the magnitude would be the number of threads currently queued waiting. A real implementation keeps the count at zero and holds a wait queue instead, but the accounting is the same.

Counting vs binary semaphores

The initial value you choose is what gives a semaphore its character.

A counting semaphore starts at some N > 1 and guards a pool of N identical resources. Set it to the number of things you have, and it hands out exactly that many permits before making the next thread wait. Classic uses:

A binary semaphore starts at 1 and can only ever be 0 or 1 — one permit, held or free. That makes it behave a lot like a mutex: the first wait() takes the single permit (count 1 → 0), and anyone else calling wait() blocks until a signal() returns it (0 → 1). Initialise to 1 for mutual exclusion; initialise to N to admit N at once.

Because they are not the same, and the difference is ownership (the next card is all about it). A mutex remembers which thread locked it and insists that same thread unlock it — great for catching bugs and for reentrancy. A binary semaphore has no owner: any thread may signal() it, even one that never called wait(). So use a binary semaphore when you actually want that freedom — chiefly, to signal an event from one thread to another — and a mutex when you want a plain, owned lock. Reaching for a semaphore where a mutex belongs is a well-worn way to write an ownerless bug.

The killer feature: a semaphore has no owner

Here is the property that makes semaphores genuinely more powerful than mutexes, not just "a mutex that counts". A mutex has an owner: the thread that locks it is the only one allowed to unlock it. A semaphore has no owner at all. One thread can call wait() and a completely different thread can call signal().

That sounds like a small technicality. It is the difference between "protecting data" and "coordinating threads". Because signal() can come from another thread, a semaphore can signal an event across threads: thread A blocks on wait() until thread B reaches some milestone and calls signal(). Start such a semaphore at 0 — no permits — so the waiter genuinely sleeps until the event fires:

// A semaphore used as an EVENT / signal, initialised to 0 (no permits yet). const ready = new Semaphore(0); // Thread A (consumer of the event) ready.wait(); // blocks here — there are no permits yet useTheThing(); // runs only after B signals // Thread B (producer of the event), some time later, on ANOTHER thread prepareTheThing(); ready.signal(); // count 0 -> 1, wakes A. B never called wait() — and that's fine.

Try that with a mutex and the runtime will (rightly) complain that B is unlocking a lock it never locked. The semaphore is happy: it is just a counter, and signal() from anyone is a legal move. This ownerless signalling is exactly what powers the headline application below.

The semaphore was invented by the Dutch computer scientist Edsger Dijkstra around 1962–63. He named the two operations P and V after Dutch words — the usual story is P for proberen ("to try") and V for verhogen ("to increase" or "raise"). English textbooks later softened these to the friendlier wait() and signal(), or down() and up(), but you will still meet P and V constantly in operating-systems papers and exam questions — now you know they are just take-a-permit and give-a-permit-back.

The headline application: producer–consumer (bounded buffer)

Picture a fixed-size shelf between a baker (the producer) and a customer (the consumer). The baker puts loaves on the shelf; the customer takes them off. Two things can go wrong, and both are about waiting for the right moment:

This is the bounded-buffer problem, and it is the textbook reason semaphores exist. The classic solution uses two counting semaphores plus one mutex:

The beautiful part is how empty and full pass permits back and forth. Every insert does wait(empty) then signal(full): it spends a free slot and produces an item. Every remove does wait(full) then signal(empty): it spends an item and frees a slot. The producer's signal(full) is precisely the ownerless cross-thread signal that wakes the sleeping consumer — and vice versa.

// Shared: buffer of capacity N, plus three semaphores. const empty = new Semaphore(N); // free slots, starts full of permits const full = new Semaphore(0); // items ready, starts empty const mutex = new Semaphore(1); // binary: guards the buffer itself function producer(): void { while (true) { const item = produceItem(); empty.wait(); // take a free slot — BLOCKS if the buffer is full mutex.wait(); // lock the buffer insert(item); // critical section: touch shared pointers mutex.signal(); // unlock the buffer full.signal(); // announce a new item — wakes a waiting consumer } } function consumer(): void { while (true) { full.wait(); // take an item — BLOCKS if the buffer is empty mutex.wait(); // lock the buffer const item = remove(); mutex.signal(); // unlock the buffer empty.signal(); // announce a free slot — wakes a waiting producer consumeItem(item); } }

Follow the diagram below: an item is inserted (a free slot is spent, an item appears — empty down, full up) and removed (an item is spent, a slot frees — full down, empty up). Watch what happens when the producer runs ahead and the buffer fills: empty hits 0 and the next wait(empty) puts the producer to sleep until the consumer frees a slot.

In the producer, the resource semaphore empty is acquired before the mutex, and released in mirror order. Swap them at your peril. If the producer does mutex.wait() first and then empty.wait(), picture a full buffer: the producer grabs the mutex, then blocks forever on empty — while still holding the mutex. The consumer needs that same mutex to remove an item and free a slot, so it can never run, so empty is never signalled. Nothing races; the whole thing simply deadlocks. Rule of thumb: acquire the counting semaphore that might block for a long time before the short-lived mutex, and release in the reverse order.

Run it yourself: the producer blocks when the buffer is full

The sandbox runs on a single thread, so it can't truly sleep a producer — which is perfect, because it lets us script the exact schedule and watch the invariant do its job every time. Below, a tiny Semaphore class (just a count, with a wait() that reports whether it could proceed) drives a bounded buffer of capacity 3. We run a schedule that deliberately over-produces so you can see empty hit 0 and the fourth produce refuse to proceed — then a consume frees a slot and the producer gets in. Press Run ▶:

// A scripted semaphore: a count, plus a wait() that tells us whether a // permit was available. On a real thread, "no permit" would SLEEP the // caller; here we just report it so we can watch the buffer block. class Semaphore { constructor(private count: number, public name: string) {} // returns true if a permit was taken, false if the caller would BLOCK wait(): boolean { if (this.count > 0) { this.count--; return true; } return false; // count is 0 -> would go negative -> block } signal(): void { this.count++; } // return a permit get value(): number { return this.count; } } const CAP = 3; const buffer: number[] = []; const empty = new Semaphore(CAP, "empty"); // free slots: 3 permits const full = new Semaphore(0, "full"); // items ready: 0 permits let nextItem = 1; function show(msg: string): void { const cells: string[] = []; for (let i = 0; i < CAP; i++) { cells.push(i < buffer.length ? String(buffer[i]) : "_"); } console.log(msg + " buffer=[" + cells.join(" ") + "] empty=" + empty.value + " full=" + full.value); } function produce(): void { const item = nextItem; if (!empty.wait()) { // no free slot console.log("produce(" + item + "): empty=0 -> PRODUCER BLOCKS (buffer full)"); return; // a real thread sleeps here } buffer.push(item); // (mutex around this on a real thread) nextItem++; full.signal(); // wake a waiting consumer show("produce(" + item + "):"); } function consume(): void { if (!full.wait()) { // no item console.log("consume(): full=0 -> CONSUMER BLOCKS (buffer empty)"); return; } const item = buffer.shift(); empty.signal(); // wake a waiting producer show("consume(" + item + "):"); } // Over-produce on purpose: fill all 3 slots, try a 4th (blocks), // then consume one (frees a slot) and retry the producer (now succeeds). console.log("start: buffer=[_ _ _] empty=" + empty.value + " full=" + full.value); produce(); // 1 produce(); // 2 produce(); // 3 -> buffer now full, empty = 0 produce(); // 4 -> BLOCKS consume(); // -> frees a slot, empty back to 1 produce(); // -> the producer gets in

Notice that the count never goes negative and the buffer never overflows: empty falling to 0 is exactly the signal that stops the producer, and full falling to 0 is what would stop the consumer. The two semaphores are doing all the coordination — the producer and consumer never have to check the buffer's length themselves.

Because anyone may signal(), a semaphore has no way to notice that you handed back a permit you never took. Call signal(empty) one time too many — a stray extra release, a double-free, an off-by-one in a loop — and you have quietly invented a slot that doesn't exist. Now two producers can both pass wait(empty) for the same physical space, and they overwrite each other's item: the very corruption the buffer was meant to prevent, with no crash and no error message. A mutex would have caught "you unlocked something you didn't lock"; a semaphore trusts you completely. Signal exactly once per successful wait, and treat the count as a sacred invariant.