Mutexes and semaphores

Why it matters

Locks are how most code makes critical sections safe, and they are also the most common cause of a multithreaded program that scales from one core to two and then stops. Knowing what a lock costs when nobody else wants it (almost nothing) versus when everybody does (everything) explains most concurrency performance problems, and semaphores turn up as connection pools, rate limiters and concurrency caps everywhere.

The idea

Mutex

A mutex (mutual exclusion lock) is held by at most one thread at a time. A thread calls lock before the critical section and unlock after; any other thread calling lock while it is held waits. A mutex has an owner: only the thread that locked it should unlock it, which lets implementations detect misuse and support inheritance-style fixes for the inversion problem from the scheduling module.

Semaphore

A semaphore holds a counter. Wait (also called P or acquire) decrements it, blocking if it would go below zero; signal (V or release) increments it and wakes a waiter. Initialise it to N and at most N threads hold it at once, which makes it the natural tool for bounding concurrency: a pool of 20 database connections, at most 8 concurrent image decodes, at most 100 in-flight requests to a dependency. A semaphore initialised to 1 behaves like a mutex without ownership, and semaphores can also be used for signalling between threads (one releases, another acquires).

	Mutex	Counting semaphore
Holders at once	One	Up to N
Ownership	Yes; the locker unlocks	No; any thread may release
Typical use	Protecting shared data	Bounding concurrency: pools, limits, permits
Common bug	Forgetting to unlock on an error path	Releasing more than acquired, inflating the count

How locks are built

Locks rest on atomic CPU instructions such as compare-and-swap (CAS) or test-and-set, which read and update a memory word as one indivisible step. An uncontended lock is a single CAS on a word in the thread's cache: a few nanoseconds. When the lock is taken, the waiter can spin (loop, retrying the CAS), which is fast if the holder will release within a microsecond or so but burns a core, or sleep (ask the kernel to park it), which costs a system call and a context switch. Linux's futex (fast userspace mutex) combines them: the fast path stays entirely in user space, and only on contention does a thread make a system call to sleep on the address. Most mutexes spin briefly, then sleep.

Reader-writer locks

When data is read far more often than written, a reader-writer lock lets many readers in at once but gives a writer exclusive access. It helps only when read sections are long enough to outweigh the extra bookkeeping, and it needs a policy for whether waiting writers block new readers; otherwise a stream of readers can starve writers. Read-mostly data is often better served by copy-on-write snapshots or RCU-style techniques that let readers proceed without any lock.

The real cost: contention

An uncontended lock is nearly free. A contended one serialises threads, bounces its cache line between cores, and forces sleeps and wake-ups, so adding threads makes the program slower. Remedies, in order: hold locks for less time (move I/O and computation outside), use finer-grained locks (one per bucket or shard instead of one global lock), use per-thread data merged later (per-core counters), and replace locks with atomics or lock-free structures where the access pattern allows.

Always unlock

Every code path out of a critical section must release the lock, including exceptions and early returns. Use the language's structured forms: synchronized blocks or try/finally in Java, with in Python, RAII guards (lock_guard, scoped_lock) in C++, defer mu.Unlock() in Go. A lock leaked on an error path is a deadlock waiting for the next caller.

Trade-offs

Mutexes are simple and correct for most shared data; semaphores generalise to N holders and signalling, at the cost of no ownership and easier misuse. Spinning saves context switches on short waits and wastes CPU on long ones. Coarse locks are easy to reason about and limit scaling; fine-grained locks scale and raise the risk of deadlock, the next lesson.

In an interview

Semaphores make concurrency limits concrete: "Each instance caps calls to the payment provider with a semaphore of 50 permits, so a slow provider cannot pin all our threads; callers that cannot get a permit within 100 ms fail fast." For contention: "Profiling showed threads waiting on one global cache lock, so we sharded the cache into 64 segments, each with its own lock."