C11 Memory Model: Reordering and Visibility

The C11 standard formally defined a multithreaded memory model for the C language, introducing native atomic types and operations via the <stdatomic.h> library. This standard establishes concrete guarantees that control both compiler and processor instruction reordering and govern cache visibility across threads. By defining concepts such as the "happens-before" relationship, modification order, and explicit memory ordering constraints, C11 enables developers to write portable, high-performance concurrent code without relying on vendor-specific compiler extensions or hardware-specific assembly instructions.

Data Races and the Abstract Machine

Prior to C11, the C abstract machine had no concept of concurrent execution threads. Compilers were free to reorder reads and writes assuming single-threaded execution.

Under C11, concurrent execution is an explicit part of the language specification. Two expressions conflict if one evaluates to modify a memory location and the other reads or modifies the same location. If two conflicting operations execute concurrently without synchronization, it constitutes a data race, which results in undefined behavior. The C11 memory model guarantees that any execution free of data races will behave predictably according to the synchronization constraints specified by the programmer.

Synchronization and the "Happens-Before" Relationship

Visibility and reordering in C11 are framed around the concept of the "happens-before" relationship. If operation \(A\) happens-before operation \(B\), the compiler and hardware guarantee that:

  1. \(A\) will be sequenced before \(B\) in terms of execution.
  2. Any memory modifications produced by \(A\) are fully visible to \(B\).

A happens-before relationship is established when an atomic operation in one thread "synchronizes-with" an atomic operation in another thread, creating an inter-thread ordering barrier that propagates cache updates and suppresses disruptive reordering.

C11 Memory Order Guarantees

C11 introduces six distinct memory ordering parameters via the memory_order enumeration, representing different levels of guarantees regarding reordering and visibility:

1. Sequential Consistency (memory_order_seq_cst)

This is the default ordering applied to all atomic operations if none is explicitly specified. It provides the strongest guarantees:

  • Reordering: No operations (atomic or non-atomic) can be reordered across a sequentially consistent operation.
  • Visibility: Enforces a single, globally visible total order of all seq_cst operations across all threads. Every thread observes these operations in the exact same sequence, making hardware caches appear instantaneously synchronized across cores.

2. Acquire-Release Semantics (memory_order_release, memory_order_acquire, memory_order_acq_rel)

Acquire-release ordering establishes targeted synchronization between threads without imposing a global total order.

  • memory_order_release: Applied to write operations. Guarantees that prior reads and writes (both atomic and non-atomic) within the current thread cannot be reordered after the release write. It flushes prior memory writes so they are visible to any thread that later performs an acquire operation on the same atomic variable.
  • memory_order_acquire: Applied to read operations. Guarantees that subsequent reads and writes cannot be reordered before the acquire read. When paired with a release store, it guarantees that all modifications made by the releasing thread become visible to the acquiring thread.
  • memory_order_acq_rel: Applied to read-modify-write operations (like atomic_fetch_add). Combines both acquire and release semantics.

3. Consume Semantics (memory_order_consume)

Designed to limit ordering guarantees strictly to data-dependent operations. Reads that depend on the value loaded by a consume operation are guaranteed not to be reordered before that load. Because tracking dependencies through compiler optimization passes is complex, most modern C compilers automatically promote memory_order_consume to memory_order_acquire.

4. Relaxed Ordering (memory_order_relaxed)

Relaxed operations provide the lowest level of overhead by eliminating synchronization and ordering barriers:

  • Reordering: The compiler and CPU are free to aggressively reorder instructions around the relaxed operation, provided they do not break single-thread program order constraints.
  • Visibility: Guarantees only atomicity and a consistent modification order for that specific atomic object. It does not establish a happens-before relationship and guarantees no visibility or ordering for other memory locations.

Modification Order

Regardless of the chosen memory ordering (even under memory_order_relaxed), C11 guarantees that all modifications to a single atomic variable occur in a single, universally agreed-upon total order known as the modification order. While different threads might observe changes to different variables in different sequences under weak ordering, no thread will ever observe writes to the same atomic variable out of its established modification order.

Explicit Memory Fences

In addition to operations tied directly to atomic variables, C11 provides standalone memory barriers using atomic_thread_fence(). Fences allow developers to enforce ordering and visibility rules across non-atomic memory operations without needing to execute a read or write on an atomic variable at that exact instruction, decoupling synchronization logic from specific data loads and stores.