Mutex Implementation: Atomic Operations and OS Primitives

The Foundation: Atomic Operations

In the last lesson, you saw that a simple check-then-set operation on a boolean flag is not thread-safe because it's a non-atomic read-modify-write sequence. A thread could be interrupted between reading the flag as false and setting it to true. So, how can we make this operation atomic, or indivisible?

The answer lies in specialized CPU instructions that the C++ standard library exposes through std::atomic. The most important of these for implementing locks is compare-and-swap (CAS).

A CAS operation, like std::atomic::compare_exchange_strong, does the following atomically:

1. Reads the value from a memory location.
2. Compares it to a provided expected value.
3. If they are equal, it writes a new desired value to that location and returns true.
4. If they are not equal, it does nothing and returns false.

This entire sequence is guaranteed by the hardware to be indivisible. No other thread can interfere.

To see how this is used, let's look at the most basic type of lock: a spinlock.

As the video shows, we can implement a simple spinlock by repeatedly trying to CAS the lock's state from "unlocked" to "locked" in a loop.

#include <atomic>

class Spinlock {
public:
    void lock() {
        // Keep trying to switch the flag from false (unlocked) to true (locked).
        // The while loop spins until it succeeds.
        while (flag.exchange(true, std::memory_order_acquire)) {
            // The lock was already held, so just spin.
            // On x86, this is a `pause` instruction to be more efficient.
        }
    }

    void unlock() {
        // Set the flag to false (unlocked).
        flag.store(false, std::memory_order_release);
    }

private:
    std::atomic<bool> flag = {false};
};

(Note: The exchange operation is another atomic primitive that writes a new value and returns the old one. It can be simpler than CAS for a basic spinlock.)

This works and is correct, but it has a major drawback: busy-waiting. If a thread is waiting for the lock, it burns CPU cycles spinning in a loop doing no useful work. This is fine if locks are held for very short periods, but it's terribly inefficient for longer waits.

The Deeper Problem: Memory Reordering

There's another critical reason we need primitives like std::mutex that goes beyond just atomicity: memory reordering. To optimize performance, both compilers and modern CPUs can reorder memory reads and writes in ways that are not visible to a single thread but can cause chaos in a multithreaded program.

Let's watch a segment from one of the most famous talks on this topic to understand the problem.

As you saw, even a simple store buffer can cause a write to become visible to other cores after a subsequent read, effectively reordering the operations.

Synchronization primitives like mutexes and atomics solve this by inserting memory barriers.

• A lock() operation typically acts as an acquire barrier. It ensures that no memory reads or writes from after the lock can be reordered to happen before it.
• An unlock() operation acts as a release barrier. It ensures that no memory reads or writes from before the unlock can be reordered to happen after it.

These barriers ensure that all memory operations inside the critical section stay "contained" between the lock and unlock. This is what std::memory_order_acquire and std::memory_order_release in the spinlock example refer to.

The Slow Path: Sleeping with Futexes

Busy-waiting in a spinlock is inefficient. The better approach for a contended lock is to give up the CPU and let the OS schedule another thread. We need to ask the kernel to put our thread to sleep and wake it up only when the lock is free.

On Linux, the primary mechanism for this is the futex (Fast Userspace Mutex) system call. The design philosophy of the futex is brilliant: make system calls only when absolutely necessary (i.e., on contention).

The two key futex operations are:

• futex(addr, FUTEX_WAIT, val, ...): This tells the kernel: "Check if the integer at addr still has the value val. If it does, put me to sleep. If it doesn't, return immediately with an error." The check is crucial to prevent a race condition where the lock is unlocked just before the WAIT call.
• futex(addr, FUTEX_WAKE, N, ...): This tells the kernel: "Wake up N threads that are currently sleeping on the futex at addr."

The kernel maintains internal wait queues for each memory address that threads are sleeping on, making this process efficient.

Putting It All Together: A Futex-Based Mutex

Now we can combine these pieces to build a complete, adaptive mutex. We can't use a simple boolean anymore; we need a state machine to track whether the lock is held and whether any threads are waiting. A common implementation, popularized by Ulrich Drepper's paper "Futexes Are Tricky", uses a single atomic integer with three states:

• 0: The mutex is unlocked.
• 1: The mutex is locked, and there are no threads waiting.
• 2: The mutex is locked, and there is at least one thread waiting in the kernel.

This leads to the following logic:

Locking (lock())

1. Fast Path: Atomically try to compare_exchange the state from 0 to 1. If this succeeds, you've acquired the lock without contention. You're done.
2. Slow Path: If the CAS fails, the lock is already held (state is 1 or 2).
   • Set the state to 2 to indicate that there is now a waiter. This prevents the unlocking thread from mistakenly thinking there are no waiters.
   • Call futex(FUTEX_WAIT, 2) to go to sleep.
   • When awakened by the kernel, loop back and try to acquire the lock again (e.g., CAS from 0 to 2, since you know there might be other waiters).

Unlocking (unlock())

1. Atomically decrement the state using fetch_sub(1).
2. Check the previous value of the state:
   • If it was 1 (locked, no waiters), the state is now 0. You're done. This is the fast path unlock.
   • If it was 2 (locked, with waiters), the state is now 1. This means you must wake a sleeping thread. Set the state to 0 and call futex(FUTEX_WAKE, 1).

Let's study a concrete implementation of this logic.

Conclusion

You've now seen the full picture of how a std::mutex is built from the ground up. It's not magic; it's a clever, two-phase algorithm that balances user-space performance with kernel-space efficiency.

Key Takeaways:

• A modern mutex is an adaptive lock, not a simple spinlock.
• The Fast Path (Uncontended): A single, atomic compare-and-swap (CAS) instruction in user-space acquires the lock with minimal overhead.
• The Slow Path (Contended): When the lock is held, the thread makes a futex system call to the kernel, which puts the thread to sleep efficiently. It avoids burning CPU cycles with busy-waiting.
• Memory Barriers: Lock and unlock operations also act as acquire and release memory barriers, preventing the compiler and CPU from performing harmful memory reorderings across the critical section.
• State Machine: The implementation relies on a multi-state atomic integer (e.g., 0=unlocked, 1=locked, 2=contended) to coordinate between threads in user-space and the kernel.

What's Next?

We've mastered how a thread can wait for a lock. But often, a thread needs to wait for a specific condition to become true (e.g., "the queue is no longer empty"). Using a mutex alone for this leads to inefficient busy-waiting. In our next lesson, we will introduce std::condition_variable, the C++ primitive designed for exactly this kind of signaling. You will see that it is also built on top of futexes and works hand-in-hand with std::unique_lock to create powerful and efficient synchronization patterns.