聊聊 内存模型与内存序

本文始发于公众号【高性能架构探索】，本公众号致力于分享干货、硬货以及工作上的bug分析。

原文链接如下：
https://mp.weixin.qq.com/s/t5_Up2YZEZt1NLbvgYz9FQ

最近群里聊到了Memory Order相关知识，恰好自己对这块的理解是模糊的、无序的，所以借助本文，重新整理下相关知识。

写在前面

在真正了解Memory Model的作用之前，曾经简单地将Memory Order等同于mutex和atomic来进行线程间数据同步，或者用来限制线程间的执行顺序，其实这是一个错误的理解。直到后来仔细研究了Memory Order之后，才发现无论是功能还是原理，Memory Order与他们都不是同一件事。实际上，Memory Order是用来用来约束同一个线程内的内存访问排序方式的，虽然同一个线程内的代码顺序重排不会影响本线程的执行结果（如果结果都不一致，那么重排就没有意义了），但是在多线程环境下，重排造成的数据访问顺序变化会影响其它线程的访问结果。

正是基于以上原因，引入了内存模型。C++的内存模型解决的问题是如何合理地限制单一线程中的代码执行顺序，使得在不使用锁的情况下，既能最大化利用CPU的计算能力，又能保证多线程环境下不会出现逻辑错误。

指令乱序

现在的CPU都采用的是多核、多线程技术用以提升计算能力；采用乱序执行、流水线、分支预测以及多级缓存等方法来提升程序性能。多核技术在提升程序性能的同时，也带来了执行序列乱序和内存序列访问的乱序问题。与此同时，编译器也会基于自己的规则对代码进行优化，这些优化动作也会导致一些代码的顺序被重排。

首先，我们看一段代码，如下：

int A = 0;
int B = 0;

void fun() {
    A = B + 1; // L5
    B = 1; // L6
}

int main() {
    fun();
    return 0;
}

如果使用 g++ test.cc，则生成的汇编指令如下：

movl    B(%rip), %eax
addl    $1, %eax
movl    %eax, A(%rip)
movl    $1, B(%rip)

通过上述指令，可以看到，先把B放到eax，然后eax+1放到A，最后才执行B + 1。

而如果我们使用g++ -O2 test.cc，则生成的汇编指令如下：

movl    B(%rip), %eax
movl    $1, B(%rip)
addl    $1, %eax
movl    %eax, A(%rip)

可以看到，先把B放到eax，然后执行B = 1，再执行eax + 1，最后将eax赋值给A。从上述指令可以看出执行B赋值(语句L6)语句先于A赋值语句(语句L5)执行。

我们将上述这种不按照代码顺序执行的指令方式称之为指令乱序。

对于指令乱序，这块需要注意的是：编译器只需要保证在单线程环境下，执行的结果最终一致就可以了，所以，指令乱序在单线程环境下完全是允许的。对于编译器来说，它只知道：在当前线程中，数据的读写以及数据之间的依赖关系。但是，编译器并不知道哪些数据是在线程间共享，而且是有可能会被修改的。而这些是需要开发人员去保证的。

那么，指令乱序是否允许开发人员控制，而不是任由编译器随意优化？

可以使用编译选项停止此类优化，或者使用预编译指令将不希望被重排的代码分隔开，比如在gcc下可用asm volatile，如下：

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

类似的，处理器也会提供指令给开发人员使用，以避免乱序控制，例如，x86，x86-64上的指令如下：

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

为什么需要内存模型

多线程技术是为了最大限度的压榨cpu，提升计算能力。在单核时代，多线程的概念是在宏观上并行，微观上串行，多线程可以访问相同的CPU缓存和同一组寄存器。但是在多核时代，多个线程可能执行在不同的核上，每个CPU都有自己的缓存和寄存器，在一个CPU上执行的线程无法访问另一个CPU的缓存和寄存器。CPU会根据一定的规则对机器指令的内存交互进行重新排序，特别是允许每个处理器延迟存储并且从不同位置装载数据。与此同时，编译器也会基于自己的规则对代码进行优化，这些优化动作也会导致一些代码的顺序被重排。这种指令的重排，虽然不影响单线程的执行结果，但是会加剧多线程访问共享数据时的数据竞争（Data Race）问题。

以上节例子中的A、B两个变量为例，在编译器将其乱序后，虽然对于当前线程是没问题的。但是在多线程环境下，如果其它线程依赖了A 和 B，会加剧多线程访问共享数据的竞争问题，同时可能会得到意想不到的结果。

正是因为指令乱序以及多线程环境数据竞争的不确定性，我们在开发的时候，经常会使用信号量或者锁来实现同步需求，进而解决数据竞争导致的不确定性问题。但是，加锁或者信号量是相对接近操作系统的底层原语，每一次加锁或者解锁都有可能导致用户态和内核态的互相切换，这就导致了数据访问开销，如果锁使用不当，可能会造成严重的性能问题，所以就需要一种语言层面的机制，既没有锁那样的大开销，又可以满足数据访问一致性的需求。2004年，Java5.0开始引入适用于多线程环境的内存模型，而C++直到C++11才开始引入。

Herb Sutter在其文章中这样来评价C++11引入的内存模型：

The memory model means that C++ code now has a standardized library to call regardless of who made the compiler and on what platform it's running. There's a standard way to control how different threads talk to the processor's memory.

"When you are talking about splitting [code] across different cores that's in the standard, we are talking about the memory model. We are going to optimize it without breaking the following assumptions people are going to make in the code," Sutter said

从内容可以看出，C++11引入Memory model的意义在于有了一个语言层面的、与运行平台和编译器无关的标准库，可以使得开发人员更为便捷高效的控制内存访问顺序。

一言以蔽之，引入内存模型的原因，有以下几个原因：

• 编译器优化：在某些情况下，即使是简单的语句，也不能保证是原子操作
• CPU out-of-order：CPU为了性能，可能会调整指令的执行顺序
• CPU Cache不一致：在CPU Cache的影响下，在某个CPU下执行了指令，不会立即被其它CPU所看到

关系术语

为了便于更好的理解后面的内容，我们需要理解几种关系术语。

sequenced-before

sequenced-before是一种单线程上的关系，这是一个非对称，可传递的成对关系。

在了解sequenced-before之前，我们需要先看一个概念evaluation(求值)。

对一个表达式进行求值(evaluation)，包含以下两部分：

• value computations: calculation of the value that is returned by the expression. This may involve determination of the identity of the object (glvalue evaluation, e.g. if the expression returns a reference to some object) or reading the value previously assigned to an object (prvalue evaluation, e.g. if the expression returns a number, or some other value)
• Initiation of side effects: access (read or write) to an object designated by a volatile glvalue, modification (writing) to an object, calling a library I/O function, or calling a function that does any of those operations.

上述内容简单理解就是，value computation就是计算表达式的值，side effect就是对对象进行读写。

对于C++来说，语言本身并没有规定表达式的求值顺序，因此像是f1() + f2() + f3()这种表达式，编译器可以决定先执行哪个函数，之后再按照加法运算的规则从左边加到右边，因此编译器可能会优化成为(f1() + f2()) + f(3)，但f1() + f2()和f3()都可以先执行。

经常可以看到如下这种代码：

i = i++ + i;

正是因为语言本身没有规定表达式的求值顺序，所以上述代码中两个子表达式(i++和i)无法确定先后顺序，因此这个语句的行为是未定义的。

sequenced-before就是对在同一个线程内，求值顺序关系的描述：

• 如果A sequenced-before B，代表A的求值会先完成，才进行对B的求值
• 如果A not sequenced-before B，而B sequenced-before A，则代表先对B进行求值，然后对A进行求值
• 如果A not sequenced-before B，而B not sequenced-before A，则A和B都有可能先执行，甚至可以同时执行

happens-before

happens-before是sequenced-before的扩展，因为它还包含了不同线程之间的关系。当A操作happens-before B操作的时候，操作A先于操作B执行，且A操作的结果对B来说可见。

看下cppreference对happens-before关系的定义，如下：

Regardless of threads, evaluation A happens-before evaluation B if any of the following is true:

\1) A is sequenced-before B

\2) A inter-thread happens before B

从上述定义可以看出，happens-before包含两种情况，一种是同一线程内的happens-before关系(等同于sequenced-before)，另一种是不同线程的happens-before关系。

对于同一线程内的happens-before，其等同于sequenced-before，所以在此忽略，着重讲下线程间的happens-before关系。

假设有一个变量x，其初始化为0，如下：

int x = 0;

此时有两个线程同时运行，线程A进行++x操作，线程B打印x的值。因为这两个线程不具备happens-before关系，也就是说没有保证++x操作对于打印x的操作是可见的，因此打印的值有可能是0，也有可能是1。

对于这种场景，语言本身必须提供适当的手段，可以使得开发人员能够在多线程场景下达到happens-before的关系，进而得到正确的运行结果。这也就是上面说的第二点A inter-thread happens before B。

C++中定义了5种能够建立跨线程的happens-before的场景，如下：

• A synchronizes-with B
• A is dependency-ordered before B
• A synchronizes-with some evaluation X, and X is sequenced-before B
• A is sequenced-before some evaluation X, and X inter-thread happens-before B
• A inter-thread happens-before some evaluation X, and X inter-thread happens-before B

synchronizes-with

synchronized-with描述的是不同线程间的同步关系，当线程A synchronized-with线程B的时，代表线程A对某个变量或者内存的操作，对于线程B是可见的。换句话说，synchronized-with就是跨线程版本的happens-before。

假设在多线程环境下，线程A对变量x进行x = 1的写操作，线程B读取x的值。在未进行任何同步的条件下，即使线程A先执行，线程B后执行，线程B读取到的x的值也不一定是最新的值。这是因为为了让程序执行效率更高编译器或者CPU做了指令乱序优化，也有可能A线程修改后的值在寄存器内，或者被存储在CPU cache中，还没来得及写入内存 。正是因为种种操作 ，所以在多线程环境下，假如同时存在读写操作，就需要对该变量或者内存做同步操作。

所以，synchronizes-with是这样一种关系，它可以保证线程A的写操作结果，在线程B是可见的。

在2014年C++的官方标准文件（Standard for Programming Language C++）N4296的第12页，提示了C++提供的同步操作，也就是使用atomic或mutex：

The library defines a number of atomic operations and operations on mutexes that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another.

memory_order

C++11中引入了六种内存约束符用以解决多线程下的内存一致性问题(在头文件《P0371R1: Temporarily discourage memory_order_consume》

memory_order_acq_rel

Acquire-Release模型中的其它三个约束符，要么用来约束读，要么用来约束写。那么如何对一个原子操作中的两个动作执行约束呢？这就要用到 memory_order_acq_rel，它既可以约束读，也可以约束写。

对于使用memory_order_acq_rel约束符的原子操作，对当前线程的影响就是：当前线程T1中此操作之前或者之后的内存读写都不能被重新排序（假设此操作之前的操作为操作A，此操作为操作B，此操作之后的操作为B，那么执行顺序总是ABC，这块可以理解为同一线程内的sequenced-before关系）；对其它线程T2的影响是，如果T2线程使用了memory_order_release约束符的写操作，那么T2线程中写操作之前的所有操作均对T1线程可见；如果T2线程使用了memory_order_acquire约束符的读操作，则T1线程的写操作对T2线程可见。

理解起来可能比较绕，这个标记相当于对读操作使用了memory_order_acquire约束符，对写操作使用了memory_order_release约束符。当前线程中这个操作之前的内存读写不能被重排到这个操作之后，这个操作之后的内存读写也不能被重排到这个操作之前。

cppreference中使用了3个线程的例子来解释memory_order_acq_rel约束符，代码如下：

#include 
#include 
#include 
#include 
 
std::vector data;
std::atomic flag = {0};
 
void thread_1() {
    data.push_back(42); // L10
    flag.store(1, std::memory_order_release); // L11
}
 
void thread_2() {
    int expected=1; // L15
    // memory_order_relaxed is okay because this is an RMW,
    // and RMWs (with any ordering) following a release form a release sequence
    while (!flag.compare_exchange_strong(expected, 2, std::memory_order_relaxed)) { // L18
        expected = 1;
    }
}
 
void thread_3() {
    while (flag.load(std::memory_order_acquire) < 2); // L24
    // if we read the value 2 from the atomic flag, we see 42 in the vector
    assert(data.at(0) == 42); // L26
}
 
int main() {
    std::thread a(thread_1);
    std::thread b(thread_2);
    std::thread c(thread_3);
    a.join(); 
    b.join(); 
    c.join();
    
    return 0;
}

线程thread_2中，对原子变量flag的compare_exchange操作使用了memory_order_acq_rel约束符，这就意味着L15不能重排到L18之后，也就是说当compare_exchange操作发生的时候，能确保expected的值是1，使得这个 compare_exchange_strong操作能够完成将flag替换成2的动作；thread_1线程中对flag使用了带memory_order_release约束符的store，这意味着当thread_2线程中取flag的值得时候，L10已经完成（不会被重排到L11之后）。当thread_2线程compare_exchange操作将2写入flag的时候，thread_3线程中带memory_order_acquire标记的load操作能看到L18之前的内存写入，自然也包括L10的内存写入，所以L26的断言始终是成立的。

上面例子中，memory_order_acq_rel约束符用于同时存在读和写的场景，这个时候，相当于使用了memory_order_acquire&memory_order_acquire组合组合。其实，它也可以单独用于读或者单独用于写，示例如下：

// Thread-1:
a = y.load(memory_order_acq_rel); // A
x.store(a, memory_order_acq_rel); // B

// Thread-2:
b = x.load(memory_order_acq_rel); // C
y.store(1, memory_order_acq_rel); // D

再看另外一个实例：

// Thread-1:                              
a = y.load(memory_order_acquire); // A
x.store(a, memory_order_release); // B

// Thread-2:
b = x.load(memory_order_acquire); // C
y.store(1, memory_order_release); // D

上述两个示例，效果完全一样，都可以保证A先于B执行，C先于D执行。

总结

C++11提供的6种内存访问约束符中：

• memory_order_release：在当前线程T1中，该操作X之前的任何读写操作指令都不能放在操作X之后。如果其它线程对同一变量使用了memory_order_acquire或者memory_order_consume约束符，则当前线程写操作之前的任何读写操作都对其它线程可见(注意consume的话是依赖关系可见)

• memory_order_acquire：在当前线程中，load操作之后的依赖于此原子变量的读和写操作都不能被重排到当前指令前。如果有其他线程使用memory_order_release内存模型对此原子变量进行store操作，在当前线程中是可见的。

• memory_order_relaxed：没有同步或顺序制约，仅对此操作要求原子性

• memory_order_consume：在当前线程中，load操作之后的依赖于此原子变量的读和写操作都不能被重排到当前指令前。如果有其他线程使用memory_order_release内存模型对此原子变量进行store操作，在当前线程中是可见的。

• memory_order_acq_rel：等同于对原子变量同时使用memory_order_release和memory_order_acquire约束符

• memory_order_seq_cst：从宏观角度看，线程的执行顺序与代码顺序严格一致

C++的内存模型则是依赖上面六种内存约束符来实现的：

• Relax模型：对应的是memory_order中的memory_order_relaxed。从其字面意思就能看出，其对于内存序的限制最小，也就是说这种方式只能保证当前的数据访问是原子操作(不会被其他线程的操作打断)，但是对内存访问顺序没有任何约束，也就是说对不同的数据的读写可能会被重新排序
• Acquire-Release模型：对应的memory_order_consume memory_order_acquire memory_order_release memory_order_acq_rel约束符(需要互相配合使用)；对于一个原子变量A，对A的写操作(Release)和读操作(Acquire)之间进行同步，并建立排序约束关系，即对于写操作(release)X，在写操作X之前的所有读写指令都不能放到写操作X之后；对于读操作(acquire)Y，在读操作Y之后的所有读写指令都不能放到读操作Y之前。
• Sequential consistency模型：对应的memory_order_seq_cst约束符；程序的执行顺序与代码顺序严格一致，也就是说，在顺序一致性模型中，不存在指令乱序。

下面这幅图大致梳理了内存模型的核心概念，可以帮我们快速回顾。

后记

这篇文章断断续续写了一个多月，中间很多次都想放弃。不过，幸好还是咬牙坚持了下来。查了很多资料，奈何因为知识储备不足，很多地方都没有理解透彻，所以文章中可能存在理解偏差，希望友好交流，共同进步。

在写文的过程中，深切体会到了内存模型的复杂高深之处，C++的内存模型为了提供足够的灵活性和高性能，将各种约束符都暴露给了开发人员，给高手足够的发挥空间，也让新手一脸茫然。

好了，今天的文章就到这，我们下期见！