Interviewers ask “what’s the difference between a mutex and a semaphore?” because the common answer, “a mutex is a semaphore with a count of one”, is half right in a way that causes real bugs. The two share a mechanism (a counter plus a queue of waiting threads) but they model different things. A mutex models ownership of some shared state. A semaphore models a number of available permits. Pick the one that matches what you’re protecting, and the code tells the next reader what you meant.
A mutex protects an invariant and has an owner
Use a mutex when some data must never be seen half-updated. A linked list whose pointers are mid-rewrite, a bank transfer that has debited one account but not credited the other, a cache entry and its expiry time. The rule is that a thread takes the lock, makes the data consistent again, and releases it. Exactly one thread holds it at a time, and that thread is the owner.
Ownership isn’t just a convention. Because the system knows which thread holds a mutex, it can do things a plain counter can’t:
- refuse a release from a thread that doesn’t own it
- detect a thread trying to lock a mutex it already holds
- support recursive locking, where the owner may lock again and must release the same number of times
- boost the owner’s priority when a more important thread is waiting for it (priority inheritance)
- tell the next locker that the previous owner died while holding it (robust mutexes on Linux return
EOWNERDEAD)
Here is a POSIX error-checking mutex on macOS, locked by the main thread, with a second thread trying to release it:
pthread_mutexattr_t a; pthread_mutexattr_init(&a);
pthread_mutexattr_settype(&a, PTHREAD_MUTEX_ERRORCHECK);
pthread_mutex_init(&m, &a);
pthread_mutex_lock(&m);
/* a second thread calls pthread_mutex_unlock(&m) */
/* then the main thread calls pthread_mutex_lock(&m) again */unlock from non-owner thread: 1 (Operation not permitted)
owner locks it again: 11 (Resource deadlock avoided)EPERM for the stranger’s release and EDEADLK for the owner relocking. With the default mutex type both mistakes are undefined behaviour instead: they might appear to work, corrupt the lock or hang. Error-checking mutexes are worth turning on in debug builds for exactly this reason.
A semaphore counts permits and has no owner
A semaphore holds a non-negative count. wait (Dijkstra’s P, sem_wait, acquire) decrements it, blocking while it’s zero. post (V, sem_post, release) increments it and wakes a waiter. Any thread can post, including one that never waited. That’s the defining property, and it makes semaphores good at two jobs.
The first job is capping concurrency: allow at most N things at once. Here ten threads each call a slow downstream API, gated by a semaphore with three permits:
import threading, time
permits = threading.Semaphore(3)
active = 0; peak = 0; guard = threading.Lock()
def call_api(i):
global active, peak
with permits:
with guard:
active += 1; peak = max(peak, active)
time.sleep(0.2) # pretend this is a slow downstream call
with guard:
active -= 110 calls, 3 permits: peak concurrency 3, took 0.82sNever more than three in flight, and four waves of 0.2 seconds (3, 3, 3, then 1) give 0.8 seconds. Note that the semaphore didn’t protect any data; the counter active still needed its own mutex. That’s the clearest way to see the difference: the semaphore limits how many, the mutex keeps one piece of state consistent.
The second job is signalling. A semaphore initialised to zero lets one thread wait until another says “ready”: the waiter calls acquire, the other thread calls release when the data is in place. There’s no lock being held and returned, just a permit created by one thread and consumed by another. The bounded-buffer problem uses two counting semaphores this way, one counting empty slots and one counting full ones.
Where the “binary semaphore” answer goes wrong
A semaphore with count one does give mutual exclusion, but it gives up everything that ownership buys. Any thread can release it, so a bug that releases twice (an error path plus a finally, say) silently turns your one-at-a-time section into two-at-a-time. Python demonstrates the hazard, and it also has a surprise:
for kind in (threading.Lock, threading.RLock):
m = kind(); m.acquire()
def other():
try:
m.release(); print(f"{kind.__name__}: another thread released it, no error")
except RuntimeError as e:
print(f"{kind.__name__}: RuntimeError: {e}")
t = threading.Thread(target=other); t.start(); t.join()
s = threading.Semaphore(2); s.release()
print("Semaphore(2) after an extra release has value", s._value)
b = threading.BoundedSemaphore(2)
try:
b.release()
except ValueError as e:
print("BoundedSemaphore: ValueError:", e)lock: another thread released it, no error
RLock: RuntimeError: cannot release un-acquired lock
Semaphore(2) after an extra release has value 3
BoundedSemaphore: ValueError: Semaphore released too many timesPython’s basic Lock is really a binary semaphore: it has no owner, so another thread can release it without complaint. RLock tracks its owner and refuses. And a plain Semaphore accepts the extra release and now admits three threads where you meant two. BoundedSemaphore exists to catch that, and it’s the one to use for resource limits.
Ownership also explains why priority inheritance needs a mutex. When a high-priority thread blocks on a mutex, the kernel knows exactly which thread to boost. When it blocks on a semaphore, any thread might eventually post, so there’s nobody to boost.
What the kernel actually does
On Linux, both primitives in glibc are built on futexes. The uncontended path is a single atomic compare-and-swap on a word in user memory, with no system call at all. Only when a thread must wait does it call futex(FUTEX_WAIT) to sleep in the kernel, and the releasing thread calls FUTEX_WAKE if it sees waiters. So an uncontended mutex costs tens of nanoseconds, while a contended one costs a context switch. macOS has its own equivalent kernel wait primitive, and I didn’t trace it here.
A spinlock is the other option for very short critical sections on multicore machines: the waiter burns CPU checking the lock instead of sleeping. It wins when the hold time is shorter than a sleep-and-wake round trip, and loses badly when the holder gets preempted. Most mutex implementations spin briefly before sleeping to get some of both.
Across processes, POSIX offers named semaphores (sem_open) and process-shared mutexes placed in shared memory. Here ownership matters again: if a process dies holding a semaphore permit, that permit is gone for good, whereas a robust mutex lets the next locker find out and repair the state.
Interview practice: capping calls to a payment API
A payment provider allows at most five concurrent requests from your service. One engineer wrapped the client call in a mutex. Another replaced it with Semaphore(5), acquired before the call and released after a successful response. Review both versions.
A strong answer
The mutex version is correct but needlessly slow: it allows one request at a time, so throughput is a fifth of what the provider permits, and a single slow response stalls everyone. There’s no shared state to protect here; the requirement is a count, which is a semaphore’s job.
The semaphore version has a leak. If the call raises (a timeout, a 500), the release never runs and that permit is gone. After five failures, every thread blocks forever. The release belongs in a finally block, or better, use the with permits: form so it can’t be skipped. I’d also use BoundedSemaphore(5), so a future double release raises an error instead of silently allowing six.
Then the scaling question: this limit is per process. With four instances behind a load balancer, the provider sees up to twenty concurrent requests. Either divide the limit (a permit or two per instance, accepting some waste), or enforce it in a shared place such as a small rate-limiting service or a counter in Redis with expiry, so a crashed instance doesn’t hold permits forever.
More on synchronization
- Operating Systems interview questions
- Operating Systems MCQs
- Race Conditions and Atomic State Transitions
- Operating Systems: Thread Pools
- OSTEP, Semaphores, covering semaphores as locks, as signals and for the bounded buffer