AlgoInsight

Free lesson · Concurrency Interview Mastery

Mutex (Mutual Exclusion)

Medium11 min readconcurrencymultithreadinginterview-prep

In Module 2 you met the mutex in five different languages - synchronized and ReentrantLock in Java, std::mutex in C++, lock in C#, sync.Mutex in Go, threading.Lock in Python. This module steps back from the syntax to the primitive itself: what a mutex fundamentally is, how it actually works beneath the API, and the properties that distinguish one mutex from another. This is the layer that makes the language-specific versions comprehensible - once you understand the primitive, every language's mutex is just a particular packaging of the same idea. And it's the layer interviewers probe when they ask "but how does a lock actually work?"

A mutex - short for mutual exclusion - is the most fundamental synchronization primitive. Its single job: ensure that only one thread executes a protected region of code at a time. Everything else in this course builds on it.

The problem a mutex solves

Recall the core hazard from Module 1: when multiple threads access shared mutable state and at least one writes, the interleaving of their operations can corrupt that state. The classic example is incrementing a shared counter. count++ looks atomic but is actually three steps - read the value, add one, write it back - and two threads interleaving those steps lose updates.

Thread A reads count (0)
Thread B reads count (0)
Thread A computes 0+1, writes 1
Thread B computes 0+1, writes 1     // should be 2, but it's 1 - lost update

The region of code that touches shared state and must not be interleaved is the critical section. A mutex makes a critical section run atomically with respect to other threads: while one thread is inside, no other thread can enter. The lost-update race vanishes because the read-modify-write sequence can no longer interleave.

What a mutex provides

A mutex has two operations - conceptually lock (acquire) and unlock (release) - and one invariant: at most one thread holds the mutex at any moment.

mutex.lock()        // acquire: if free, take it; if held, BLOCK until it's free
    // critical section - exclusive access guaranteed here
mutex.unlock()      // release: hand it to a waiting thread, or leave it free

When a thread calls lock on a free mutex, it acquires it and proceeds. When a thread calls lock on a mutex another thread already holds, it blocks - it waits, making no progress, until the holder calls unlock. At that point one waiting thread acquires the mutex and proceeds. This is the whole contract: exclusive access for the holder, blocking for everyone else, until release.

Two consequences follow from this contract, and they're the heart of why mutexes work. First, mutual exclusion: the critical section is serialized - threads take turns, never overlap. Second, and easy to forget, a mutex also provides memory visibility: as you saw in the memory-model lessons, releasing a mutex publishes the holder's writes to the next thread that acquires it. A mutex isn't only a turnstile; it's also a memory barrier that makes one thread's changes visible to the next. Both guarantees matter, and both come from the same acquire/release discipline.

stateDiagram-v2
    [*] --> Unlocked
    Unlocked --> Locked: thread acquires (lock succeeds)
    Locked --> Unlocked: holder releases (unlock), no waiters
    Locked --> Locked: another thread calls lock -> it BLOCKS (waits)
    Locked --> HandedOff: holder releases, a waiter is waiting
    HandedOff --> Locked: waiting thread acquires
    note right of Locked
        Exactly one holder.
        Others block until release.
    end note

This state diagram shows the lifecycle of a mutex. It starts in the Unlocked state. When a thread acquires it, the lock succeeds and it moves to the Locked state, where exactly one thread holds it. If another thread calls lock while it's held, that thread blocks and waits - the mutex stays Locked. When the holder releases and no one is waiting, the mutex returns to Unlocked. When the holder releases and a waiter is present, the mutex is handed off directly to a waiting thread, which acquires it and the mutex stays Locked under the new owner. The core invariant, noted on the Locked state, is that there is exactly one holder at a time and all others block until release.

How a mutex actually works under the hood

This is where the primitive gets interesting, and where strong candidates separate themselves. A mutex can't be built from ordinary reads and writes - the very lost-update race it prevents would corrupt the lock's own state. So mutexes are built on atomic hardware instructions, the indivisible read-modify-write operations the CPU guarantees can't be interleaved.

The classic building block is test-and-set: atomically read a flag and set it to "taken," returning the old value, in one uninterruptible instruction. If the old value was "free," you got the lock; if it was "taken," someone else has it. Modern implementations more often use compare-and-swap (CAS): atomically, "if this location equals expected, set it to new." A thread acquires the lock by CAS-ing the lock word from "unlocked" to "locked"; if the CAS succeeds, it has the lock, and if it fails, someone else got there first. Because the hardware guarantees these operations are atomic, two threads can't both see the lock as free and both take it.

That handles acquiring a free lock. But what does a thread do when the lock is held? Two strategies:

Note: Real-world mutexes are usually hybrid: they spin briefly (betting the lock will free quickly), then fall back to blocking if it doesn't. On Linux, the blocking path is built on the futex ("fast userspace mutex") system call, which lets the fast, uncontended case stay entirely in user space - a CAS with no kernel involvement at all - and only enters the kernel when a thread actually has to wait. This is why an uncontended lock/unlock is cheap (just an atomic instruction) while a contended one is expensive (a system call and a context switch). Knowing that the uncontended path avoids the kernel, and the contended path doesn't, explains the entire performance profile of locking and is a standout interview answer.

Properties that distinguish mutexes

Not all mutexes are the same. Several properties vary, and knowing them helps you choose and reason correctly:

Ownership. A proper mutex has an owner - the thread that locked it is the only one allowed to unlock it. This ownership is exactly what distinguishes a mutex from a binary semaphore (more on that below), and it's what lets a mutex detect misuse like unlocking a lock you don't hold.

Reentrancy (recursive locking). Can the holder lock the same mutex again without deadlocking itself? A non-reentrant mutex deadlocks if the holder tries to re-acquire it (common with std::mutex, sync.Mutex). A reentrant (recursive) mutex counts acquisitions and allows the holder to lock multiple times, requiring an equal number of unlocks (Java's synchronized and ReentrantLock, C#'s lock). Reentrancy matters when a locked method calls another method that locks the same mutex.

Fairness. When the lock frees and several threads are waiting, which gets it? A fair mutex grants it in FIFO order, preventing starvation but costing throughput. An unfair mutex lets any waiter (often a currently-running one) grab it, which is faster but can starve unlucky threads. Most default mutexes are unfair for performance; some (like Java's ReentrantLock(true)) offer an optional fair mode.

// non-reentrant: this DEADLOCKS - the thread waits for a lock it already holds
mutex.lock()
mutex.lock()    // blocks forever; the holder (this thread) never unlocks

// reentrant: this is fine - same thread re-acquires, must unlock twice
recursive.lock()
recursive.lock()   // ok, count = 2
recursive.unlock() // count = 1
recursive.unlock() // count = 0, released

Mutex vs binary semaphore

A frequent interview question, because the two look identical - both have two states and two operations. The distinguishing property is ownership. A mutex is owned: only the locking thread may unlock it. A binary semaphore is not owned: any thread can signal (release) it, including one that never acquired it. This makes them suited to different jobs - a mutex protects a critical section (the same thread enters and leaves), while a binary semaphore is better for signaling between threads (one thread waits, a different thread signals). Using a mutex where you need cross-thread signaling, or a semaphore where you need owned mutual exclusion, is a design smell. We cover semaphores fully in the next lesson; for now, hold onto "mutex = owned mutual exclusion; binary semaphore = unowned signaling."

Using a mutex correctly

The primitive is simple; misusing it is easy. The essential disciplines, true in every language:

Warning: The most common mutex bug isn't in the mutex - it's forgetting to use it on some access to the shared state. A mutex only works if every access to the protected data goes through it. One unguarded read or write - a single place where a thread touches the shared state without locking - reintroduces the race, and it's invisible in review because the code looks fine in isolation. Discipline: identify the shared state, decide which mutex guards it, and ensure no code path touches it without holding that mutex. The lock is only as good as your consistency in using it.

Contention: where mutexes cost you

Understanding the performance of a mutex comes down to one word: contention - how often threads actually compete for the same lock. The cost of a mutex is wildly different depending on whether it's contended, and this is the single most important thing to understand about mutex performance.

An uncontended lock - one no other thread is trying to acquire at that moment - is nearly free. As covered above, acquiring it is just an atomic compare-and-swap in user space, a handful of nanoseconds, with no kernel involvement. So a mutex that's rarely contended costs almost nothing, and you should never avoid locking out of vague performance fear when contention is low. The lock itself is cheap; correctness is worth it.

A contended lock is a different story. When a thread tries to acquire a held lock, it eventually blocks - a system call into the kernel, the thread descheduled, a context switch to another thread, and later another context switch to wake it back up when the lock frees. That's on the order of microseconds, a thousand times costlier than the uncontended case. Worse, while contended, threads are serialized - they're taking turns, not running in parallel, which is the opposite of what you wanted concurrency for. High contention turns a multi-threaded program back into a sequential one with added overhead, the re-serialization trap from Module 1 made concrete at the primitive level.

This cost model drives every locking-performance decision. To reduce contention you have a few levers: shrink the critical section so the lock is held for less time, reducing the window in which others can collide with it; split one lock into several (finer granularity) so threads contending for different data don't contend for the same lock; or avoid locking entirely for hot single-variable cases by using atomics instead. Each of these is a way of attacking contention, and the next module on locking strategies is essentially a catalog of contention-reduction techniques. The mental model to carry forward: a mutex's price is paid almost entirely under contention, so the art of high-performance locking is the art of minimizing how often and how long threads actually compete for the same lock.

Tip: When profiling concurrent code that isn't scaling, lock contention is one of the first things to check. A program that runs no faster - or slower - with more threads is often bottlenecked on a hot lock that serializes the threads despite the parallelism you added. The fix is rarely "remove the lock" (that reintroduces races); it's to reduce contention by the levers above - smaller critical sections, finer-grained locks, or lock-free atomics for the hottest paths. Recognizing "this doesn't scale because of lock contention" and naming the remedy is exactly the kind of performance reasoning senior interviews probe.

The interview angle

Interview: Reliable questions: (1) "What is a mutex and what does it guarantee?" - Mutual exclusion: at most one thread in the critical section at a time (lock/unlock), plus memory visibility (release publishes writes to the next acquirer). (2) "How does a mutex work under the hood?" - Built on atomic hardware instructions (test-and-set or compare-and-swap); uncontended acquire is a userspace atomic, contended waiting spins briefly then blocks via the OS (futex on Linux), which is why uncontended locking is cheap and contended locking is expensive. (3) "Mutex vs binary semaphore?" - A mutex is owned (only the locker unlocks), suited to mutual exclusion; a binary semaphore is unowned, suited to signaling between threads. (4) "What is a reentrant mutex?" - One the holder can re-acquire without deadlocking, releasing an equal number of times; matters when locked code calls other locked code. (5) "What's the most common mutex mistake?" - Failing to guard every access to the shared state, or holding the lock too long. The under-the-hood answer (atomics + spin-then-block + futex) is the one that signals real depth.

Quick reference

MUTEX = mutual exclusion: at most ONE holder at a time.
  lock()/acquire   -> take it, or BLOCK until free
  unlock()/release -> hand off to a waiter, or leave free
  also provides MEMORY VISIBILITY (release publishes writes to next acquirer)

UNDER THE HOOD:
  built on atomic instructions: test-and-set / compare-and-swap (CAS)
  uncontended  -> userspace atomic, no kernel (cheap)
  contended    -> spin briefly, then block via OS (futex on Linux) (expensive)

PROPERTIES:
  ownership   -> only the locker may unlock (distinguishes mutex from binary semaphore)
  reentrancy  -> can the holder re-lock? recursive mutex counts and needs equal unlocks
  fairness    -> FIFO (no starvation, slower) vs barging (faster, can starve)

DISCIPLINE:
  always release (scope-bound: RAII / defer / finally)   keep critical sections SMALL
  guard EVERY access to the shared state                 order locks to avoid deadlock

The mutex is the foundation. The next lesson generalizes it: a semaphore is, in a sense, a mutex that lets N threads through instead of one - the primitive for limiting concurrency and for signaling between threads, and the building block from which much of the rest of this module is constructed.

Back to Concurrency Interview Mastery