Offensive Security Researcher & Quantum Cryptography Analyst

How does a mutex lock ensure mutual exclusion in a critical section

Abdul Wahab Junaid
How does a mutex lock ensure mutual exclusion in a critical section

I think the best way to really understand mutual exclusion is to trace what happens at the hardware level when two threads race to acquire the same mutex at almost exactly the same instant. It’s easy to say “a mutex makes sure only one thread runs the critical section at a time,” but the how — the actual mechanism that guarantees this even when two CPU cores execute instructions within nanoseconds of each other — is genuinely interesting and worth understanding properly.

The Problem a Mutex Solves

A critical section is a block of code that accesses shared, mutable state in a way that must not be interrupted or interleaved with another thread’s access to the same state. Without protection, two threads executing balance = balance - amount concurrently can interleave at the machine-instruction level: both threads read the old value of balance before either writes back the new value, and one thread’s update is lost. This is a race condition, and it’s exactly what mutual exclusion prevents.

Step 1: The Atomic Test-and-Set (or Compare-and-Swap)

The foundation of every mutex implementation is a hardware-level atomic instruction — an instruction that the CPU guarantees executes as an indivisible unit, with no other core able to observe or interleave with it partway through. Common atomic primitives include:

On x86, this is implemented via instructions like LOCK CMPXCHG (compare-and-exchange with the LOCK prefix, which asserts a cache-coherence guarantee across cores). On ARM (relevant for Android and iOS devices), it’s implemented via load-linked/store-conditional pairs: LDXR (load exclusive) and STXR (store exclusive), which achieve the same atomicity guarantee through a different mechanism — the store only succeeds if no other core has touched that memory location since the load.

A simplified mutex lock() using CAS looks conceptually like this:

// simplified conceptual implementation
int lock_state = 0;  // 0 = unlocked, 1 = locked

void mutex_lock(int *lock_state) {
    while (!compare_and_swap(lock_state, 0, 1)) {
        // CAS failed — another thread holds the lock; retry or yield
    }
    // CAS succeeded — we now hold the lock; lock_state is now 1
}

void mutex_unlock(int *lock_state) {
    *lock_state = 0;  // release
}

The key insight: compare_and_swap is a single, hardware-guaranteed atomic operation. Even if two threads on two different CPU cores call it at literally the same nanosecond, the CPU’s cache-coherence protocol (typically MESI or a variant) ensures only one of them observes success. The other sees the CAS fail (because the value was no longer 0 by the time its attempt was processed) and must retry.

Step 2: What Happens When the Lock Is Contended

The simplified spin-loop above (while (!CAS...)) is called a spinlock — a thread that fails to acquire the lock keeps retrying in a tight loop, burning CPU cycles. This is fine for very short critical sections but wasteful if the lock is held for a long time, since the waiting thread contributes nothing useful while spinning and actively competes for CPU cache bandwidth with the thread that holds the lock.

Real-world mutex implementations (like pthread_mutex_t on Linux) are smarter: they use a hybrid approach. The thread spins briefly (a few iterations, or a few microseconds) hoping the lock will be released quickly, and if it isn’t, the thread calls into the kernel via the futex syscall to be put to sleep, removing it from the CPU scheduler’s active run queue entirely. When the lock holder calls unlock(), it checks whether any threads are sleeping on that futex and, if so, issues a wake-up syscall, causing the OS scheduler to make the waiting thread runnable again.

mutex_lock():
    1. Try atomic CAS (fast path) — succeeds if uncontended
    2. If CAS fails: spin briefly (optional, tunable)
    3. If still failing: futex_wait() syscall — thread sleeps, removed from run queue
    4. (later) woken by futex_wake() from the unlocking thread
    5. retry CAS — loop back to step 1

This is exactly why an uncontended mutex lock/unlock is extremely cheap (just the CAS instruction, no syscall) while a contended one is much more expensive (syscalls, context switches, scheduler involvement).

Step 3: Memory Ordering Guarantees

Mutual exclusion isn’t just about “who gets to run the code” — it’s also about memory visibility. A correct mutex implementation includes memory barriers (fences) that ensure all writes made by a thread inside the critical section are visible to the next thread that acquires the same mutex, in the correct order. Without this guarantee, even if only one thread logically “holds” the lock at a time, CPU instruction reordering and per-core caching could let another thread see stale or partially-updated data after acquiring the lock.

Formally, mutex acquire/release operations provide acquire and release semantics: lock() acts as an acquire barrier (no subsequent read/write in the critical section can be reordered before it), and unlock() acts as a release barrier (no prior read/write can be reordered after it). This is what makes the “happens-before” relationship well-defined: everything the previous lock-holder did before unlock() is guaranteed visible to whatever the next lock-holder does after its lock() succeeds.

Diagram: Two Threads Racing for the Same Mutex

Time -->

Thread A: [CAS attempt: 0->1] SUCCESS --> [critical section] --> [unlock: 1->0]
Thread B: [CAS attempt: 0->1] FAIL (saw 1) --> [spin/sleep] ------> [CAS attempt: 0->1] SUCCESS --> [critical section]
                                                                     ^ retries after A's unlock signals waiters

Even though both threads may issue their CAS instruction within the same few CPU cycles, the cache-coherence protocol serializes the underlying memory operation — only one CAS can “win” against a given memory location’s current value, because the hardware treats the read-compare-write as one indivisible unit.

Reentrant vs. Non-Reentrant Mutexes

A standard mutex is non-reentrant: if the thread that already holds the lock tries to lock it again (e.g., in a recursive function), it will deadlock against itself, since the mutex doesn’t distinguish “a new thread wants this” from “the same thread wants this again.” A reentrant (recursive) mutex tracks both an owner thread ID and an acquisition count, allowing the owning thread to re-acquire it multiple times, only truly releasing it once the count returns to zero via a matching number of unlocks. pthread_mutex_t supports this via the PTHREAD_MUTEX_RECURSIVE attribute on Linux/UNIX; Windows’ CRITICAL_SECTION is recursive by default; Java’s synchronized and ReentrantLock are also reentrant.

Real-World Use Cases

Troubleshooting

  1. Deadlock on self re-lock — verify whether your mutex type is reentrant; if not, recursive locking by the same thread will hang.
  2. High CPU usage under contention — check whether the mutex implementation is spin-heavy; tune spin duration or switch to a sleeping mutex for long critical sections.
  3. Stale data despite “correct” locking — verify the mutex implementation provides proper acquire/release memory barriers; on some embedded or custom lock implementations, this is easy to get wrong.

Best Practices

Summary

A mutex lock ensures mutual exclusion by combining a hardware-guaranteed atomic instruction (compare-and-swap or test-and-set) with OS-level blocking (via mechanisms like Linux’s futex) for contended cases, plus proper memory-ordering barriers to guarantee visibility of the critical section’s effects across threads. The atomic instruction guarantees that only one thread can transition the lock from “unlocked” to “locked” at a time, even under perfectly simultaneous contention, while the surrounding runtime machinery handles the efficiency of waiting and the correctness of what each thread sees once it acquires the lock.

FAQs

Q: What CPU instruction actually enforces mutual exclusion? Atomic instructions like compare-and-swap (x86: LOCK CMPXCHG) or load-linked/store-conditional pairs (ARM: LDXR/STXR), which the hardware guarantees execute indivisibly relative to other cores.

Q: Why is an uncontended mutex so fast? Because acquiring it only requires a single successful atomic CPU instruction in userspace, with no operating system involvement or context switch.

Q: What happens to a thread waiting on a contended mutex? It typically spins briefly, then is put to sleep via an OS mechanism (like Linux’s futex), removing it from the active scheduler queue until the lock is released and it’s woken up.

Q: Does a mutex guarantee memory visibility, or just exclusive execution? Both — a correctly implemented mutex includes acquire/release memory barriers, ensuring writes made inside the critical section are visible to the next thread that acquires the same lock.

References

Exit mobile version