Mutex Internals: From Cache Lines to Futex Wait Queues

Hardware does not implement pthread_mutex_lock() or std::condition_variable directly.

Hardware gives lower-level tools:

• atomic loads and stores;
• atomic read-modify-write operations;
• cache coherence;
• memory ordering controls;
• fences;
• interrupts and context-switch support.

Libraries and kernels build synchronization primitives on top.

The stack looks like this:

application code
  |
  | std::atomic / pthread_mutex / pthread_cond / Rust Atomic / parking_lot
  v
libc / language runtime
  |
  | fast path: userspace atomic instructions
  | slow path: syscall into kernel
  v
kernel
  |
  | futex wait queues, scheduler, task states, wakeups
  v
CPU hardware
  |
  | cache coherence, atomic RMW instructions, fences, load/store ordering
  v
cache line / memory system

The dependency graph:

cache coherence + atomic RMW + ordering
  |
  +-> atomic<T>
  |
  +-> spinlock
  |
  +-> mutex fast path
          |
          +-> futex slow path
                  |
                  +-> condition-variable blocking

The important split:

atomic:
make one memory operation indivisible

spinlock:
wait by retrying in userspace

mutex:
try in userspace, sleep in the kernel if contended

condition variable:
wait for a predicate transition while coordinating with a mutex

There are two separate hardware problems.

Cache coherence:

For one memory location, all cores agree on the order of writes.

Memory consistency / ordering:

For multiple memory locations, when do writes by one core become visible
to another core, and in what order?

Cache coherence makes this operation behave as one shared-object update:

std::atomic<int> x;
x.fetch_add(1);

Memory ordering makes this pattern meaningful:

data = 123;
ready.store(true, std::memory_order_release);

// another thread
if (ready.load(std::memory_order_acquire)) {
    use(data);
}

The release store says:

make earlier writes visible before publishing ready

The acquire load says:

after observing ready, do not move later reads before the acquire

Atomicity alone does not provide that full message-passing contract.

On x86, atomic read-modify-write operations are commonly implemented with the LOCK prefix:

lock cmpxchg [mem], reg
lock xadd    [mem], reg
lock add     [mem], reg
xchg         [mem], reg     ; xchg with memory is implicitly locked

Old mental model:

LOCK = freeze the entire memory bus

Modern cached-memory mental model:

LOCK = obtain exclusive ownership of the cache line,
       perform the read-modify-write atomically,
       use the coherence protocol to serialize conflicting access.

Rough flow for lock cmpxchg(&x):

1. Core 0 issues Read-For-Ownership for the cache line containing x.
2. Other cores' copies of that line are invalidated or downgraded.
3. Core 0 obtains the line in an exclusive/modified state.
4. Core 0 performs compare + store as one atomic RMW.
5. Other cores observe either the old value or the new value, never a half-update.

Important point:

The update does not need to be flushed to DRAM immediately.
Visibility is handled through cache coherence, not by making DRAM the first observer.

This code is atomic but still wrong as a publication protocol:

data = 42;
flag.store(1, std::memory_order_relaxed);

Another thread:

if (flag.load(std::memory_order_relaxed)) {
    printf("%d\n", data);
}

The flag itself is atomic. But relaxed ordering does not guarantee that data = 42 becomes visible before flag = 1.

The usual lock pattern is:

lock.acquire();   // acquire ordering
critical_section();
lock.release();   // release ordering

C++ exposes common ordering modes:

For locks:

lock acquisition:
  acquire

lock release:
  release

That is the minimum shape that makes critical-section memory effects usable by the next owner.

A mutex is not just a spinlock. A mutex can sleep.

spinlock:
  wait by burning CPU

mutex:
  try fast atomic acquire
  if contended, block in the kernel
  scheduler runs someone else

Linux classifies mutexes as sleeping locks and raw spinlocks as spinning locks.

uncontended:
  stay in userspace

contended:
  ask kernel to park and wake waiters

struct Mutex {
    std::atomic<int> state{0};
    // 0 = unlocked
    // 1 = locked, no known waiters
    // 2 = locked, maybe waiters
};

void lock(Mutex* m) {
    int expected = 0;

    if (m->state.compare_exchange_strong(
            expected,
            1,
            std::memory_order_acquire,
            std::memory_order_relaxed)) {
        return;
    }

    lock_slow(m);
}

no syscall
no scheduler
one atomic compare-and-swap

void lock_slow(Mutex* m) {
    for (;;) {
        int expected = 0;
        if (m->state.compare_exchange_strong(
                expected,
                2,
                std::memory_order_acquire,
                std::memory_order_relaxed)) {
            return;
        }

        futex_wait(&m->state, 2);
    }
}

void unlock(Mutex* m) {
    int old = m->state.exchange(0, std::memory_order_release);

    if (old == 2) {
        futex_wake(&m->state, 1);
    }
}

futex_wait(address, expected)

kernel checks:
  *address == expected?

if yes:
  put this thread to sleep atomically

if no:
  return immediately

Thread B checks lock is held.
Thread A unlocks and wakes.
Thread B goes to sleep after the wake.
Thread B may sleep forever.

Thread B asks kernel: sleep only if state is still 2.
If Thread A already changed state to 0, the kernel refuses to sleep B.

A condition variable is not a lock.

It is a wait queue for a predicate.

Correct usage:

std::mutex m;
std::condition_variable cv;
bool ready = false;

std::unique_lock<std::mutex> lock(m);

while (!ready) {
    cv.wait(lock);
}

Incorrect usage:

if (!ready) {
    cv.wait(lock);
}

The loop matters because:

• wakeups may be spurious;
• another thread may consume the condition before this thread reacquires the mutex;
• the wait returning does not by itself prove the predicate is true.

POSIX explicitly requires callers to re-evaluate the predicate after return from pthread_cond_wait() or pthread_cond_timedwait().

Bad version:

// Thread A
if (!ready) {
    cond_wait(cv);
}

// Thread B
ready = true;
cond_signal(cv);

Lost wakeup race:

Thread A checks ready == false.
Thread B sets ready = true and signals.
Thread A starts waiting.
No one signals again.
Thread A can sleep forever.

Correct version:

// Thread A
lock(m);
while (!ready) {
    cond_wait(cv, m);
}
unlock(m);

// Thread B
lock(m);
ready = true;
unlock(m);
cond_signal(cv);

The mutex protects the predicate:

ready

The condition variable coordinates the wait queue:

who is sleeping until ready might become true

They solve different parts of the problem.

Timeline view:

Thread A                      Thread B
--------                      --------
lock(m)
ready == false
register waiter
release m and sleep
                              lock(m)
                              ready = true
                              unlock(m)
                              signal(cv)
wake
reacquire m
recheck ready
continue

The key is that the predicate check, waiter registration, mutex release, and blocking sequence are coordinated so that the signal cannot disappear between “I should sleep” and “I am asleep.”

These are educational models, not production implementations. Real locks handle ABI constraints, owner tracking, robust mutexes, priority inheritance, adaptive spinning, cancellation, timeouts, process-shared memory, scheduler policy, and many platform-specific details.

class SpinLock {
    std::atomic<int> state{0};

public:
    void lock() {
        for (;;) {
            while (state.load(std::memory_order_relaxed) != 0) {
                cpu_relax();
            }

            int expected = 0;
            if (state.compare_exchange_strong(
                    expected,
                    1,
                    std::memory_order_acquire,
                    std::memory_order_relaxed)) {
                return;
            }
        }
    }

    void unlock() {
        state.store(0, std::memory_order_release);
    }
};

class Mutex {
    std::atomic<int> state{0};
    // 0 = unlocked
    // 1 = locked, no waiters
    // 2 = locked, possible waiters

public:
    void lock() {
        int expected = 0;

        if (state.compare_exchange_strong(
                expected,
                1,
                std::memory_order_acquire,
                std::memory_order_relaxed)) {
            return;
        }

        for (;;) {
            expected = 0;
            if (state.compare_exchange_strong(
                    expected,
                    2,
                    std::memory_order_acquire,
                    std::memory_order_relaxed)) {
                return;
            }

            state.store(2, std::memory_order_relaxed);
            futex_wait(&state, 2);
        }
    }

    void unlock() {
        int old = state.exchange(0, std::memory_order_release);

        if (old == 2) {
            futex_wake(&state, 1);
        }
    }
};

class CondVar {
    std::atomic<uint32_t> seq{0};

public:
    void wait(Mutex& m) {
        uint32_t old = seq.load(std::memory_order_relaxed);

        m.unlock();

        futex_wait(&seq, old);

        m.lock();
    }

    void signal() {
        seq.fetch_add(1, std::memory_order_release);
        futex_wake(&seq, 1);
    }

    void broadcast() {
        seq.fetch_add(1, std::memory_order_release);
        futex_wake(&seq, INT_MAX);
    }
};

• Linux kernel memory barriers
• Linux Generic Mutex Subsystem
• Linux futex(2) manual page
• POSIX pthread_cond_wait()
• Intel 64 and IA-32 Architectures Software Developer Manuals
• RISC-V ratified specifications