Skip to content

Engineering

Semaphores explained: the count is the contract

Locks, caps and signals are one primitive with different starting counts. This article covers how semaphore code fails: deadlock, laps and a wrong starting count.

Computing America. Applications, integrations, data analysis and AI/ML engineering.

Send the function
5 min readComputing America
Two railway semaphore signal arms at dusk, one raised and one lowered.

In short

  • A job that ran twice is often a retry, not a race. A semaphore won't fix a retry; an idempotency key will.
  • Somebody has to signal before they wait. If both sides wait first, each is waiting for a signal the other sends only after it stops waiting.
  • A barrier built from the obvious pieces is correct once and broken on reuse, because a fast participant can lap the slow ones. The two-phase turnstile is the standard fix.
  • Implementing a pattern against a forgiving API and again against POSIX exposes what you only thought you understood, because the strict version hangs on its first run, or admits too many if the test counts threads inside.
  • Semaphores are rarely the right production tool, but channels and bounded queues guard a count and a condition variable guards a condition, so the same debugging steps apply to all three.

Downey’s Little Book of Semaphores (opens in a new tab) builds nearly every classic synchronization pattern from one integer with a different starting value: 1 makes a lock, N a cap, 0 a signal. The count is the contract: when a concurrency bug involves a counting primitive in the code, the count is where to look first.

Production concurrency bugs don't present as concurrency bugs. They present as a job that ran twice, a report with a number you can't reproduce, a queue that stalls under load once a week, or an integration that duplicates a record when the network is slow. Duplicates often come from retries, not races (step 1 below). Otherwise, finding the cause means reading someone else's code under a deadline and deciding whether one specific interleaving is possible.

One integer, three contracts

A semaphore has two operations. One decrements the integer and blocks while it would go negative. The other increments it and wakes a waiter if any are blocked. The starting value sets the policy.

Initial countWhat you haveWhat it is in production
1Mutual exclusion: exactly one participant inside at a time.A lock, under whatever name your runtime gives it.
NBounded concurrency: at most N inside at once.A connection pool, a concurrency limiter, a license count, a worker cap.
0A signal: whoever arrives first waits until somebody else has done the thing.A latch, a completion handle, one half of a rendezvous.
The same two operations give a lock, a cap or a signal; only the starting count differs.

Interactive · Concurrency

The classical patterns, with threads crossing the line

Live · Semaphore visualizer
Same primitive, six protocols. Switch modes to watch the same acquire / release pair become a mutex, a multiplex, a barrier, a bounded buffer, or, wired wrong, a deadlock.
critical section · capacity 3wait queuepermits: 3 / 3queued: 0completed: 0

Multiplex. Same primitive, initialized to N. Up to N threads in the section at once; arrivals beyond N block. Connection pools, rate limits, "at most K of these can run in parallel."

What this isRendezvous, mutex, bounded concurrency, a reusable barrier, a bounded buffer and a deliberate deadlock, each driven by the same counter-and-queue primitive the implementations use. The primitive never changes; what changes is the protocol built on it, which is the whole argument of the write-up.

Both sides waiting first is the deadlock

One side waiting first is fine (B does it in the listing below). If both do, neither signal is ever sent. With the two halves of a pattern a hundred lines apart in different files, that's hard to see, but the shape is recognizable.

Fig. 1

Drone A's first step: A acquires or A releases

Drone B's first step: B releases or B acquires

A acquires · B releases

Runs

  • A waits for B's release
  • B releases first, so it arrives

A acquires · B acquires

Deadlock

  • A waits for B's release
  • B waits for A's release
  • Each release sits behind a wait

A releases · B releases

Runs

  • Both release first
  • Each then finds the other's signal

A releases · B acquires

Runs: the listing below

  • A releases first
  • B waits, then releases

The rendezvous deadlocks in one of its four orderings: only when both drones acquire before they release does neither signal ever get sent.

SourceThe rendezvous listing in this article, with each function's first step moved before or after its release; four orderings, none measured.

python/rendezvous.pyPython
aArrived = Semaphore(0)bArrived = Semaphore(0) def A():    print("Drone A: Picked up the package.")    bArrived.release()       # tell B I’m here    aArrived.acquire()       # wait for B def B():    bArrived.acquire()       # wait for A    print("Drone B: Arrived at the rendezvous point.")    aArrived.release()       # tell A I’m here
Two counts starting at zero, four operations, and the entire ordering guarantee is the order of the two on lines 6 and 7.

The barrier is correct once

A barrier holds N participants until all N have arrived, then releases them together. Built from a counter, a lock and a semaphore, the direct version works on first use and breaks on the second, because a fast participant can loop around and re-enter before the slow ones have left.

The standard fix is a two-phase turnstile: one gate to leave the previous round and a second to enter the next, so no participant can lap another. A variant pre-loads the first turnstile and drops one gate.

barriers/reusable.pyPython
mutex      = Semaphore(1)turnstile  = Semaphore(0)   # phase 1: shut until the last party arrivesturnstile2 = Semaphore(1)   # phase 2: open, so the barrier can be re-entered with counted(mutex, +1) as n:    if n == PARTIES:        turnstile2.acquire()    # shut the exit before opening the entrance        turnstile.release()
Every initial count on the first three lines is a policy decision. Start turnstile2 at 0 instead of 1 and the last party blocks on line 7 while holding the mutex, so the barrier deadlocks the first time it is used. Reading concurrent code accurately is the skill; the primitives are incidental.

Implement it twice

We built the skill of reading these by implementing every pattern in the book twice, in Python and against the POSIX interface in C++. A forgiving semaphore reads like pseudocode: no error path, no teardown. The POSIX version demands explicit initialization, one post per permit, destruction only after every waiter is released, and a return code checked on every call. The compiler checks none of it, and a count initialized the wrong way round builds cleanly. Only the run catches it: a count too low hangs, and a count too high runs silently unless the test records how many threads are inside.

cpp/multiplex.cppC++
sem_t multiplex; void count() {    sem_wait(&multiplex);    sem_post(&multiplex);   // critical section elided; the pair is the point} int main() {    sem_init(&multiplex, 0, 3);   // capacity 3: the policy, stated once    // ... spawn / join 20 threads, all calling count() ...    sem_destroy(&multiplex);}
The third argument on line 9 is the only line in the file that decides how much concurrency this program permits.

Handoff explains condition variables

In the exclusive queue pattern, where participants pair up before proceeding, the elegant implementation deliberately doesn't release the mutex on handoff. The partner inherits it. That looks like it breaks every rule about balanced acquisition and release. It's what a Hoare-style monitor does when it signals: the lock goes straight to the thread being woken.

The condition variables you have (POSIX, Java, C++) are Mesa-style and do the opposite. The signaler keeps going and the woken thread races to re-acquire the mutex, so you wait in a loop on the predicate. By the time the woken thread has the mutex back, the condition it was woken for may be gone.

What to do with a job that ran twice

In production we reach for a channel, a bounded queue, a mutex with a condition variable or a task runtime, because they're clearer at the call site and easier to review. Channels and bounded queues guard a count of items or free slots, and a condition variable guards a condition its waiters re-check. Each makes waiters block, so when a bug shows up in any of them, work backward to that count or condition:

  1. 1.Rule out a retry first. If the same request arrived twice, the fix is an idempotency key checked before the work, not a lock. An idempotent operation gives the same result when applied twice.
  2. 2.List each shared resource and write down what its count should be, 1, N or 0, or the condition its waiters need.
  3. 3.Find every place that waits on it and every place that signals it.
  4. 4.Ask whether any path out of a wait skips its matching signal, and whether two waiters can each be waiting on the other.
  5. 5.Check the running process. If threads hang, dump their stacks and see what each is parked on: jstack (opens in a new tab) for a JVM, py-spy dump --pid (opens in a new tab) for Python. If results are wrong without a hang, run the code under ThreadSanitizer (opens in a new tab) (-fsanitize=thread for C and C++) or Go's -race flag, which report data races.

Sources

  1. 1.The Little Book of Semaphores (opens in a new tab), Allen B. Downey, Green Tea Press
  2. 2.The jstack command, JDK 21 Reference (opens in a new tab), Oracle
  3. 3.py-spy: sampling profiler for Python programs (opens in a new tab), Ben Frederickson, GitHub
  4. 4.ThreadSanitizer (opens in a new tab), LLVM Project

Next step

Send us the code that only fails under load.

The function that is correct in every test and wrong in production. We will tell you what the count was supposed to be.

Reply
A person replies, not a sequence: within one business day, from someone who would be on the engagement.

Packages

Start with a package

Four packages, each with its price on the page. Pick one and buy it online.

Billing