Semaphore vs Mutex: Counting Permits Explained

"What is the difference between a semaphore and a mutex?" is one of the oldest concurrency interview questions, and the textbook answer, "a mutex is a semaphore with a count of one", is only half right. The useful answer is about what each one counts and who is allowed to give it back. Get that right and the follow-ups answer themselves.

The problem it solves

Some resources are limited but not single. A database allows 20 connections, a licence covers five seats, a partner API tolerates ten requests in flight. A mutex is too strict: it lets one thread in when twenty could go. No lock is too loose: the twenty-first caller gets an error.

What you want is a gate that lets up to N threads through and makes the rest wait, without anyone keeping a list of who is inside.

The intuition

A semaphore is a counter of permits:

• acquire takes a permit. If the count is above zero, it decrements and returns at once. If the count is zero, the caller blocks until a permit comes back, or returns False immediately if it asked not to block.
• release puts a permit back, increments the count, and wakes one waiting thread.

That is all it tracks. It never records which thread holds a permit, which is the lesson's one-liner: count the permits, not the holders.

Now compare a mutex. A mutex protects a critical section so that one thread at a time runs it, and conceptually it has an owner: the thread that locked it is the one that unlocks it. Many implementations enforce that; Python's reentrant lock raises an error if another thread tries to release it, and a reentrant lock also lets its owner acquire it again without deadlocking. A semaphore has no owner, so any thread may release it. That difference makes a semaphore useful for signalling (one thread releases, a different thread's acquire wakes up) and makes it easy to misuse as a lock.

So "a semaphore initialised to one behaves like a mutex" is true for what it lets in: one holder at a time. It is not true for what it checks: nothing stops the wrong thread from releasing it, or the same thread from releasing it twice.

One more boundary matters in interviews. A semaphore caps how many threads are inside; it does not make what they do in there safe. Three threads holding three permits can still race on shared data, and they need their own lock for that.

Watch it run

The animation uses the lesson's allotment: three wheelbarrows on a rack, and a semaphore that counts permits, never who is holding them. Plot A takes one, and acquire decrements the count, leaving two. Plot B takes the second; nobody scheduled anything or asked. Plot C takes the last one, the rack is empty and the count is 0. Then plot D asks: acquire(blocking=False) returns False, and a plain acquire would wait. Plot A wheels one back, and release puts a permit on the rack and wakes a waiter. Plot D takes it: four gardeners, three barrows, no coordinator. Initialise the count to one and you have a mutex, one permit meaning one holder at a time. It caps how many are inside, and what they do in there is still entirely your problem. Use it for things that are genuinely limited: connections, licences, outbound calls.

The code

The lesson's rack, step by step:

import threading

barrows = threading.Semaphore(3)     # three permits on the rack

for plot in ["A", "B", "C"]:
    barrows.acquire()
    print(plot, "took a barrow")
# A took a barrow
# B took a barrow
# C took a barrow

print("spare?", barrows.acquire(blocking=False))   # spare? False
barrows.release()                                  # plot A wheels one back
print("spare?", barrows.acquire(blocking=False))   # spare? True

Ten threads at a gate of three. Each one holds its permit until the main thread says go, so the snapshot shows exactly how many got in while the rest queue:

def crowd(limit, workers):
    gate = threading.Semaphore(limit)
    cond = threading.Condition()
    go = threading.Event()
    inside = peak = 0

    def task():
        nonlocal inside, peak
        with gate:                                 # acquire ... release, even on error
            with cond:
                inside += 1
                peak = max(peak, inside)
                cond.notify_all()
            go.wait()                              # hold the permit until told to go
            with cond:
                inside -= 1

    threads = [threading.Thread(target=task) for _ in range(workers)]
    for t in threads:
        t.start()
    with cond:
        cond.wait_for(lambda: inside == min(limit, workers))
        snapshot = inside                          # everyone else is queued at the gate
    go.set()
    for t in threads:
        t.join()
    return snapshot, peak

print(crowd(3, 10))                                # (3, 3)

With one permit, the semaphore gives mutual exclusion, and eight threads incrementing a shared total lose nothing:

def count_to(n_threads, per_thread, gate):
    total = 0
    def work():
        nonlocal total
        for _ in range(per_thread):
            with gate:                             # one permit: mutual exclusion
                total += 1
    threads = [threading.Thread(target=work) for _ in range(n_threads)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    return total

print(count_to(8, 2000, threading.Semaphore(1)))   # 16000

The two safety nets a plain semaphore lacks. A bounded semaphore refuses to be released above its starting count, and a reentrant lock refuses to be released by a thread that does not own it:

rack = threading.BoundedSemaphore(3)
try:
    rack.release()                                 # nobody took one
except ValueError as e:
    print("ValueError:", e)                        # ValueError: Semaphore released too many times

owned = threading.RLock()
owned.acquire()
errors = []
def stranger():
    try:
        owned.release()
    except RuntimeError as e:
        errors.append(str(e))
t = threading.Thread(target=stranger)
t.start()
t.join()
print(errors)                                      # ['cannot release un-acquired lock']

A brute-force check: 2,000 random sequences of acquire and release against a plain integer model of the permits, then 60 threaded runs with random limits and crowd sizes:

import random

random.seed(19)
ok = True
for _ in range(2000):                              # the permit arithmetic, op by op
    limit = random.randint(1, 5)
    sem, permits = threading.BoundedSemaphore(limit), limit
    for _ in range(30):
        if random.random() < 0.5:
            ok &= sem.acquire(blocking=False) == (permits > 0)
            permits -= permits > 0
        else:
            try:
                sem.release()
                raised = False
            except ValueError:
                raised = True
            ok &= raised == (permits == limit)
            permits += not raised
for _ in range(60):                                # and with real threads
    limit, workers = random.randint(1, 5), random.randint(1, 12)
    ok &= crowd(limit, workers) == (min(limit, workers),) * 2
print(ok)                                          # True

The complexity

• acquire and release are constant time apart from waiting: a counter update under an internal lock, plus waking one waiter.
• Throughput is capped at the number of permits. With N permits and work that takes time t, at most N items finish per t; the rest of the time is queueing, which is the point.
• Waiting is not first come, first served: Python does not guarantee which waiter wakes, and many other implementations do not either.

Where it goes wrong

• Forgetting to release on an error path. The permit leaks, and after N failures the gate is shut for good. Use with, or try and finally.
• Releasing more than you acquired. A plain semaphore quietly grows past its limit. A bounded semaphore turns that bug into an exception.
• Using a semaphore of one as a lock and then releasing it from the wrong thread, or acquiring it twice in the same thread and deadlocking.
• Assuming the permits protect the data. N holders can still race on what they share.
• Acquiring two semaphores in different orders in different threads. That is the classic deadlock setup, permits or not.

When it shows up in interviews

It appears as "semaphore versus mutex", as "limit this crawler to ten concurrent requests", and inside design questions about connection pools and bounded queues. A producer-consumer buffer can be built from two semaphores, one counting free slots and one counting filled ones, plus a mutex for the buffer itself. Expect a follow-up on what happens when a holder crashes, and on fairness.

How to say it in an interview

"A semaphore is a counter of permits. Acquire takes one or waits when there are none; release puts one back and wakes a waiter. It caps how many threads use something at once, such as connections or outbound calls, and it does not track who holds a permit, so any thread can release it, which also makes it usable for signalling. A mutex is about exclusive ownership: one holder, and the holder is the one that unlocks it. A semaphore of one gives the same exclusion but without the ownership check, so for a critical section I use a real lock, and for a limited pool I use a bounded semaphore, released in a finally or a with block."