Atomics: What Is Memory Order?
Peeking inside stdatomic.h, we see each of the atomic_* functions has a corresponding explicit function, denoted by the _explicit suffix. The explicit functions take one extra argument: a memory_order enum.

At first this may seem strange. Isn't the purpose of an atomic function to ensure the thing executes as a single atomic operation - what does memory order have to do with it? You may also be wondering what memory order even is to begin with. Let's clear this up first and then answer that question.

Memory order simply refers to the order in which operations on regions of memory occur. You may be more comfortable thinking of operations on variables, since that's the semantics programming languages use. But a variable is just some region of memory whose value is whatever the bits in that region represent. There are 2 fundamental operations on memory: load (read) and store (write).

Memory order was already hinted at in the Intro To Atomics article. But let's spell it out now.

Let's consider a situation where we have a multi-threaded program and it is not making use of any synchronization primitives. That is, no variables are atomic, there are no mutexes or anything else. Just normal variables being accessed by the threads. Each thread itself has a well-defined memory order. Lines of source code which occur before other lines (within the same thread!) must appear as though they executed prior to the other lines. And every line must appear to execute fully before the next. However, any operations on the same memory region across threads is undefined. There is no memory order at all!

This means if thread 1 performs an operation X on a variable M, and thread 2 performs an operation Y on M, any of the following scenarios are possible: a) thread 1 observes Y fully completing and then X, b) thread 1 observes X fully completing and then Y, c) thread 1 observes Y in an intermediate state and then X, d) thread 1 observes X in an intermediate state and then Y. The same 4 possibilities may be observed in thread 2. And most importantly, both threads may observe completely different orderings! So thread 1 may see Y complete then X, whereas thread 2 sees X partially complete and then Y.

This is commonly referred to as read and write tearing or a "data race", when intermediate states are visible. The article What Is Mutual Exclusion? demonstrates this with the classic example of incrementing a normal variable in two threads. Many increments are lost because the threads are reading intermediate states. This can be rectified with a mutex, because a mutex imposes a sequentially-consistent memory ordering (we will get there).

Okay, the situation is a little more complicated.

You probably noticed I italicized the word "appears" in a paragraph above. A line of source code that comes before another must appear to execute first. What this means is any consequences of the former line must be visible to the latter line. But there are plenty of situations where lines of code could be swapped and everything would remain the same. If they have no relationship to one another, for example. The compiler may re-order instructions to optimize the code. It is allowed to do this as long as the code appears to run in the correct order. But it's not just the compiler. The CPU may re-order instructions too for different reasons.

A single-threaded program works fine because the memory order is defined within a single thread. But clearly a multi-threaded program with an undefined memory order is hardly useful at all. Atomics are meant to be an alternative to mutexes. But if atomics had no way of impacting memory order (like a mutex does), then it wouldn't be a very useful addition at all. That's why memory order shows up with atomics.

There are 6 memory_order enums. Each one falls into one of 4 memory order classes. These classes provide different levels of memory ordering guarantees. They are hierarchical in that each class does everything the lower class does and more. The next articles will dive into the details of these 4 memory order classes.

< Introduction To Atomics | Atomics: Relaxed Memory Order >