The C11 Memory Model and Atomics¶

Until C11, C had no memory model. That means the language spec didn’t say what happens when two threads read and write the same variable — it was left to implementations, and implementations disagreed. C11 fixed this by adopting a memory model modeled on C++11’s: it defines exactly what is and isn’t undefined behavior in the presence of threads, and provides <stdatomic.h> so you can write correct, portable, lock-free code.

This file walks you through the practical parts of that model. You’ll leave with three things: (1) the ability to use _Atomic variables and atomic_* operations correctly, (2) an intuition for the six memory orders and which one to pick when, and (3) a real understanding of why cache coherence exists and how it constrains the fast paths of your programs.

Why the memory model exists¶

Modern CPUs and compilers reorder memory operations aggressively for performance:

The compiler may hoist a load out of a loop, reorder independent stores, or drop a redundant load.
The CPU has store buffers (writes queued before hitting cache), load-store queues, and out-of-order execution.

Without a memory model, this is fine for single-threaded code (as long as the observable single-thread behavior is preserved). For multithreaded code, it’s disastrous: thread A writes data=1; ready=1; and thread B sees ready=1 but reads data=0 because the CPU reordered the writes.

The memory model gives you two things:

Atomic operations — reads and writes that are indivisible; other threads never see a torn value.
Memory ordering guarantees — controls over how reads and writes on the same thread appear to other threads.

`_Atomic` and `<stdatomic.h>`¶

#include <stdatomic.h>

_Atomic int counter = 0;
// or equivalently: atomic_int counter = ATOMIC_VAR_INIT(0);

atomic_fetch_add(&counter, 1);       // atomic ++counter, returns old value
atomic_store(&counter, 42);
int x = atomic_load(&counter);

_Atomic bool flag = false;
bool expected = false;
if (atomic_compare_exchange_strong(&flag, &expected, true)) {
    /* CAS succeeded: flag was false, now true */
}

Operations you’ll use daily:

Operation	What it does
`atomic_load(&x)`	Read `x` atomically.
`atomic_store(&x, v)`	Write `v` to `x` atomically.
`atomic_fetch_add(&x, n)`	`x += n`, return old `x`.
`atomic_fetch_sub(&x, n)`	`x -= n`, return old `x`.
`atomic_fetch_or/and/xor`	Bitwise variants.
`atomic_exchange(&x, v)`	Set `x = v`, return old `x`.
`atomic_compare_exchange_strong(&x, &expected, desired)`	If `x == expected`, set `x = desired` and return true; else load `x` into `*expected` and return false.
`atomic_compare_exchange_weak(...)`	Same, allowed to spuriously fail even when `x == expected`. Use inside a retry loop.

_weak vs _strong: on some architectures (ARM in particular), the underlying LL/SC instructions can fail spuriously. _weak exposes that, so on those platforms it’s cheaper than _strong (which has to retry internally). Rule: use _weak inside a retry loop you’re writing anyway; use _strong if you’re not looping.

The six memory orders¶

Every atomic operation takes an optional memory order. The default is memory_order_seq_cst (sequential consistency), the strongest and safest.

Order	What it means	When to use
`memory_order_relaxed`	Only atomicity, no ordering. Other threads may see writes to unrelated variables in any order relative to this one.	Counters where only the final value matters; statistics; reference counting increments (not decrement-to-zero — that needs `acq_rel`).
`memory_order_consume`	Weaker acquire; only applies to dependencies through the loaded value. Deprecated in practice — compilers implement it as `acquire`. Do not use.
`memory_order_acquire`	On a load: no reads or writes in the current thread can be reordered before this load. Pairs with a release store.	Read side of publish-subscribe: load the pointer, then read the pointed-to data with confidence.
`memory_order_release`	On a store: no reads or writes in the current thread can be reordered after this store. Pairs with an acquire load.	Write side of publish: set up the data, then publish the pointer.
`memory_order_acq_rel`	Both, for RMW ops.	`atomic_fetch_sub` on a reference count, where zero triggers destruction.
`memory_order_seq_cst`	Everything above, plus a single total order that all seq_cst operations across all threads agree on.	Default. Use unless you have a benchmark showing the weaker order matters.

The acquire-release publish pattern¶

The single most useful atomic pattern in real code. Producer prepares data, then publishes a pointer with release. Consumer loads the pointer with acquire, then reads the data.

_Atomic(int*) shared_ptr = NULL;

/* producer */
int *p = malloc(sizeof(int) * 1024);
for (int i = 0; i < 1024; i++) p[i] = compute(i);
atomic_store_explicit(&shared_ptr, p, memory_order_release);

/* consumer */
int *p;
while (!(p = atomic_load_explicit(&shared_ptr, memory_order_acquire))) { /* wait */ }
int x = p[42];   // guaranteed to see the compute() result

Without the acquire/release, the consumer might read p[42] before the producer’s stores to p[42] became visible. With them, the release ordering pairs with the acquire ordering, and everything the producer wrote before the release is visible to the consumer after the acquire.

Why seq_cst is the default and relaxed is a footgun¶

memory_order_seq_cst gives you the illusion of a single global order of atomic operations that all threads agree on. This is the mental model of the naive multithreaded programmer, and it’s slow — seq_cst on x86 requires expensive mfence or xchg instructions; on ARM it’s even more expensive.

memory_order_relaxed gives you nothing but atomicity. Other threads may see your writes in any order, or arbitrarily delayed. Reasoning about correctness with relaxed is genuinely hard — even experts get it wrong. Do not use relaxed unless you have both a benchmark showing seq_cst is a bottleneck and a proof (or model-checker verification) that your algorithm is correct under relaxed.

The honest workflow:

Write it with seq_cst (the default; just use atomic_load(&x) etc.).
Benchmark.
If the atomic op shows up in your profile: try acquire/release.
If that still shows up: consider relaxed, prove correctness on paper.

Most programs never reach step 3.

Cache coherence intuition¶

Every core has its own L1 and L2 caches. When two cores read the same memory address, both have it in their L1 in a state called Shared. When one core writes, it must first send an invalidate message to all other cores holding that cache line; they mark their copies invalid. The writer’s copy goes to Modified. On next read, the other cores must re-fetch — from the writer’s cache (via cache-to-cache transfer) or from memory.

This protocol (MESI, or MOESI on AMD) is what makes atomics work correctly across cores. It’s also what makes them expensive: an atomic that misses cache and requires cache-line transfer can take 30-100+ ns — vs 1 ns for an L1 hit.

False sharing is the pathology that follows. Two variables a and b that happen to share a cache line (typically 64 bytes on x86-64). Thread 1 writes a; thread 2 writes b. Neither writes the other, but every write invalidates the other’s cache line. Throughput collapses.

Fix:

struct {
    _Atomic int a;
    char pad[64 - sizeof(int)];
    _Atomic int b;
} shared_state;

Or use alignas(64):

#include <stdalign.h>
struct {
    alignas(64) _Atomic int a;
    alignas(64) _Atomic int b;
} shared_state;

perf c2c (mentioned in phase 4 file 07) is the tool that finds false sharing. Run it before you assume you don’t have any.

`atomic_thread_fence`¶

Sometimes you want ordering without a specific atomic operation to attach it to — e.g., double-checked locking, or when you’re using _Atomic variables together in a lock-free algorithm. atomic_thread_fence(memory_order_release) inserts a compiler+CPU barrier without a memory operation.

Rule of thumb: if you’re reaching for a naked fence, you’re probably making a mistake. The pairing acquire-load / release-store is almost always cleaner and correct-by-construction. Fences exist; use them last.

`volatile` is not atomic — do not confuse them¶

volatile tells the compiler “don’t optimize away accesses to this variable.” It does not give you atomicity, ordering with respect to other memory, or cross-thread visibility guarantees.

volatile is for MMIO (memory-mapped I/O registers) and sig_atomic_t in signal handlers.
_Atomic is for cross-thread communication.

Code that uses volatile int flag for thread synchronization is buggy. It may appear to work on x86 (where the memory model is strong) and fail on ARM (where it isn’t).

What most people get wrong about this¶

They think atomics are “like locks but faster.” They’re not. Locks give you mutual exclusion over a region; atomics give you ordered access to a single variable. You can build a lock out of atomics (a spinlock is exactly atomic_flag_test_and_set in a loop), but you cannot build “protect this whole struct” out of a single atomic — you’d need a lock or a much cleverer lock-free algorithm. When in doubt: use a mutex. Atomics are for the few, hot, well-understood paths.

Practice this week¶

Write a shared counter incremented by 8 threads, 1M increments each. Verify with atomic_int + atomic_fetch_add. Then use a plain int and see the count come out wrong. Then wrap in a mutex — correct again, but measurably slower for this workload.
Implement a spinlock with atomic_flag. Compare its throughput to pthread_mutex_t at 2, 4, and 16 threads. Spinlock wins at low contention, loses catastrophically at high contention. Understand why (busy-wait vs futex sleep).
Create the false-sharing scenario above. Measure with and without padding. Typical speedup: 5-20×. Then confirm with perf c2c record + perf c2c report.
Read chapter 4 (“Counting”) of McKenney’s perfbook. It’s the best introduction to atomic reasoning in existence, and it walks you through the same counter problem with increasingly sophisticated solutions.

References¶

Paul McKenney, Is Parallel Programming Hard… — chapters 4 (Counting), 15 (Advanced Synchronization: Memory Ordering). The chapter 15 diagrams alone are worth the read.
Hans Boehm, “Threads Cannot Be Implemented as a Library” (2005) — the paper that pushed C/C++ to adopt a memory model. Historical but clarifying.
Preshing on Programming (preshing.com) — a whole blog on memory ordering with clean, minimal examples. Start with “Memory Barriers Are Like Source Control Operations.”
cppreference.com’s <stdatomic.h> and memory_order pages — not tutorial, but the definitive reference.
man 3 atomic_load, man 7 atomic_ops (Linux glibc).

Return to README.md · Next: 03_lock_free_and_lock_hierarchy.md