↓Recommended to follow↓

This article is a sister piece to “C++ Concurrency Programming”. It will focus on the memory model introduced by the C++11 standard.

Introduction

In the article “C++ Concurrency Programming”, we have already introduced the new APIs in concurrent programming from C++11 to C++17.

With the knowledge from that article, you should be able to develop a complete C++ concurrent system. This is sufficient for most people.

However, in some cases, we may need to go further.

Recall that the knowledge mentioned above is centered around mutexes. To avoid race conditions, it ensures that only one thread can enter the critical section at any time. This raises two issues:

1. Deadlocks may occur.
2. The efficiency of concurrency is not enough.

The issue of deadlocks has been discussed in the previous article. As for the second point, the reason for the insufficient concurrency efficiency is that those strategies are lock-based: once a thread enters the critical section, other threads can only wait.

Is there a strategy that allows other threads to proceed without waiting, achieving better concurrency?

The answer is yes, this is called a lock-free strategy. However, implementing this strategy can be more complicated, as you need a deeper understanding of the C++ memory model, which is what this article aims to explain.

For programming with lock-free strategies, readers can also refer to the article by Jeff Preshing: “An Introduction to Lock-Free Programming”^[1].

About the C++ Memory Model

In 2004, Java 5.0 introduced a memory model suitable for multi-threaded environments: JSR-133^[2]. However, C++ did not introduce a memory model until the 2011 standard.

The Java memory model significantly influenced the C++ memory model, but the latter goes further. It allows developers to break sequential consistency (Sequential Consistency, which we will explain below) for better control.

This is because C++ is a systems programming language, and one of its design intentions is to provide developers a way to program “close to the machine” without needing another lower-level language.

Even though most programmers do not need to care about the memory model, understanding these principles becomes crucial when working in a “close to the machine” manner.

The memory model is the foundation for reliable operation in multi-threaded environments, as it requires a complete definition of the operational details of multi-threaded environments.

In simple terms, the memory model can be thought of as a contract. It defines a set of operations and the detailed meanings behind these operations. Developers use this set of operations to synchronize data to avoid race conditions, while the system (including: compiler, operating system, and processor) guarantees that the execution logic conforms to the memory model’s definitions for relevant operations – thus fulfilling the contract.

The memory model mainly includes the following three parts:

• Atomic operations: As the name suggests, these operations cannot be interrupted once executed; you cannot see their intermediate state; they either complete execution or do not execute at all.
• Local order of operations: A series of operations cannot be executed out of order.
• Visibility of operations: Defines how operations on shared variables are visible to other threads.

Why do we need a memory model?

Before the C++11 standard, the C++ environment had no concept of multi-threading. Compilers and processors assumed there was only one execution flow in the system. Once multi-threading was introduced, the situation became very complex. This is because modern computer systems automatically include many optimizations to speed up execution. These optimizations ensure that the original logic is not broken in a single-threaded environment. However, once it comes to multi-threading, the situation is different.

In fact, there is often a significant difference between the code written by developers and the final running program, and the running results being consistent with the developer’s expectations is merely an “illusion”.

The reason for this discrepancy mainly comes from three aspects:

• Compiler optimizations
• CPU out-of-order execution
• CPU cache inconsistency

Let’s introduce them one by one.

Memory Reorder

Consider the following pseudo-code:

X = 0, Y = 0;

Thread 1:
X = 1; // ①
r1 = Y; // ②

Thread 2:
Y = 1;
r2 = X;

You might think that after this program executes, r1 and r2 cannot both be 0. But the fact is not so^[4].

This is due to the existence of “Memory Reorder”, which includes two types of reordering: compiler and processor.

This leads to the situation where the order of events in thread 1 is ① before ②, but for thread 2, it may see the result as ② before ①. Of course, thread 1 sees thread 2 the same way.

In fact, none of today’s hardware platforms provide a completely sequentially consistent memory model because doing so would be too inefficient.

Different compilers and processors have different preferences for Memory Reorder, but they all follow a certain principle: they cannot modify the behavior of a single-threaded program (Thou shalt not modify the behavior of a single-threaded program.^[5]). Based on this, they can perform various types of optimizations.

Compiler Optimizations

Take gcc as an example; this compiler provides the -o parameter to control many optimization options^[6].

Consider the following code:

int A, B;

void foo()
{
    A = B + 1;
    B = 0;
}

After compilation and optimization, it may become something like this:

int A, B;

void foo()
{
    int temp = B;
    B = 0;
    A = temp + 1;
}

Note that the compiler only needs to ensure that the execution results in a single-threaded environment remain the same. Therefore, this is permissible.

For the compiler, it knows the read and write of data and the dependencies among data within the current thread. However, the compiler does not know which data is shared between threads and may be modified. This requires developers to control it at the software level.

For compiler’s out-of-order optimization, developers are not completely unable to control it. The compiler provides a tool called memory barrier^[7] that allows developers to inform the compiler that this part of the code cannot be reordered during compilation.

The memory barrier in gcc is written as follows:

int A, B;

void foo()
{
    A = B + 1;
    asm volatile("" ::: "memory");
    B = 0;
}

Out-of-order Execution

Not only compilers, but processors may also execute instructions out of order.

Here is a table provided by Wikipedia that lists different types of CPUs and the types of reordering they might perform.

From this table, we can see that different CPU architectures have different preferences for Memory Reorder.

Most of the desktop and laptop computers we use are based on x86 architecture, while mobile devices like phones or tablets generally use ARM architecture. Comparatively, the former has much fewer types of reordering than the latter.

The x86 memory model is called x86-TSO (Total Store Order), which is probably one of the strongest memory models among processors.

The following image is a comparative relationship diagram provided in an article from Preshing on Programming^[8].

From this, we can infer that in a multi-threaded environment, if the code we write contains undefined behavior, these issues will be more easily exposed on mobile devices than on computers.

Regarding hardware memory models, those interested can continue to refer to the following links:

• Weak vs. Strong Memory Models^[9]
• This Is Why They Call It a Weakly-Ordered CPU^[10]
• A Tutorial Introduction to the ARM and POWER Relaxed Memory Models^[11]
• x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors^[12]

Similarly, processors also provide instructions for developers to control out-of-order execution. For example, the fence instruction on x86 and x86-64:

lfence (asm), void _mm_lfence(void)
sfence (asm), void _mm_sfence(void)
mfence (asm), void _mm_mfence(void)

This reminds us that if we only develop concurrent systems with a single-threaded mindset, introducing Memory Reorder can lead to issues. For example, using the variables A and B above, after the compiler reorders them, while it is fine for the current thread, if another thread happens to use these two variables and relies on their update order, problems may arise.

Cache Coherency

It is not that simple. Modern mainstream CPUs almost always contain multiple cores and multi-level caches. Below is the CPU cache information from my MacBook Pro.

If drawn as a structural diagram, it might look something like this:

Each CPU core, when running, will prioritize using the nearest cache. Once it hits, it directly uses the data in the cache. This is because cache is much faster than main memory (RAM). However, the caches between each core and between each level of cache are often inconsistent. Synchronizing this data takes time.

This creates a problem: if one CPU core modifies a piece of data, it does not synchronize to inform other cores, leading to data inconsistency.

All these reasons show us that the program running on the CPU and the code we write may not be consistent. Moreover, for the same execution, different threads may perceive the execution order of other threads differently.

Therefore, the memory model needs to consider all these details to allow developers to control precisely. Because all undefined behaviors can cause problems.

Objects and Memory Locations

The basic storage unit in the C++ memory model is the byte. A byte is at least large enough to contain any member of the basic execution character set as well as the eight-bit code units of Unicode UTF-8 encoding, and is composed of a continuous sequence of bits.

All data in C++ consists of objects.

Here, an object includes simple basic types (like int and double), as well as pointer types (like my_class*). Of course, it also includes objects of various class defined classes.

Regardless of the type, an object contains one or more memory locations. Each memory location must be one of the following two cases:

• Scalar type (Scalar Type) objects, which include the following:

• Numeric types: integers or floating-point numbers
• T * pointer types
• Enumeration types
• Pointer to members
• nullptr_t

• Adjacent bit fields^[13] maximum sequence

Bit Fields

Bit field declarations have an explicit size in bits for class data members. Adjacent bit field members can be packed together and cross over various bytes.

For example:

struct S {
 // Three-bit unsigned bit field,
 // Allowing values from 0 to 7
 unsigned int b : 3;
};

The value of a bit field must be greater than or equal to 0. The value 0 is special; it is only allowed on unnamed bit fields. It has a special meaning: it specifies that the next bit field in the class definition will begin at the boundary of the allocated unit.

Now, look at the following example:

struct S {
    char a;         // Memory location #1
    int  b : 5;     // Memory location #2
    int  c : 11,    // Memory location #2 (continuation, adjacent bit fields occupy the same memory location)
           : 0,     // Unnamed bit field, separating the next bit field
         d : 8;     // Memory location #3 (due to the presence of the 0 value unnamed bit field, this is a new memory location)
    struct {
        int ee : 8; // Memory location #4
    } e;
} obj;

We can see that this structure contains four memory locations.

The introduction of memory locations is closely related to the memory model.

If multiple threads access different memory locations, there will not be any problems. However, if they access the same memory location simultaneously, caution is required.

When multiple threads access the same memory location, and if at least one thread has a write operation, if these accesses do not have a consistent modification order, the result is undefined. In other words: bugs may occur.

Modification Order

We already know that data in C++ consists of objects. An object contains several memory locations.

Each object, from initialization to final destruction, must have a definite modification order for accesses performed on it during its lifecycle, which includes access operations from all threads.

Although this order may vary with each run of the program (for example: changes in CPU resources, the impact of the scheduler), for a specific run, there must be a “consistent order” that is recognized and visible to all threads.

For example: once a thread modifies a piece of data, this operation must be made visible to all threads, and after the modification operation, all threads should receive the modified value.

From the perspective of data types, there are two cases:

• For atomic types (see below): the compiler guarantees data synchronization.
• For non-atomic types: developers must ensure synchronization.

In the article “C++ Concurrency Programming”^[14], data synchronization for non-atomic type data is achieved through mutexes.

One of the difficulties in concurrent programming is identifying which data in the system is shared among threads and may be modified, and providing “reasonable” protection for them. This emphasis is important because protecting shared data is essentially countering the optimizations of the compiler and processor, so protection should not be excessive (we mentioned the granularity of locks when discussing concurrent programming).

We must minimize interference with the compiler and processor’s optimizations while ensuring correctness: for code that does not access shared data or is read-only for all threads, this part can be left for the compiler and processor to optimize.

Another point to clarify is that this states that there must be a clear modification order for each variable. However, this does not require all variables to have a global consistent order. This means that when looking at the access order of multiple variables together, different threads may see different orders.

You may find this hard to understand now, but as we proceed with the explanation, you will likely grasp its meaning better.

Relationship Terms

Next, let’s introduce a few relationship terms in the C++ memory model.

sequenced-before

Sequenced-before is a relationship in a single thread, which is an asymmetric and transitive pairwise relation.

For two operations A and B, if A sequenced-before B, then A’s execution should occur before B, and the result after A’s execution should be visible to B, introducing a local ordering.

Multiple statements within the same thread have a sequenced-before relationship, for example:

int i = 7; // ①
i++;       // ②

Here, ① sequenced-before ②.

However, there is no such relationship among multiple sub-expressions within the same statement. Particularly extreme, for the following statement:

i = i++ + i;

Since the two sub-expressions on the right side of the equal sign cannot determine the order, the behavior of this statement is undefined. This means you should never write such code.

happens-before

The happens-before relationship is an extension of the sequenced-before relationship, as it also includes relationships between different threads.

If A happens-before B, then the memory state of A will be visible before the execution of operation B, providing a guarantee for data access between threads.

Similarly, this is an asymmetric and transitive relationship.

If A happens-before B and B happens-before C, then it can be inferred that A happens-before C.

synchronizes-with

The synchronizes-with describes a state propagation relationship. If A synchronizes-with B, it guarantees that the state of operation A is visible before operation B is executed.

We will see below that atomic operations’ acquire-release have a synchronized-with relationship.

Additionally, the release and acquisition of locks and mutexes can achieve a synchronized-with relationship, and the completion of thread execution and join operations can also achieve a synchronized-with relationship.

Finally, through synchronizes-with, a happens-before relationship can be established.

Atomic Types and Atomic Operations

To understand the memory model, one must first grasp the atomic types and atomic operations provided by C++11.

Atomic types are not a class but a series of classes located in the <atomic> header file. Atomic types include atomic operations. However, there are also some atomic operations outside atomic types.

Here are the atomic types corresponding to basic types. The first column is the type alias (for ease of use), and the second column is the original definition of the type.

About volatile and atomic types: Both Java and C++ have the volatile keyword. However, the same keyword has different meanings in different languages. The volatile in Java has a similar meaning to atomic types in C++. The volatile in C++ prohibits the compiler from optimizing this variable.

Type Alias	Type Definition
atomic_bool	std::atomic
atomic_char	std::atomic
atomic_schar	std::atomic
atomic_uchar	std::atomic
atomic_int	std::atomic
atomic_uint	std::atomic
atomic_short	std::atomic
atomic_ushort	std::atomic
atomic_long	std::atomic
atomic_ulong	std::atomic
atomic_llong	std::atomic
atomic_ullong	std::atomic
atomic_char16_t	std::atomic<char16_t>
atomic_char32_t	std::atomic<char32_t>
atomic_wchar_t	std::atomic<wchar_t>

In addition to the above, there are more atomic types for integral types, see: cppreference std::atomic^[15].

“Atomic operations” as the name implies: the operation is either completed or not executed, and from any thread, no intermediate state can be observed. For example, in an atomic read operation: if another thread performs an atomic write operation, then the atomic read operation will either obtain the value before modification or the value after modification, but not a half-modified value.

Non-atomic types, on the other hand, behave differently. If an attempt is made to modify a non-atomic type object, other threads may see neither the value before modification nor the value after modification. Regarding this, in C++ concurrency programming, we have seen issues caused by non-atomic types.

It is important to note that all atomic types do not support copy and assignment. Because this operation involves two atomic objects: first reading the value from one atomic object and then writing it to another atomic object. However, a single operation on two different atomic objects cannot be atomic.

Different atomic types contain different atomic operations. The table below categorizes atomic types into four classes and lists the operations they support (for brevity, the atomic in the class name is replaced with #).

Function	#_flag	#_bool	Pointer Type	Integral Type	Description
test_and_set	Y	Sets flag to true and returns the original value
clear	Y	Sets flag to false
is_lock_free	Y	Y	Y	Checks if atomic variable is lock-free
load	Y	Y	Y	Returns the value of the atomic variable
store	Y	Y	Y	Sets the value of the atomic variable with a non-atomic variable’s value
exchange	Y	Y	Y	Replaces with a new value and returns the original value
compare_exchange_weak compare_exchange_strong	Y	Y	Y	Compares and changes value
fetch_add, +=	Y	Y	Increases value
fetch_sub, -=	Y	Y	Decreases value
++, —	Y	Y	Increments and decrements
fetch_or, |=	Y	Performs OR and assigns value
fetch_and, &=	Y	Performs AND and assigns value
fetch_xor, ^=	Y	Performs XOR and assigns value

Please note, there are no atomic operations for multiplication and division^[16].

atomic_flag

atomic_flag is the simplest atomic type, representing a boolean flag. It only contains two states: set (value set to true) or cleared (value set to false).

atomic_flag must be initialized with ATOMIC_FLAG_INIT, which will set it to the cleared state (this is the only option). Like this:

std::atomic_flag f = ATOMIC_FLAG_INIT;

After initialization, atomic_flag only supports the following two operations:

• test_and_set: Sets the value to true and returns the original value.
• clear: Clears, i.e., sets the value to false.

atomic_flag is too primitive to be used frequently. Typically, atomic_bool is a better choice.

is_lock_free

Besides atomic_flag, other atomic types support is_lock_free. This interface can be used to query whether atomic operations on this type of object are lock-free.

The standard requires that the atomic operations of atomic_flag are all lock-free, but whether other types are lock-free depends on the specific platform.

load, store, and exchange

Although atomic types do not support copy and assignment operations, they provide atomic operations for querying and setting values. Specifically:

• load: Atomically obtains the value of the atomic object.
• store: Atomically replaces the value of the atomic object with a non-atomic object.
• exchange: Atomically replaces the value of the atomic object and obtains the value it held previously.

Note that these three operations use and return non-atomic type values.

Compare and Change

compare_exchange_weak and compare_exchange_strong are two similar methods.

They both accept two input values: T& expected and T desired. These two methods will compare the actual value of the atomic variable with the provided expected value (expected), and if they are equal, the atomic variable’s value will be updated to the provided desired value (desired). Otherwise, the atomic variable’s value remains unchanged. If the atomic variable’s value has changed, it returns true; otherwise, it returns false.

This is where the two methods are the same. The difference lies in that on some machines lacking a single compare-and-swap instruction^[17], compare_exchange_weak may fail and return false even if the original value equals the expected value (expected), which is called a spurious failure.

Thus, calling compare_exchange_weak typically requires completing in a loop.

bool expected = false;extern atomic<bool> b; // set somewhere else while(!b.compare_exchange_weak(expected,true) && !expected);

On the other hand, compare_exchange_strong will only return false if the actual value is not equal to expected.

In comparison, compare_exchange_strong is more convenient to use. However, on some platforms, using compare_exchange_weak may be more efficient.

Pointer Atomic Types

The atomic type for a pointer of type T is std::atomic<T*>.

In addition to the operations introduced above, pointer atomic types also provide operations to adjust the pointer position by offset:

• fetch_add or +=: Increases by the specified value.
• fetch_sub or -=: Decreases by the specified value.
• ++ and --: Increments and decrements.

These operations are consistent with the ordinary operational logic we are familiar with, except that they are all atomic operations.

Integral Atomic Types

All operations supported by pointer atomic types are supported for integral atomic types as well. In addition, integral atomic types also support three logical operations: OR, AND, and XOR (eXclusive OR).

Please note that there are no atomic operations for multiplication and division^[18].

Additionally, it should be noted that among the operations supported by pointer atomic types and integral atomic types, all named functions (e.g., fetch_add, fetch_or) return the value before modification. In contrast, compound assignment operators (e.g., +=, |=) return the value after modification. Prefix and postfix increments and decrements behave like ordinary operations: ++x returns the new value, while x++ returns the old value.

Atomic Operations as Free Functions

All the operations we introduced above are located within atomic types.

However, there are also some atomic operations that are free functions and do not belong to any class. The reason for these functions’ existence is to maintain compatibility with C. These free functions only use pointers, not references.

These free functions include the following:

• atomic_is_lock_free
• atomic_store
• atomic_store_explicit
• atomic_load
• atomic_load_explicit
• atomic_exchange
• atomic_exchange_explicit
• atomic_compare_exchange_weak
• atomic_compare_exchange_weak_explicit
• atomic_compare_exchange_strong
• atomic_compare_exchange_strong_explicit
• atomic_fetch_add
• atomic_fetch_add_explicit
• atomic_fetch_sub
• atomic_fetch_sub_explicit
• atomic_fetch_and
• atomic_fetch_and_explicit
• atomic_fetch_or
• atomic_fetch_or_explicit
• atomic_fetch_xor
• atomic_fetch_xor_explicit
• atomic_flag_test_and_set
• atomic_flag_test_and_set_explicit
• atomic_flag_clear
• atomic_flag_clear_explicit

The meanings of these functions are similar to those of the atomic operations introduced earlier, and their corresponding relationships can be inferred from their names.

For detailed explanations of these functions, please refer to this link^[19], we will not elaborate further here.

memory_order

Regarding atomic operations, we have only discussed half of the content. The other half lies in an optional parameter supported by these operations.

All atomic operations included in atomic types, as well as free functions with the _explicit suffix, support an optional parameter of type std::memory_order. This parameter is an enumeration type, and its possible values are as follows:

typedef enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
} memory_order;

memory_order has six values, but memory_order_consume is somewhat special. Its semantics were modified in C++17, and the standard now does not recommend using it, so currently, no compiler implements it; you can temporarily ignore it until the C++20 standard is released.

First, not every memory_order is meaningful for every atomic operation. Their usage needs to be paired with specific operations.

We can categorize atomic operations into three types based on whether they read or write data: “Read”, “Write”, and “Read-Modify-Write” (read, modify, write). Below is the classification of these operations.

Operation	Read	Write	Read-Modify-Write
test_and_set	Y
clear	Y
is_lock_free	Y
load	Y
store	Y
exchange	Y
compare_exchange_strong	Y
compare_exchange_weak	Y
fetch_add, +=	Y
fetch_sub, -=	Y
fetch_or, |=	Y
++,–	Y
fetch_and, &=	Y
fetch_xor, ^=	Y

And for each category, the meaningful memory_order parameters are as follows.

Operation	Order
Read	memory_order_relaxed memory_order_consume memory_order_acquire memory_order_seq_cst
Write	memory_order_relaxed memory_order_release memory_order_seq_cst
Read-modify-write	memory_order_relaxed memory_order_acq_rel memory_order_seq_cst

For example, since store is a Write operation, it makes sense to specify memory_order_relaxed or memory_order_release or memory_order_seq_cst when calling store. However, specifying memory_order_acquire does not make sense.

When multiple threads contain multiple atomic operations, these atomic operations can lead to different strengths of the memory model at runtime due to their choice of memory_order. There are three situations, ranked from strong to weak:

• Sequential Consistency: abbreviated as seq-cst.
• Acquire and Release: abbreviated as acq-rel.
• Relaxed: loose model.

The latter two are only provided in the C++ memory model and are not available in other programming languages such as Java or C#.

Considering that these three terms currently do not have a consistent translation, we will still express them in English in the following text.

seq-cst Model

When using atomic operations without specifying memory_order, the default memory order memory_order_seq_cst will be used, so specifying or not specifying this value has the same effect when calling these functions.

This is the strictest memory model, seq-cst has two guarantees:

• The program’s instructions are consistent with the source code order
• All operations of all threads have a global order

This means that all code regarding atomic operations will not be reordered, and you can list all possible interleavings of threads, even if the results of each interleaving execution may differ. But for any single execution, its execution order must belong to one of these possibilities. Moreover, for a specific single execution, the order seen by all threads is consistent.

In this model, the order of all operations within each thread is visible to all threads. Therefore, it is the global synchronization of all threads.

This model is easy to understand, but its drawback is poor performance. Because to achieve sequential consistency, many measures must be taken to counter the optimizations of the compiler and CPU.

Consider the following code:

std::atomic<bool> x,y;
std::atomic<int> z;
void write_x_then_y(){
    x.store(true); // ①
    y.store(true); // ②
}
void read_y_then_x(){
    while(!y.load()); // ③
    if(x.load()) // ④
        ++z; // ⑤
}
int main(){
    x=false;
    y=false;
    z=0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load()!=0); // ⑥
}

In this code, several points are explained as follows:

1. In thread a, x is set to true first.
2. In thread a, y is then set to true.
3. In thread b, it first confirms that y is already true; if not, it continues to wait.
4. After confirming that y is true, it checks whether x is true.
5. If x is also true, it increments z.
6. The assert confirms that z will not be 0.

The assert in this code will never trigger. This is because the timing occurring in thread a will also synchronize to thread b.

The store and load operations on y establish a synchronized-with relationship. Therefore, we can obtain:

• ① happens-before ②
• ② happens-before ③
• ③ happens-before ④
• Thus, z will definitely increment
• And the start and join of threads can also form happens-before relationships, thus the assert will definitely not trigger.

We can describe this process with the following diagram:

acq-rel Model

Once sequential consistency is broken, the situation becomes complex. Next, let’s look at the acq-rel model.

memory_order_release corresponds to write operations, memory_order_acquire corresponds to read operations, and memory_order_acq_rel corresponds to both read and write.

Acquire and release operations on the same atomic variable will introduce a synchronizes-with relationship. Besides, there will no longer be a global consistent order.

The C++ standard describes it as follows:

An atomic operation A that performs a release operation on an atomic object M synchronized with an atomic operation B that performs an acquire operation on M and takes its value from any side effect in the release sequence headed by A.

The acq-rel model has the following guarantees:

• Atomic operations on the same object are not allowed to be reordered.
• Release operations prevent all read and write operations before it from being reordered with write operations after it.
• Acquire operations prevent all read operations before it from being reordered with read and write operations after it.

For the code above, the following write will also ensure that assert does not trigger:

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x_then_y()
{
    x.store(true, std::memory_order_relaxed); // ①
    y.store(true, std::memory_order_release); // ②
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_acquire)); // ③
    if(x.load(std::memory_order_relaxed))
        ++z;  // ④
}

int main()
{
    x=false;
    y=false;
    z=0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load()!=0); // ⑤
}

In this code, although the read and write of x use relaxed mode, the read and write of y use the release-acquire model. In this case,

• ② and ③ establish a synchronized-with relationship.
• At the same time, ① happens-before ②, and ③ happens-before ④
• Therefore, the execution order of ①, ②, ③, and ④ can be inferred.

This guarantees that assert will not trigger. Note here the bridging relationship between ② and ③.

Similarly, we can describe the logic here with the following diagram:

relaxed Model

When performing atomic operations, specifying memory_order_relaxed will use the relaxed model. This is the weakest memory model.

The only guarantee in this model is that there exists a globally consistent modification order for specific atomic variables, and no other guarantees exist. This means that even with the same code, different threads may see different execution orders.

For example, using a similar code snippet, but this time we specify the memory_order of atomic operations as memory_order_relaxed.

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x_then_y()
{
    x.store(true, std::memory_order_relaxed); // ①
    y.store(true, std::memory_order_relaxed); // ②
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_relaxed)); // ③
    if(x.load(std::memory_order_relaxed)) // ④
        ++z;  // ⑤
}

int main()
{
    x=false;
    y=false;
    z=0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load()!=0); // ⑥
}

This time we may not be so lucky, because the assert is possible to trigger.

The reason is that for the above code, even if thread a believes that x has been set to true before y, for thread b, it does not necessarily see the same result; after confirming that y is true, it may still see x as false, thus the ++z operation at line ③ does not execute, leading to the assert triggering.

From the perspective of atomic variable y, even though the logic of this code guarantees the order ② => ③ => ④, the order of the read and write of x in thread a will not synchronize to thread b. Therefore, thread a may see the execution order as ①②③④, while thread b sees it as ②①③④. This is what we mentioned earlier about the “modification order” not requiring all variables to have a global consistent order.

If we were to diagram the flow of this code, it would look like this:

Threads a and b execute in parallel, and events occurring in thread a do not require synchronization to thread b.

To summarize, regarding memory_order_relaxed:

• Even though all operations are atomic, all events do not require a global order
• Within the same thread, there are happens-before rules, but between threads, different orders may be perceived

Additionally, it should be noted that the occurrence of problems here is only a theoretical possibility. If you compile and run the above code snippet, you will probably not encounter the problem even after running it 100 times. However, this does not mean the problem does not exist; it is just very unlikely to occur. This is precisely one of the reasons why concurrent systems are difficult to develop: many issues do not appear most of the time, and when they do occur rarely, they are hard to understand.

The relaxed model has too few constraints, so it often needs to be used in conjunction with the fences mentioned later; examples will be seen later.

Model Selection

Once we know the three models, it is natural to consider how to choose.

In most cases, the seq-cst model should be a better choice because it is the easiest to understand.

However, if one seeks higher performance, then relaxed or rel-acq models should be considered. Of course, the premise is that you must have enough grasp of them. Because correctness of the program is obviously more important than high efficiency. If the program has bugs, then its efficiency is meaningless.

The following code simply compares the performance of seq-cst and relaxed models:

#include <atomic>
#include <chrono>
#include <iostream>
#include <thread>

const int kLoopCount = 100000000;

using namespace std;

void increment(atomic<int>* value, memory_order order) {
    for (int i = 0; i < kLoopCount; i++) {
       value->fetch_add(1, order);
    }
}

void thread_worker(atomic<int>* value, memory_order order) {
    thread t1(increment, value, order);
    thread t2(increment, value, order);
    thread t3(increment, value, order);
    t1.join();
    t2.join();
    t3.join();
}

int main() {

    atomic<int> a(0);
    atomic<int> b(0);

    auto start = chrono::steady_clock::now();
    thread_worker(&a, memory_order_relaxed);
    auto end = chrono::steady_clock::now();
    auto time1 = chrono::duration_cast<chrono::milliseconds>(end - start);

    start = chrono::steady_clock::now();
    thread_worker(&b, memory_order_seq_cst);
    end = chrono::steady_clock::now();
    auto time2 = chrono::duration_cast<chrono::milliseconds>(end - start);

    cout << "Relaxed order cost " << time1.count() << "ms" << endl;
    cout << "Seq_cts order cost " << time2.count() << "ms" << endl;

    return 0;
}

Here we create three threads to perform an atomic variable increment operation by +1 each time. One uses memory_order_relaxed, the other uses memory_order_seq_cst. The time consumption of a certain run is compared as follows:

Relaxed order cost 7468ms
Seq_cts order cost 7641ms

As seen, the time consumption difference is minimal.

Of course, this performance will depend on many factors; results may vary across different platforms and different project complexities, reminding us to choose which model based on specific situations. Purely pursuing a slight performance increase while adding significant programming complexity may be irrational.

Premature optimization is the root of all evil. (过早的优化是万恶之源.) – Donald Knuth

Fence

When discussing Memory Reorder, we mentioned memory barriers.

Both compilers and processors provide developers with means to control out-of-order optimizations, but these means are platform-dependent and lack portability.

C++, as a cross-platform programming language, also provides corresponding mechanisms. Since C++11, the following two mechanisms have been provided:

• std::atomic_thread_fence: Synchronization of data access between threads
• std::atomic_signal_fence: Synchronization between threads and signal handlers

In this article, we will focus only on atomic_thread_fence. The translation of the word Fence in Chinese is “栅栏”, which acts like a barrier, preventing the code before and after it from crossing.

There are three types of fences:

• full fence: specifies memory_order_seq_cst or memory_order_acq_rel.
• acquire fence: specifies memory_order_acquire.
• release fence: specifies memory_order_release.

Different types of fences provide different protections against reordering. We can divide the interleaving of reads and writes into the following four situations:

• ① Load-Load: read followed by read
• ② Load-Store: read followed by write
• ③ Store-Load: write followed by read
• ④ Store-Store: write followed by write

The effects achieved by the three types of fences are as follows:

• Full fence can prevent the first, second, and fourth cases, but cannot prevent the third case.

It might be easier to understand through the following diagram, where the red diagonal lines indicate that this type of reordering will be prohibited.

• Acquire fence prevents all read operations before it from being reordered with read and write operations after it. The diagram is as follows:

• Release fence prevents all read and write operations before it from being reordered with write operations after it, as illustrated below:

Please note: None of the three types of fences will prevent reordering of write followed by read.

Reviewing the code in the relaxed model, the reason issues occurred there is that the write operations for x and y in thread a may be reordered. As long as we prevent this reordering from happening, the problems will not occur.

To do this, we can modify the code as follows:

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x_then_y()
{
    x.store(true, std::memory_order_relaxed); // ①
    std::atomic_thread_fence(std::memory_order_release);
    y.store(true, std::memory_order_relaxed); // ②
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_relaxed)); // ③
    std::atomic_thread_fence(std::memory_order_acquire);
    if(x.load(std::memory_order_relaxed))
        ++z;  // ④
}

Here we still retain the original read and write operations with memory_order_relaxed. However, we added a fence between the original ① and ②, as well as between ③ and ④. Moreover, we used memory_order_release and memory_order_acquire to block the reordering of the preceding and following code, thus preventing the occurrence of problems.

Mutex and Barriers

Previously, we introduced the mutex mutex: the thread that acquires the mutex lock will have the exclusive qualification to enter the critical section.

Besides ensuring mutual exclusion, the locking and unlocking of mutex also act as a “barrier”. Because the code within the barrier cannot be optimized out of order (but it does not guarantee that content outside the barrier will enter into the barrier).

In the three situations illustrated below, the first situation may be optimized into the second. However, the second situation will not be optimized into the third:

Conclusion

Thus, we have covered the content regarding C++ concurrency programming and the memory model.

Of course, fully understanding them is not an easy task. Understanding the theory is one thing; combining it with practical project experience is essential for better grasping them.

The following image roughly outlines the core concepts of the memory model, which can help us quickly review in the future.

This is just the starting point of our understanding of concurrent programming. To gain a deeper understanding of this content, you can explore more resources provided in the links below.

References

[1]

“An Introduction to Lock-Free Programming”: https://preshing.com/20120612/an-introduction-to-lock-free-programming/

[2]

Memory Model: https://en.wikipedia.org/wiki/Java_memory_model

[3]

JSR-133: https://download.oracle.com/otndocs/jcp/memory_model-1.0-pfd-spec-oth-JSpec/

[4]

Not so: https://preshing.com/20120515/memory-reordering-caught-in-the-act/

[5]

Thou shalt not modify the behavior of a single-threaded program.: https://preshing.com/20120625/memory-ordering-at-compile-time/

[6]

Many optimization options: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

[7]

Memory Barrier: https://stackoverflow.com/questions/286629/what-is-a-memory-fence

[8]

Preshing on Programming: https://preshing.com/

[9]

Weak vs. Strong Memory Models: https://preshing.com/20120930/weak-vs-strong-memory-models/

[10]

This Is Why They Call It a Weakly-Ordered CPU: https://preshing.com/20121019/this-is-why-they-call-it-a-weakly-ordered-cpu/

[11]

A Tutorial Introduction to the ARM and POWER Relaxed Memory Models: https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

[12]

x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors: https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf

[13]

Bit field: https://en.cppreference.com/w/cpp/language/bit_field

[14]

“C++ Concurrency Programming”: https://paul.pub/cpp-concurrency/

[15]

cppreference std::atomic: https://en.cppreference.com/w/cpp/atomic/atomic

[16]

There are no atomic operations for floating point types: https://stackoverflow.com/questions/20981007/atomic-operations-on-floats

[17]

Compare-and-swap instruction: https://en.wikipedia.org/wiki/Compare-and-swap

[18]

There are no atomic operations for multiplication and division: https://stackoverflow.com/questions/9824951/why-dont-stdatomicintegral-specializations-provide-multiplication-and-divis

[19]

This link: https://en.cppreference.com/w/cpp/header/atomic

Author: Paul’s Bar

https://paul.pub/cpp-memory-model/

– EOF –

Recommended Reading Click the title to jump

1. Value Categories in C++

2. How Does the Linux File System Work?

3. The Most Stable C/C++ Learning Path in 2021

Follow “CPP Developers”

Read selected C++ technical articles. Join the exclusive circle of C++ developers

Likes and views are the biggest support❤️