旭穹の陋室

线程和数据竞争

当一个表达式（expression）的求值（evaluation）写入一个内存地址，而另一个求值读取或修改同一内存地址时，这些表达式被称为冲突（conflict）。具有两个冲突求值的程序具有数据竞争（data race），除非：

• 两个求值操作都在同一线程或同一信号处理程序（signal handler）中执行；
• 两个冲突的求值操作都是原子操作；
• 其中一个冲突的求值操作发生在另一个之前（引入内存顺序（std::memory_order）概念，另外也可通过加锁解决）；

当出现数据竞争时，程序的表现是未定义的。

内存顺序究竟解决了什么问题？

首先上个暴论：即便目前大多数资料（包括官方文档）中给出的示例都是关于多线程的，但是内存顺序其实不是限制多线程之间的指令的执行顺序。而是规定单个线程内的指令如何排序的。

是的，内存排序模型本身与多线程无关，而是限制单一线程中的指令执行顺序。但是指令执行顺序的（合理地）重排在单线程环境下不会造成逻辑错误，而在多线程环境下（可能）会，所以需要对重排进行限制。

让我从一个实际的例子逐步展开：

int x = 0;
// thread 1:
x++;
// thread 2:
x++;

对于非原子操作x++，编译之后对应3条汇编指令：

• mov（从内存到寄存器）
• add（加法）
• mov（从寄存器到内存）

由于操作本身不是原子的，在多线程环境下，就可能出现：线程1刚执行完add，还未将值写回内存时，线程2开始执行从内存到寄存器的mov操作，这样线程2就看不到线程1的执行结果。从而使得最终x的结果为1。

如果我们想要避免这种情况，就需要用到上面提到的原子操作。这样整个x++操作为一个整体，逻辑上不可分割，从而解决了线程间同步的问题。但到这里其实还没内存顺序什么事。

在进一步展开之前，我们要先明确代码执行过程发生的两次重排：

• 编译器指令重排：编译器编译（特别是开了优化之后），汇编指令的执行顺序并不一定严格按照高级语言代码中的顺序，而是以编译器的优化规则而基准，在不破坏代码逻辑的情况下，进行了一定程度的重排。
• CPU指令重排（乱序发射）：如果仅仅只有编译器指令重排，两个线程（相同的回调函数）的指令执行顺序虽然可能跟源代码不同，但两个线程之间应该是相同的（因为执行相同的机器码）。但实际上，在CPU层面看，两个线程的指令执行顺序是不一定一致的，甚至，同一线程的不同次执行之间的执行顺序也可能不一致。这都归功于现代CPU的多发射和乱序执行。

现在知道了重排的存在，我们考虑如下这种情况：

#include <atomic>
#include <cassert>
#include <thread>

std::atomic<bool> f = false;
std::atomic<bool> g = false;
// thread 1:
void th1_func() {
    f.store(true, std::memory_order_relaxed);		// [1]
    g.store(true, std::memory_order_relaxed);		// [2] 
}
// thread 2:
void th2_func() {
    while (!g.load(std::memory_order_relaxed))		// [3]
        ;
    assert(f.load(std::memory_order_relaxed));		// [4]
}

int main() {
    for (int i = 0; i < 1e6; ++i) {
        f = false;
        g = false;
        std::thread th1(th1_func);
        std::thread th2(th2_func);
        th1.join();
        th2.join();
    }
}

先不考虑std::memory_order_relaxed究竟是什么，可以简单的认为对内存访问指令的排序施加最小程度的限制。那么。你是否会觉得assert永远都不会触发，即f一定为true？

如果你的答案为是，那么你一定深信操作 [1] 一定先于操作 [2] 完成，所以当能够执行操作 [4] 时，f一定为true。然而，操作 [1] 和操作 [2] 的执行顺序是可能发生重排的。显然，这种重排虽然是发生在单个线程之中，但其确实会影响到多线程下程序的逻辑。

是的，我成功触发了断言，在M1的Mac上（x86是强内存模型，目前未触发过），使用如下的CMakeLists.txt：

cmake_minimum_required(VERSION 3.10)
project(MemoryOrder)
SET(CMAKE_BUILD_TYPE Debug)
SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++20 -O3")
add_executable(MemoryOrder main.cpp)

Assertion failed: (f.load(std::memory_order_relaxed)), function th2_func, file main.cpp, line 16.
[1] 14901 abort ./MemoryOrder

如果看到这里，你还能保持清醒，那么你应该对内存顺序有了一个基本的理解了。概括的讲，内存顺序的几种模型就是对内存访问指令的执行顺序施加一定的限制，这种限制，决定了以atomic操作为基准点，其前后的内存访问指令能够以多大的自由度进行重排，从而不会导致多线程环境下的程序逻辑错误。

内存的Consistency和Coherence

在描述内存体系结构的概念术语中，有两个常见的概念：Consistency和Coherence，它们都可以被翻译成一致性、连续性。但是，这两个概念想表达的问题是不同的，经常容易混淆。

Consistency

Consistency描述的一致性是指多个Master设备读写同一块内存区域时的顺序一致性。即约定了读写操作的将以何种执行顺序被所有的Master观察到。

• 这里的多个Master设备可以是共享内存的CPU和GPU，也可以是CPU中的不同核心；
• 对于Consistency问题，硬件只提供解决机制，需要由软件自行选择使用何种机制来保证Consistent；
• 我们软件编程中关心的内存顺序问题其实多说都是Consistency问题；

Coherence

Coherence描述的一致性是指当一个内存区域有多份拷贝时的数据一致性。即约定了读操作最终会读到什么数据。

• 这里的多份拷贝可能有几种情况：
  • 最常见的情况就是每个CPU核心有自己的Cache，Master A准备写入主内存M中位于地址P的数据D可能被先缓存到A的Cache中，这时Master B如果直接从主内存中读取数据D，就可能拿到旧值；
  • 另外就是不同线程都对同一内存数据D做写操作，数据D在不同的寄存器中也会有多份拷贝，且值不尽相同，在它们被写回主存前，读取数据D也会存在数据一致性问题。
• 这里最终的含义是指对某内存数据D的修改，迟早都会对所有的Master可见，但具体是什么时候什么条件下，你能确定读到修改的结果，Coherence未做约束。
• 满足以下三个条件的内存系统是coherent的：
  • 单Master中的程序次序（program order）：对同一地址P的内存数据D，若Master A写操作之后没有其他Master再执行写操作，那么A的读操作总能返回A之前写入的值；
  • 最终可见：对同一地址P的内存数据D，Master A完成写操作之后，Master B执行读操作。若两者相隔时间足够长，且没有其他Master再执行写操作，那么B的读操作可以获得A写入的值；
  • 写串行化（write serialization）：即不同Master对同一地址P的内存数据D的写操作，在所有master看来，都是以相同的次序进行的。比如Master A先写入值1，Master B后写入值2，则对所有Master，不能先读到值2，再读到值1。
• 一般Coherence问题，由硬件保证正确性，不需要软件控制；

Sequenced-before

同一线程之内，操作A的执行顺序在操作B前面，那么就称为A sequenced-before B。它不仅仅表示两个操作之间的先后顺序，还表示了操作结果之间的可见性关系。两个操作A和操作B，如果有A sequenced-before B，除了表示操作A的顺序在B之前，还表示了操作A的结果操作B可见。

Carries dependency

同一线程之内，操作A sequenced-before B，且操作B的计算依赖于A的结果，则称A carries dependency into B。所谓依赖的方式有以下三种：

• A的值是B表达式的一部分，除了：
  • B是对std::kill_dependency的调用；
  • A是内置操作符&&、||、?:、,的左操作数；
• A写入标量对象M，B从M读取；
• 传递性：A carries dependency into 另一个操作X，X carries dependency into B；

Modification order

对于所有原子操作，保证满足以下四项要求：

• 写-写一致性（Write-write coherence）：如果一个修改某个原子M的表达式 A happens-before 另一个修改M的表达式B，则对于M的Modification order而言，A早于B；
• 读-读一致性（Read-read coherence）：如果一个读取原子M用于计算的表达式A happens-before 另一个读取原子M用于计算的表示式B，假设A的值依赖于对M的写操作X，则B的值要么同样依赖于写操作X，要么依赖于对M的副作用（side effect）Y（写），对于M的Modification order而言，Y晚于X；
• 读-写一致性（Read-write coherence）：如果一个读取原子M用于计算的表达式A happens-before 另一个修改M的表达式B，则A的值依赖于一个副作用X（写），对于M的Modification order而言，X早于B；
• 写-读一致性（Write-read coherence）：如果一个修改某个原子M的副作用 X（写）happens-before 另一个读取原子M用于计算的表示式B，则B值的计算要么从X处取值，要么从就Modification order而言晚于X的副作用Y处取值；

• Release Operation

原子变量的store操作被指定为memory_order_release内存顺序或者更强要求的内存顺序时，被称为release operation。在本线程内，release operation之前的任何内存访问操作（包括非原子操作和relaxed的原子操作）都不会被重排到release operation之后。通常用于在该操作前准备某些资源，准备完毕后*“release”*给别的线程。

• Acquire Operation

原子变量的load操作被指定为memory_order_acquire内存顺序或者更强要求的内存顺序时，被称为acquire operation。在本线程内，acquire operation之后的任何内存访问操作（包括非原子操作和relaxed的原子操作）都不会被重排到acquire operation之前。通常用于等待某些资源，一旦满足条件就可以安全的*“acquire”*并消费这些资源。

• Consume Operation

原子变量的load操作被指定为memory_order_consume内存顺序或者更强要求的内存顺序时，（至少）被称为consume operation。在本线程中，consume operation之后任何依赖于所load的值的内存访问操作都不会被重排到consume operation之前。相比于acquire操作，consume操作更为宽松，去除了对无依赖关系的操作的重排限制，减少了所需同步的数据量。

Synchronizes with

如果A线程中的原子store操作是release操作，B线程中对同一原子变量的load操作是acquire操作，则可以称A线程中store操作synchronizes-with（同步） B线程中的load操作。

Release Sequence

对于原子变量M，在release操作A之后，以下对原子变量M的操作构成构成一条同步关系的传递链，称为Release Sequence：

• 同一线程内的store操作（可以是relaxed内存顺序）；
• 任意线程中的read-modify-write操作（可以是relaxed内存顺序）；

这个理解起来有点绕，举个例子：

// 线程 1：
A; // 表示一系列内存访问操作
x.store(2, memory_order_release);

// 线程 2：
B; // 与A类似
int n = x.fetch_add(1, memory_order_relaxed);
C; // 与A类似

// 线程 3：
int m = x.load(memory_order_acquire);
D; // 与A类似

假设x的初始值为0，则n可能的值为0或2，m可能的值为0、1、2和3。

若结果是n=2且m=3，则此时构成了Release Sequence，线程2读取的值是线程1写入的，而线程3读取的值是线程2写入的，通过Release Sequece的传递，线程1中的store操作 synchronizes-with 线程3中的load操作，A happens-before D；此外，若m=2，线程2还未执行，线程3直接读取线程1写入的值，线程1中的store操作同样 synchronizes-with 线程3中的load操作，A happens-before D；

需要注意的是，线程2中的fetch_add操作是Relaxed的，所以其不会对B和C的重排做任何约束，且其跟线程1中的store操作和线程3中的load操作均不构成同步关系，即便在Release Sequence中，也无法保证A happens-before C 或 B happens-before D。即Release Sequence 强调的是一个传递。

当然，若线程2中的fetch_add改成memory_order_acquire内存序，则A happens-before C；改成memory_order_release，则 B happens-before D；改成memory_order_acq_rel或memory_order_seq_cst，则A happens-before C 且 B happens-before D。

Dependency-ordered before

在不同线程间，如果满足以下任一条件，则操作A dependency-ordered before 操作B：

• A对原子变量M执行release操作，B对同一原子变量M执行consume操作，读取A操作或其Release Sequence中任何一个操作所写入的值；
• 操作A dependency-ordered before 操作X，且X carries dependency into B；

Inter-thread happens-before

在不同线程间，如果满足以下任一条件，则操作A inter-thread happens-before 操作B：

• 操作A synchronizes-with 操作B；
• 操作A dependency-ordered before 操作B；
• 操作A synchronizes-with 操作X，且X sequenced-before 操作B；
• 操作A sequenced-before 操作X, 且X inter-thread happens-before 操作B；
• 操作A inter-thread happens-before 操作X, 且X inter-thread happens-before 操作B；

happens-before

不管是否在同一线程，如果满足以下任一条件，则操作A happens-before 操作B：

• 操作A sequenced-before 操作B；
• 操作A inter-thread happens-before 操作B；

对于 happens-before，更为严格的要求称为 strongly happens-before，需满足如下任一条件（until C++20）：

• 操作A sequenced-before 操作B；
• 操作A synchronizes-with 操作B（更严格的要求，排除了consume）；
• 操作A strongly happens-before 操作X，且X strongly happens-before 操作B；

而到了C++20， strongly happens-before被更名为simply happens-before，而strongly happens-before则指代一种更强的要求，需满足如下任一条件：

• 操作A sequenced-before 操作B；
• 操作A synchronizes-with 操作B，且A和B均为 sequentially consistent 内存序；
• 操作A sequenced-before 操作X，操作X simply happens-before 操作Y，Y sequenced-before 操作B；
• 操作A strongly happens-before 操作X，且X strongly happens-before 操作B；

原子操作的内存顺序标签

• memory_order_relaxed：被打上该标签的原子操作不是同步操作，不参与synchronized-with 关系。它只保证原子性本身，以及在同一线程内对同一原子变量的操作不被重排。
• memory_order_release：被打上该标签的store原子操作被称为release operation。在本线程内，release operation之前的任何内存访问操作（包括非原子操作和relaxed的原子操作）都不会被重排到release operation之后。
• memory_order_acquire：被打上该标签的load原子操作被称为acquire operation。在本线程内，acquire operation之后的任何内存访问操作（包括非原子操作和relaxed的原子操作）都不会被重排到acquire operation之前。
• memory_order_consume：被打上该标签的load原子操作被称为consume operation。在本线程中，consume operation之后任何依赖于所load的值的内存访问操作都不会被重排到consume operation之前。在大多数平台上，该标签只影响编译器优化。
• memory_order_acq_rel：被打上该标签的 read-modify-write 原子操作（如fetch_add），既是acquire operation，又是release operation。
• memory_order_seq_cst：被打上该标签的load操作是acquire operation，store操作是release operation， read-modify-write操作既是acquire operation又是release operation。同时，存在一条单一的总序，使得所有线程看到的相同的内存操作顺序。

Relaxed ordering

被打上memory_order_relaxed标签的原子操作为Relaxed内存序，不是同步操作，不参与synchronized-with 关系。它只保证原子性本身，以及在同一线程内对同一原子变量的操作不被重排。

// Thread 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1, std::memory_order_relaxed); // B
// Thread 2:
r2 = x.load(std::memory_order_relaxed); // C 
y.store(42, std::memory_order_relaxed); // D

这里允许出现 r1 == r2 == 42，即出现D->A->B->C的执行顺序，这可能是编译重排导致的，也可能是CPU运行时乱序发射导致的。

Relaxed内存序的典型应用是递增计数器，例如std::shared_ptr中的引用计数器的递增，因为这时只需要保证原子性，而不需要考虑同步和内存排序。但是有点需要注意，std::shared_ptr引用计数器的递减，需要跟析构函数进行acquire-release同步。

Release-Acquire ordering

线程A中的原子store操作被打上memory_order_release，线程B中的对同一原子变量的load操作被打上memory_order_acquire，则它们构成Release-Acquire内存序。两者之间为同步关系，即线程A中所有的happen-before 原子store操作的内存写操作，对线程B中的原子load操作之后的操作而言，都是已经发生且可见的。这种同步关系仅在线程A和B之间成立，其他线程可能看到不同的访存顺序。

在强内存序系统（strong-ordered systems）上，如X86系统，大多数指令操作的默认排序都是Release-Acquire内存序，并不会提供额外的指令，只会影响编译器优化层面；而在弱内存序系统（weakly-ordered systems）上，如ARM系统，会使用一些特定的CPU load 指令和内存栅栏（memory fench）指令。

Release-Acquire内存序的典型示例是互斥锁（mutual exclusion locks），如std::mutex和 atomic spinlock，线程A释放（release）锁，线程B获取（acquire）锁，则线程A中发生在release操作之前的操作，对线程B acquire操作之后都是可见的。

Release-Consume ordering

线程A中的原子store操作被打上memory_order_release，线程B中的对同一原子变量的load操作被打上memory_order_consume，则它们构成Release-Consume内存序。两者之间为 Dependency-ordered before 关系，即线程A中所有的happen-before 原子store操作的内存写操作，对线程B中的原子load操作之后并依赖于所load的值的操作而言，都是已经发生且可见的。这种关系可以认为是一种相对宽松的同步关系，仅在线程A和B之间成立，其他线程可能看到不同的访存顺序。

对于所有的主流CPU而言，这种dependency ordering内存序都是自动且默认的，不需要为此提供额外的指令，只会影响编译器层面的优化。并且，到2015年2月为止，所有已知的生产编译器都不会跟踪依赖链，consume操作会被提升为acquire操作。

这种内存序的典型应用是涉及 对写入操作较少的并发数据结构的读取访问（如路由表，配置，安全策略和防火墙规则等）和 以指针作为传递媒介的发布者-订阅者（publisher-subscriber）模式，在这种模式下，生产者发布一个指针，消费者可以通过该指针访问信息：这时不需要使生产者写入内存的所有其他内容对该消费者可见（订阅内容外的内容可以不同步）。典型的示例比如 RCU 机制（read-copy-update），一个简单的示例参见这里。

自C++17开始，Release-Consume ordering 正在修订中，暂时不鼓励使用memory_order_consume标签。

Sequentially-consistent ordering

被打上memory_order_seq_cst标签的原子操作们构成顺序一致（Sequentially-consistent）内存序。SC内存序除了会跟Release-Acquire ordering一样的方式进行内存排序外，还会为被标记的原子操作建立一条单一的总序。

需要注意的是：

• 被打上memory_order_seq_cst的load操作所得到的值，要么来自之前memory_order_seq_cst标签的修改操作，要么来自非memory_order_seq_cst标签的修改操作，这些非顺序一致修改操作发生在顺序一致修改操作之后；
• 只要有非memory_order_seq_cst标签的原子操作被加入程序，则该段程序就会丢失顺序一致性保证；
• 顺序一致的内存栅栏（memory fences）操作，如std::atomic_thread_fence，只是为栅栏本身建立总序，而不是为一般情况下的原子操作建立总序；
• 单一总序并不等同于happen-before。当顺序一致内存序于其他内存序混用时，可能会出现不符合预期的情况。如下面这个例子，x和y被初始化为0：

// Thread 1:
x.store(1, std::memory_order_seq_cst); // A
y.store(1, std::memory_order_release); // B
// Thread 2:
r1 = y.fetch_add(1, std::memory_order_seq_cst); // C
r2 = y.load(std::memory_order_relaxed); // D
// Thread 3:
y.store(3, std::memory_order_seq_cst); // E
r3 = x.load(std::memory_order_seq_cst); // F

​ 可能会出现r1 == 1 && r2 == 3 && r3 == 0的情况，虽然B和C是同步关系，A 必然 happen-before C，但对于memory_order_seq_cst的单一总序而言，可能会出现B->C->E->F->A->D的总序（这里搞不太懂，如果出现这样的情况，则A就被重排到B之后，这与release操作限制重排的描述自相矛盾了。具体可以研究一下Lahav et al）。

对于多个生产者-多个消费者的场景，顺序一致内存序可能是必要的。在这种情况下，不同消费者观察到的所有生产者的行为必须以相同的顺序执行。

实现 sequencial consistent 模型是有一定的开销的。现代 CPU 通常有多核, 每个核心还有自己的缓存，为了做到全局顺序一致，每次写入操作都必须同步给其他核心。

下面这个示例展示了一种必须使用SC内存序的场景，其他任何内存序都有可能导致断言触发：

#include <thread>
#include <atomic>
#include <cassert>

std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};

void write_x() {
    x.store(true, std::memory_order_seq_cst);	// [1]
}

void write_y() {
    y.store(true, std::memory_order_seq_cst);	// [2]
}

void read_x_then_y(){
    while (!x.load(std::memory_order_seq_cst));	// [3]
    if (y.load(std::memory_order_seq_cst)) ++z;	// [4]
}

void read_y_then_x(){
    while (!y.load(std::memory_order_seq_cst));	// [5]
    if (x.load(std::memory_order_seq_cst)) ++z; // [6]
}

int main() {
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // will never happen
}

断言永远不会触发。因为 x 和 y 的修改顺序是全局一致的，如果先执行 [1] 后执行 [2], 则 read_y_then_x 中循环 [5] 退出时, 能保证 y 为 true, 此时 x 也必然为 true, 因此 [6] 会被执行; 同理, 如果先执行 [2] 后执行 [1], 则循环 [3] 退出时 y 也必然为 true, 因此 [4] 会被执行。 无论如何, z 最终都不会等于 0。

[1] https://en.cppreference.com/w/cpp/language/memory_model

[2] https://en.cppreference.com/w/cpp/atomic/memory_order

[3] 如何理解 C++11 的六种 memory order？

[4] 内存体系中的Consistent和Coherent

[5]* 谈谈 C++ 中的内存顺序 (Memory Order)