Free lesson · Concurrency Interview Mastery

Exercise: Semaphores

Medium6 min readconcurrencymultithreadinginterview-prep

The mutex exercise was about exclusion. This one is about the two things semaphores do that mutexes can't: limit concurrency to N and signal across threads. The three parts build from a simple concurrency limiter, to cross-thread signaling (where the semaphore's lack of ownership is the whole point), to the bounded-buffer classic. As before, reason each part through before opening the solution - the goal is to internalize which semaphore role solves which problem.

Important: For each part, decide first: is this a limiting concurrency problem (init to N, same thread acquires and releases) or a signaling problem (init to 0, one thread waits, a different thread releases)? Naming the role before writing code is the skill this exercise builds - it's the diagnosis that tells you how to initialize the semaphore and who acquires versus releases.

Part 1 - Limit concurrency to N

You have a service that calls a fragile downstream API. The API falls over if more than 3 requests hit it at once, but you have hundreds of threads that may call it. Throttle so that at most 3 threads call the API concurrently; the rest wait their turn.

function callApi(request):
    // TODO: ensure at most 3 threads are inside fetch() at once
    return fetch(request)

Your task: Add a semaphore so no more than 3 threads run fetch simultaneously. What do you initialize it to, who acquires, who releases, and where must the release go to survive an exception?

This is a limiting concurrency problem: init the semaphore to the limit (3), the same thread acquires before fetch and releases after. The release must be in a finally - if fetch throws and you skip the release, that permit is leaked forever and eventually all 3 leak and everything blocks. </details>

Part 2 - Signal across threads

A worker thread must not start processing until a loader thread has finished loading configuration. You can't use a mutex for this. Make the worker wait until the loader signals "config is ready."

// Loader thread:
function load():
    loadConfig()
    // TODO: signal that config is ready

// Worker thread:
function work():
    // TODO: wait until config is ready
    processWithConfig()

Your task: Use a semaphore so the worker blocks until the loader signals. Then answer: why can't a mutex do this job? This is the question that tests whether you understand ownership.

This is a signaling problem: init the semaphore to 0 (no permits). The worker acquires (blocking immediately, since count is 0); the loader releases when done, unblocking the worker. For the mutex question: a mutex is owned - only the thread that locks it can unlock it - so you can't have the worker "lock" and the loader "unlock." </details>

Part 3 - The bounded buffer

Implement a fixed-capacity buffer (size N) shared by producers and consumers. Producers block when it's full; consumers block when it's empty. Use semaphores.

buffer = fixed-size queue of capacity N

function produce(item):
    // TODO: block if full, then add item
    buffer.add(item)

function consume():
    // TODO: block if empty, then remove item
    return buffer.remove()

Your task: Solve it with two counting semaphores and a mutex. Then answer two things: (a) Why do you need two separate semaphores rather than one? (b) What is the correct ordering of acquiring the semaphore and the mutex, and what breaks if you reverse it?

You need to count two different things independently: how many empty slots remain (producers wait on this) and how many filled slots exist (consumers wait on this). One counter can't track both. The mutex separately protects the buffer structure from concurrent add/remove. </details>

Acquire the counting semaphore before the mutex. If a producer locks the mutex and then blocks waiting for an empty slot, it holds the mutex while blocked - and a consumer needs that mutex to remove an item and free a slot. Deadlock. </details>

Solution

Part 1 - Concurrency limiter

limiter = new Semaphore(3)        // 3 permits = at most 3 concurrent

function callApi(request):
    limiter.acquire()              // wait for a permit
    try:
        return fetch(request)
    finally:
        limiter.release()          // ALWAYS return the permit, even on exception

Initialize to the limit (3). Each thread acquires a permit before fetch and releases after; when all 3 permits are out, further threads block on acquire until one frees. The same thread acquires and releases - this is the limiting-concurrency role. The finally is non-negotiable: a leaked permit (acquired but never released because of an exception) permanently reduces capacity, and leaking all 3 deadlocks every future caller. This is exactly how a real concurrency limiter or fixed-size connection pool is built.

Part 2 - Cross-thread signaling

ready = new Semaphore(0)           // start with NO permits

function load():                   // loader
    loadConfig()
    ready.release()                // signal: count 0 -> 1

function work():                   // worker
    ready.acquire()                // blocks (count is 0) until loader releases
    processWithConfig()

Initialize to 0. The worker's acquire blocks immediately because there are no permits; the loader's release raises the count, completing the worker's acquire and letting it proceed. This is the signaling role - and notice the asymmetry: a different thread releases than the one that acquires.

Why a mutex can't do this: a mutex is owned - only the thread that locked it may unlock it. To signal with a mutex, the worker would "lock" and the loader would "unlock," but the loader doesn't own the lock, so that's illegal (and most mutex implementations would error or behave undefined). The semaphore's lack of ownership is precisely what makes cross-thread signaling possible. This is the concrete payoff of the ownership distinction from the lesson: ownership is why mutexes protect critical sections and semaphores signal between threads.

Part 3 - Bounded buffer

emptySlots = new Semaphore(N)      // empty slots available; starts full (= N)
fullSlots  = new Semaphore(0)      // filled slots available; starts empty
mutex      = new Mutex()            // protects the buffer structure

function produce(item):
    emptySlots.acquire()           // wait for an empty slot (block if full)
    mutex.lock()
        buffer.add(item)
    mutex.unlock()
    fullSlots.release()            // one more item is now available

function consume():
    fullSlots.acquire()            // wait for an item (block if empty)
    mutex.lock()
        item = buffer.remove()
    mutex.unlock()
    emptySlots.release()           // one more empty slot is now free
    return item

(a) Why two semaphores? Because producers and consumers wait on different conditions that must be counted independently. Producers wait for empty slots; consumers wait for full slots. These are two separate counts - a single semaphore can't simultaneously represent "how many empty slots" and "how many items." emptySlots starts at N (all empty) and fullSlots at 0 (nothing yet); each produce moves one slot from empty to full, each consume moves one back. The mutex is a third, separate concern: it protects the buffer data structure itself from two threads modifying it at once, which the semaphores don't do - semaphores count and block, the mutex excludes.

(b) Ordering. Acquire the counting semaphore before the mutex. The reverse - lock the mutex, then block on a full emptySlots - would leave a producer holding the mutex while waiting for a slot, but the only way a slot frees is a consumer removing an item, which needs the mutex the producer is holding. Circular wait, deadlock. Acquiring the semaphore first means a blocked producer holds no lock, so consumers keep making progress and eventually free a slot. The rule generalizes: never block on one primitive while holding another.

Common mistakes

Warning: Frequent errors: (1) Releasing outside finally in Part 1 - an exception leaks a permit, and enough leaks deadlock the limiter. (2) Reaching for a mutex in Part 2 - the instinct to use a lock for "wait until ready" fails because of ownership; signaling needs the unowned semaphore. (3) One semaphore for the bounded buffer - you genuinely need two, one per waitable condition; trying to do it with one leads to incorrect blocking. (4) Locking the mutex before acquiring the semaphore in Part 3 - the deadlock from holding a lock while blocked. (5) Signal/wait imbalance - releasing more permits than acquired silently lets too many threads through later; the counter trusts you to keep it balanced.

Why this exercise matters for interviews

Interview: These three parts map to the three things interviewers actually ask about semaphores: building a concurrency limiter / connection pool (Part 1), explaining why semaphores and not mutexes handle cross-thread signaling (Part 2 - the ownership question, asked constantly), and solving bounded-buffer producer-consumer (Part 3 - a top-5 concurrency interview problem). If you can state which role each problem needs (limiting vs signaling), justify the two-semaphores-plus-mutex structure, and explain the acquire-semaphore-before-mutex ordering, you've shown command of semaphores beyond "it's a counter." Rehearse Part 2's "why not a mutex" answer especially - ownership is the single most common semaphore question, and a crisp answer signals real depth.

Back to Concurrency Interview Mastery