Mutex and Semaphore

Definition: Synchronization primitives used to control access to shared resources in concurrent systems, ensuring that operations on shared state don’t interleave in ways that corrupt it.

How It Works

• Mutex (mutual exclusion lock): a binary lock with a strict ownership rule. Only the thread that locked it can unlock it; the lock is a mechanism for one thread to say “I’m using this resource right now,” not a general-purpose signal.
• Counting semaphore: an integer counter initialized to N, with two atomic operations, wait()/P() (decrement; block if the result would go below zero) and signal()/V() (increment; wake a waiter if any). Allows up to N threads to hold the semaphore concurrently, making it suitable for limiting access to a pool of N interchangeable resources.
• Binary semaphore: a semaphore with value 0 or 1. Superficially similar to a mutex, but critically, any thread can call signal() on it, not just the thread that called wait(), which makes it usable as a general signaling mechanism between threads, something a true mutex isn’t designed for.
• Spinlock: a lock where a thread trying to acquire it busy-waits (spins in a loop, burning CPU) instead of yielding the CPU/blocking. Only appropriate when the expected wait is shorter than the cost of a context switch, common inside kernel code protecting very short critical sections.
• Reader-writer lock: allows either multiple concurrent readers or one exclusive writer, never both, useful when reads vastly outnumber writes and read-read access doesn’t need to be serialized.

Under the Hood

On Linux, both pthread_mutex_t and semaphores are commonly implemented on top of the futex (fast userspace mutex) syscall. The key optimization: in the uncontended case, locking and unlocking happens entirely in userspace with a single atomic compare-and-swap instruction, no syscall at all. Only when there’s actual contention, a thread finds the lock already held, does the code fall into the futex() syscall to actually block the thread (parking it on a kernel wait queue) or wake a blocked one. This is why uncontended mutex operations are extremely cheap, a handful of nanoseconds, while contended ones cost a full kernel round trip.

A mutex’s ownership requirement is enforced at the primitive level in many implementations (pthread_mutex_unlock from a thread that doesn’t hold the lock is undefined behavior), which is what enables features like priority inheritance, the kernel can identify exactly which thread is blocking others and temporarily boost its priority, and recursive mutex variants, since the lock has a defined owner to check against for re-entrant locking.

A semaphore’s counter has no concept of ownership; it’s just shared state guarded by an atomic operation. That’s precisely what makes it suitable as a producer-consumer signal (a producer calls signal() to indicate “one item is now available,” a consumer calls wait() to consume one) even though the producer and consumer are different threads, an operation a strict mutex forbids.

History

• Edsger Dijkstra introduced the semaphore in 1965, along with the P()/V() operation names, abbreviations of the Dutch words for “try” (proberen) and “increment” (verhogen), still used in some textbooks today alongside wait()/signal().
• Early mutex implementations were pure kernel objects, every lock/unlock required a full syscall, which made uncontended locking surprisingly expensive on 1990s hardware relative to today.
• The futex (fast userspace mutex), introduced to Linux in the early 2000s, was the key optimization that made the uncontended fast path, an atomic compare-and-swap with no syscall, the default behavior of pthread_mutex_t, only falling into the kernel when threads actually contend.

Debugging Workflow

A “hung” multi-threaded process where threads are blocked but not deadlocked, or where lock contention is silently eating throughput, is diagnosed differently depending on which symptom it is:

$ cat /proc/<pid>/task/*/stack       # kernel-side blocking point per thread (needs root)
$ gdb -p <pid> -batch -ex "thread apply all bt"
Thread 4: #0 __lll_lock_wait () #1 pthread_mutex_lock () #2 process_request ()

If most threads are parked in pthread_mutex_lock waiting on the same lock, that’s contention, not a deadlock, worth checking whether the critical section is doing more work than necessary or whether the lock is too coarse-grained.

$ strace -c -e trace=futex -p <pid>
% time     seconds  usecs/call     calls    syscall
 94.20    2.481022         812      3054 futex

A syscall summary dominated by futex calls is a strong signal of heavy lock contention, since the uncontended fast path never reaches the kernel at all, every futex() call visible here represents an actual block or wake. Comparing this against a lower-contention build (fewer or finer-grained locks) is a concrete way to validate that a locking refactor actually reduced contention rather than just moving it around.

Why It Matters

• Prevents race conditions and data corruption in shared-memory multi-threaded applications, the foundational tool for making concurrent code correct.
• Semaphores generalize mutexes into a resource-counting and signaling tool, which is what makes them the right primitive for bounded resource pools (database connection limits, rate limiters) rather than simple exclusion.
• Correct use of these primitives is a prerequisite for avoiding both race conditions (too little synchronization) and Deadlock (synchronization used incorrectly).

Common Pitfalls

• Deadlocks from acquiring multiple locks in inconsistent order across threads, the same root cause covered in Deadlock, just with mutexes as the specific resource.
• Over-locking: wrapping far more code than necessary in a single lock, which serializes unrelated work and reduces concurrent throughput to effectively single-threaded speed.
• Using a mutex where a semaphore (or vice versa) is the semantically correct tool. Trying to signal across threads with a mutex, unlocking from a thread that never locked it, is undefined behavior in most implementations.
• Forgetting to release a lock on an exception/error path, leaving it held forever and blocking every other thread that needs it. RAII-style scoped locks (std::lock_guard in C++, defer mu.Unlock() in Go, try/finally in Java) exist specifically to make this structurally hard to forget.
• Priority inversion when a low-priority thread holds a lock a high-priority thread needs, and medium-priority threads preempt the low-priority holder, indirectly starving the high-priority thread. Solved with priority inheritance, which most production mutex implementations support.

Condition Variables

A mutex alone only answers “can I safely touch this data right now”; it has no way to make a thread wait for a specific condition to become true (a queue becoming non-empty, a counter reaching a target) without wastefully spinning. Condition variables solve this: a thread holding a mutex calls wait() on the condition variable, which atomically releases the mutex and blocks the thread, avoiding the race where the condition could change between checking it and going to sleep. Another thread that changes the shared state calls signal()/notify() (waking one waiter) or broadcast()/notify_all() (waking all of them), and each woken thread reacquires the mutex before wait() returns. This pairing, mutex plus condition variable, is the standard building block for producer-consumer queues, thread pools, and barriers in most languages (pthread_cond_t, Java’s Object.wait/notify, C++‘s std::condition_variable).

Comparison

	Mutex	Counting Semaphore	Binary Semaphore	Spinlock
Ownership	Yes, strict	No	No	Yes
Max concurrent holders	1	N	1	1
Can signal across threads	No	Yes	Yes	No
Blocked thread behavior	Sleeps (parked)	Sleeps (parked)	Sleeps (parked)	Busy-waits (spins)
Typical use	Protecting a critical section	Limiting access to N resources	Simple cross-thread signaling	Very short kernel-level critical sections
Uncontended cost	~Nanoseconds (userspace CAS)	~Nanoseconds (userspace CAS)	~Nanoseconds (userspace CAS)	Nanoseconds, but wastes CPU if held long
Priority inheritance support	Common (PTHREAD_PRIO_INHERIT)	Rare	Rare	Not applicable

Language-Level API Reference

Language	Mutex	Semaphore	Condition Variable
C (POSIX)	pthread_mutex_t	sem_t	pthread_cond_t
C++	std::mutex	std::counting_semaphore (C++20)	std::condition_variable
Java	synchronized / ReentrantLock	java.util.concurrent.Semaphore	Object.wait/notify, or Condition
Go	sync.Mutex	No built-in; use a buffered channel	sync.Cond
Python	threading.Lock	threading.Semaphore	threading.Condition

Example

A mutex protecting a shared connection pool, and a semaphore capping concurrent outbound HTTP requests:

mutex pool_lock
semaphore http_slots(10)   // allow at most 10 concurrent HTTP calls

acquire(pool_lock)
conn = pool.borrow()
release(pool_lock)

http_slots.wait()          // blocks once 10 requests are already in flight
send_http_request(conn)
http_slots.signal()        // frees a slot for the next waiting caller

The mutex enforces “only one thread touches the pool’s internal list at a time.” The semaphore enforces a completely different constraint, “at most 10 requests run at once”, which a mutex alone can’t express since a mutex only ever allows exactly one holder. In POSIX code this maps directly to pthread_mutex_lock/unlock and sem_wait/sem_post.

FAQ

Can a semaphore be used as a mutex? A binary semaphore can approximate one, but without ownership enforcement, any thread can release it, even one that never acquired it, which is exactly the safety property a real mutex is designed to guarantee. Use a mutex when you need exclusion with a clear owner.

Is a spinlock ever the right choice in application code? Rarely. Spinlocks make sense when the critical section is extremely short and the expected wait is shorter than a context switch, common inside OS kernels and lock-free data structure internals, but in ordinary application code a sleeping lock is almost always the better tradeoff.

Why do some mutex implementations support recursion and others don’t? A recursive (reentrant) mutex lets the same thread lock it multiple times without deadlocking itself, useful when a function that holds the lock calls another function that also needs it. Non-recursive mutexes are simpler and slightly cheaper, and recursion is often considered a code smell suggesting the locking boundary should be redesigned instead.

Related Terms

• Concurrency and Race Condition
• Deadlock
• Process and Thread
• CPU Scheduling