Mutex vs semaphore: interview questions and how to answer them

What it actually is

The textbook answer is that a mutex allows one holder and a semaphore allows N, and a binary semaphore is therefore a mutex. That answer is wrong in the way that matters. The distinction is ownership: a mutex records which thread holds it, so it can detect reentrance, refuse release by a non-owner, and participate in priority inheritance. A semaphore records only a count, so any thread can release a permit it never acquired.

That single difference produces every practical consequence. A mutex can be recursive, because it knows the acquiring thread is already the holder. A semaphore cannot, because it has nothing to compare against — a second acquire from the same thread simply takes a second permit, and if only one exists, that thread deadlocks against itself. Conversely, a semaphore can be used for signalling between threads, where one thread releases what another acquires, which a mutex forbids.

So the choice is driven by the question you are answering. "Only one thread may be inside this section" is mutual exclusion — use a mutex or lock. "At most N of these operations may be in flight" is resource counting — use a counting semaphore. "Wake a waiter when work is available" is signalling — use a semaphore, a condition variable, or a blocking queue, never a mutex.

Why it matters in production

Because bounded concurrency is one of the highest-leverage reliability tools in a backend service, and a semaphore is how you implement it. A service calling a downstream that can handle 20 concurrent requests will, without a bound, send it 200 under a traffic spike and take it down — then time out, retry, and take it down again. A 20-permit semaphore in front of that call converts an outage into a queue and then into fast rejections, which is the bulkhead pattern.

Because misusing a binary semaphore as a mutex produces bugs that are hard to attribute. Nothing stops an unrelated code path from releasing a permit it never took, so the limit silently rises to two and the section is no longer exclusive. A mutex would have thrown `IllegalMonitorStateException`. Type safety here is real safety.

And because interviewers use the question to see whether you can go past the flashcard. Everyone knows "mutex is one, semaphore is many". The ownership answer, and the reentrance consequence that follows from it, is what separates a memorised comparison from understanding.

How it works

Implementing it

Use a lock (`ReentrantLock`, `synchronized`, `std::mutex`) when the requirement is exclusivity over shared state, and let its ownership semantics catch your mistakes.

Use a counting semaphore for concurrency limits per dependency, sized to what the dependency can absorb rather than to what your service can generate. One semaphore per downstream, not one shared across all of them, or a slow dependency starves a fast one.

Always pair acquire with a `finally` release, and prefer a wrapper — a `withPermit` helper, try-with-resources, an RAII guard — so the pairing cannot be skipped by a new code path.

Do not size a semaphore by trial and error against your own latency. Apply Little's law: permits ≈ target throughput × expected latency, then verify the downstream can sustain it.

// Bulkhead: bound in-flight calls to one dependency, reject fast when saturated
private final Semaphore permits = new Semaphore(20);

Quote fetch(Request r) throws InterruptedException {
    if (!permits.tryAcquire(50, TimeUnit.MILLISECONDS)) {
        throw new DependencySaturatedException("pricing");   // shed, do not queue
    }
    try {
        return pricingClient.call(r);
    } finally {
        permits.release();          // must be finally, or the pool drains on errors
    }
}

// Ownership is the real difference
ReentrantLock lock = new ReentrantLock();
lock.unlock();                     // IllegalMonitorStateException: not the owner

Semaphore s = new Semaphore(1);
s.release();                        // permits == 2 now; exclusivity silently gone

Interview questions and how to answer them

Answers that lose the round

• Giving only "one versus many" as the difference and missing ownership, which is the property every practical consequence follows from
• Claiming a binary semaphore is a mutex: it has no owner, so it is not reentrant and any thread can release it
• Using a semaphore to guard shared state and letting an unrelated path release a permit, silently raising the limit
• Acquiring a permit outside a try and releasing inside it, so an exception between the two leaks a permit permanently
• Recursively acquiring a single-permit semaphore, which deadlocks the thread against itself with no detector to report it
• Blocking indefinitely on `acquire` under saturation, converting a downstream slowdown into total thread exhaustion
• Sharing one semaphore across several dependencies, so the slowest one consumes all the permits

FAQ

Related

More backend concepts

• Write-ahead logging
• Two-phase commit
• Saga pattern
• Transactional outbox
• Lost update problem
• Phantom read
• Dirty read
• REST API design