skip to content

How does a semaphore differ from a mutex, and why is a binary semaphore not a drop-in replacement for a mutex?

level: middleimportance: must knowfreq 66%

answer

  1. ownership is the difference, not the count
  2. mutex: only the owner unlocks
  3. semaphore: any thread may release — that's the point
  4. no owner ⇒ no reentrancy, no priority inheritance
  5. stray release silently widens a binary-semaphore lock

basics

~20 s

A mutex has an owner: only the thread that locked it may unlock it, which enables reentrancy, priority inheritance and error detection. A semaphore is an ownerless permit counter, so any thread may release. That makes it a signal, not a lock.

solid answer

~50 s

The difference is **ownership**, not the permit count. A mutex is a mutual-exclusion device with a recorded owner. The runtime knows which thread holds it, so it can reject an unlock from a non-owner, support recursive acquisition, apply priority inheritance to stop priority inversion, and often detect deadlock or abandoned locks. Lock and unlock are meant to bracket a critical section in one thread. A semaphore is an ownerless counter of permits. Any thread may release, including one that never acquired. That is the whole point when you use it for signalling — a producer releases a permit that a consumer consumes — but it removes every ownership-based safety net. So a binary semaphore *can* enforce mutual exclusion, and it will, but you lose owner checks, reentrancy and priority inheritance, and you gain a new failure mode: a stray or duplicated release quietly lets a second thread into the critical section. Rule of thumb: **mutex for mutual exclusion, semaphore for counting resources and for signalling across threads.**

code

text · 11 lines
text
sem = Semaphore(1)          # used as a "lock"

worker():
  sem.acquire()
  try: mutate(shared)
  finally: sem.release()

cleanup_on_error():          # buggy path, no matching acquire
  sem.release()              # permits -> 2, no error raised

# from now on two threads run mutate(shared) concurrently

go deeper

for a junior

Lead with ownership: only the locking thread unlocks a mutex, while any thread can release a semaphore, and give one example of each use.

for a middle

Explain what ownership buys — unlock authorisation, reentrancy, diagnostics — and name the concrete bug where a stray release widens a binary-semaphore critical section.

for a senior

Work through priority inversion and inheritance, discuss detectability of misuse, and state the selection rule by intent (exclusion versus counting versus signalling).

for a principal

Argue the design position: the primitive should encode the invariant you actually mean, so ownership-bearing exclusion and ownerless counting stay separate types in the codebase rather than one general-purpose gadget everyone reaches for.

## The one distinction that matters: ownership Candidates usually answer "a mutex allows one thread, a semaphore allows N". That is a consequence, not the definition — a binary semaphore also allows one. The real distinction is that **a mutex is owned and a semaphore is not**. A mutex records the identity of the thread currently holding it. That single piece of state unlocks a family of guarantees: - **Unlock authorisation.** Only the owner may unlock. An unlock from another thread is a detectable programming error rather than silent corruption. - **Reentrancy.** A recursive mutex can let the owner re-lock, keeping a nesting depth. An ownerless semaphore cannot distinguish "the owner again" from "a second thread", so re-acquiring a binary semaphore you already hold self-deadlocks. - **Priority inheritance.** If a high-priority thread blocks on a mutex held by a low-priority thread, the scheduler can temporarily boost the holder so it finishes and releases. This requires knowing who the holder is, so it is impossible for a semaphore. - **Diagnostics.** Deadlock detectors, lock-order checkers, "held by thread T for 4s" telemetry and abandoned-lock recovery all key off the owner. A semaphore stores only a count and a wait queue. It cannot answer "who holds this?" because in general the answer is meaningless — with N permits there are up to N holders, and with a signalling semaphore the releaser was never a holder at all. ## Why ownerless release is a feature Semaphores exist to express things a mutex cannot: - **Resource counting.** "At most 8 threads may touch the connection pool" is a count, not exclusion. - **Signalling.** With an initial count of zero, one thread blocks in acquire while a completely different thread releases when an event occurs. A mutex cannot model this — unlocking a mutex you never locked is an error, by design. - **Producer/consumer hand-off.** In a bounded buffer, the producer releases the permit the consumer will acquire, and vice versa. The permit travels between threads; ownership would forbid exactly that. So the two primitives are not competitors on a scale of "how many threads". They encode different things: a mutex encodes *this region is entered by one thread at a time and that thread is responsible for leaving it*; a semaphore encodes *there are this many units available*. ## The concrete failure mode of using a binary semaphore as a lock Suppose you guard a critical section with a semaphore initialised to one, and somewhere in a rarely-taken error path a thread releases without a matching acquire — a retry loop that calls the cleanup twice, or an exception handler that releases in addition to the `finally` block. On a counting-style implementation the permit count becomes two, and from that moment two threads execute the critical section concurrently, forever. Nothing throws. The data race appears far from the buggy line and is nearly impossible to trace back. With a mutex the same mistake produces an immediate, local error: unlocking a mutex you do not own is diagnosable, and unlocking one that is already unlocked is undefined-or-detected rather than silently permission-granting. Classic *binary* semaphores that saturate at one permit avoid this specific inflation, but they still give you no owner check, no reentrancy and no priority inheritance. ## Priority inversion, concretely A low-priority thread L takes the lock. A medium-priority thread M becomes runnable and preempts L. A high-priority thread H blocks on the lock. Now H waits on L, which cannot run because M is hogging the CPU: the high-priority thread is effectively running at medium-minus priority. With a mutex the system can boost L to H's priority until it releases (priority inheritance) or run it at a fixed ceiling (priority ceiling protocol). With a semaphore there is no holder to boost, so this class of fix simply does not exist. This is why real-time guidance is emphatic: use mutexes for mutual exclusion, semaphores only for counting and signalling. ## What they share Both block, both need a release on every exit path (use whatever the language's scope guard, `finally` or `defer` mechanism is), both can be fair or barging, and both can suffer convoying under contention. Neither says anything by itself about memory visibility beyond the ordering its own acquire/release establishes. ## The choosing rule - Exclusive access to mutable state, single thread in and out → **mutex**. - A bound on how many things may happen at once → **counting semaphore**. - One thread must wait for another to announce something → **semaphore initialised to zero**, or a condition variable/latch if a predicate is involved.

  • Give a case where you must use a semaphore and a mutex will not work at all.
    Any cross-thread signal: thread A must block until thread B finishes some work. A semaphore initialised to zero handles it directly — A acquires and blocks, B releases when done. A mutex cannot express this because unlocking a mutex you never locked is an ownership violation, and mutex acquisition is not a queue of pending events.
  • Why can't a semaphore support priority inheritance?
    Priority inheritance works by temporarily raising the priority of the thread that holds the lock so it can finish and release. A semaphore does not record a holder — with N permits there may be N of them, and with a signalling semaphore the releaser never acquired. With no identifiable holder to boost, the mechanism has nothing to act on, so unbounded priority inversion stays possible.
  • Is a counting semaphore with one permit the same as a binary semaphore?
    Not exactly. A binary semaphore saturates at one permit, so an extra release is absorbed or rejected. A counting semaphore initialised to one has no ceiling, so an unmatched release raises the count to two and permanently doubles the concurrency it allows. Neither gives you ownership, so neither is a mutex.

A mutex is a hotel room key handed to one guest who must return it themselves. A semaphore is a stack of gym-locker tokens: anyone can drop a token back on the pile, and nobody records who took which.

saying these in an interview costs you the question

  • "Mutex allows one thread, semaphore allows many" stated as the whole difference
  • Claiming a binary semaphore and a mutex are interchangeable
  • Believing a semaphore can be recursive because it holds a count
  • Expecting the runtime to error on release-without-acquire
  • Reaching for a semaphore to guard shared mutable state because it "is a lock with a counter"

context

resolving links…