Mutex vs semaphore (binary and counting)

Difficulty: Intermediate

Question

What is the difference between a mutex and a semaphore? What are binary and counting semaphores, and where is each used?

Answer

This question is asked so often that it deserves a memorable framing. A mutex is like the key to a single-person restroom: whoever takes the key is inside, and only that person can hand the key back. A semaphore is like a parking lot entrance counter showing the number of free spaces: any car leaving can increase the count, and cars enter only while the count is above zero. One is about ownership and exclusive access; the other is about counting available resources and signalling between threads.

A mutex (mutual exclusion lock) has two operations, lock and unlock, and exactly one thread can hold it at a time. Critically, it has ownership: the thread that locked it must be the one that unlocks it. Mutexes are used to protect critical sections. Many implementations add features such as priority inheritance to fight priority inversion, recursive locking, and error checking.

A semaphore, invented by Dijkstra, is an integer variable manipulated only through two atomic operations. wait (P, or down) decrements the value, and if it would go negative, the caller blocks. signal (V, or up) increments the value and wakes up one blocked waiter if any. A well-implemented semaphore avoids busy waiting by putting waiting processes on a queue and blocking them.

A binary semaphore has value 0 or 1 and can enforce mutual exclusion like a lock. A counting semaphore has an arbitrary non-negative value and controls access to a pool of N identical resources, for example 5 database connections or 10 buffer slots. Initialize it to N; each user does wait before using a resource and signal after.

Now the important distinctions. First, ownership: a mutex must be released by its owner, while a semaphore can be signalled by any thread, which is what makes it suitable for signalling and ordering. For instance, thread A can wait on a semaphore initialized to 0, and thread B signals it when data is ready. This is used for producer-consumer synchronization and cannot be done properly with a mutex. Second, purpose: a mutex is a locking mechanism; a semaphore is a signalling mechanism. Third, value range: a mutex is effectively binary, while a semaphore counts. Fourth, misuse risk: because semaphores lack ownership, a bug where a thread signals a semaphore it never waited on silently breaks mutual exclusion, and a binary semaphore used as a lock does not give priority inheritance.

Also mention the monitor and condition variable, which are higher-level constructs that wrap a mutex with wait and signal on conditions, as used in Java's synchronized, wait and notify. In practice, use a mutex for protecting data, a counting semaphore for resource pools and for producer-consumer counts, and condition variables when the waiting depends on a predicate.

A classic trap question is whether a binary semaphore and a mutex are the same. The honest answer is that they behave similarly for mutual exclusion, but they differ in ownership semantics and in supporting features such as priority inheritance, and they are designed for different purposes. Another trap: what does a semaphore value of negative N mean? In the classical definition, it means that N processes are blocked waiting.

Code examples

Semaphore as a signal and as a pool limit (Python)

import threading, time

pool = threading.Semaphore(3)          # counting: 3 connections
ready = threading.Semaphore(0)         # signalling: starts at 0

def worker(i):
    with pool:                         # wait() ... signal()
        print(f"worker {i} using connection")
        time.sleep(0.1)

def consumer():
    ready.acquire()                    # blocks until producer signals
    print("consumer: data is ready")

def producer():
    time.sleep(0.2)
    ready.release()                    # signal from a different thread

threads = [threading.Thread(target=worker, args=(i,)) for i in range(6)]
threads += [threading.Thread(target=consumer), threading.Thread(target=producer)]
for t in threads: t.start()
for t in threads: t.join()

The pool semaphore limits concurrency to 3. The ready semaphore starts at 0 and is released by a different thread, which a mutex could not legitimately do.

Key points

• Mutex has an owner; only the locker may unlock it.
• Semaphore has no owner and can be signalled by any thread.
• Binary semaphore: 0 or 1; counting semaphore: pool of N resources.
• wait/P decrements and may block; signal/V increments and may wake a waiter.
• A negative value in the classic definition equals the number of blocked waiters.

Concepts covered

mutex, semaphore, binary semaphore, counting semaphore, wait and signal