当多个线程同时访问一个变量时，会导致数据竞争问题，会导致结果未定义。而且从实现来说，即时是一条语句，从硬件层面仍不能保证读写操作是原子的，例如变量在寄存器中，修改后才写入内存。

通常使用的是 Mutex 操作，不过常用的还有原子操作。

简介

时任 ARM 工程师，参与了 ARM64 的 SMMU、内存模型等架构设计的 Will Deacon，在 Kernel Recipes 2018 中进行了名为 Evolution and use of relaxed concurrency primitives 的演讲中，曾用了这样一句话来形容多核带来的同步问题 We ask for performance, but they give us concurrency 。

本来，多核系统的出现是为了解决单核系统的性能瓶颈，但与之相伴的 Concurrency(并发) 却又是不可避免的。

Concurrency(并发) VS. Parallelism(并行) 并发是逻辑上的同时发生，具有同时处理多个任务的能力，但是两者不一定同时发生。并行则是物理意义上的同时发生，并发不一定是并行。
吃饭吃到一半，电话来了，你一直到吃完了以后才接，说明你不支持并发也不支持并行。
吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，说明你支持并发。
吃饭吃到一半，电话来了，你一边打电话一边吃饭，说明你支持并行。
并发的关键是具有处理多个任务的能力，不一定是同时处理；而并行的关键是要有同时处理多个任务的能力。

当前 CPU 大部分都是多核的，一个具有并发能力的程序，为了充分利用 CPU 资源，那么对应一般就会是并行的。

原子操作

Mutex 通常是由操作系统或者库实现，而 Atomic 原子操作则需要由底层硬件提供支持。

原子操作是解决数据竞争、线程同步的基础操作，包括像 mutex、rwlock 也基本都是基于原子操作来实现的并发控制，详细可以查看内核的代码实现。

原子变量包含了三种基础操作：

Load 读取原子变量中的值；
Store 将值保存到原子变量中；
ReadModifyWrite, RMW 原子执行读取、修改、写入操作。

实际上基于 RMW 有很多常用的操作，例如 fetch_add 自增、exchange 返回当前值并写入指定值。

不同的平台里，虽然底层实现基本相同，但是有些语言可能会在上层进行封装，例如 C++ 通过函数重载，几乎可以不用感知原子变量。如下以 C++ 为例介绍。

内存序

在 C++ 中使用时，需要同时指定内存顺序 (Memory Order)，不同内存顺序有不同的语义，可以实现不同顺序模型，对应性能也各不相同，C++ 中的内存顺序定义如下：

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

默认采用的是顺序一致性 Sequentially Consistent Ordering，可以实现较强的一致性。

void store(T desired, std::memory_order order = std::memory_order_seq_cst);
T load(std::memory_order order = std::memory_order_seq_cst) const;

虽然可以实现较强的一致性，但是会导致性能下降，所以，一些高性能场景下通常会选择其它模型，此时就需要显示通过原子操作指定模型了。

另外，如上所述 std::atomic 重载了运算符，所以，如果使用默认内存序，那么可以像使用普通变量一样使用原子变量，否则需要显示指定。而且，不同的原子操作支持的内存序是不同的，表格如下。

通过这六种内存顺序相互组合可以实现如下几种顺序模型 (Ordering Model)：

Sequencial Consistent Ordering 实现同步且保证全局顺序一致，是一致性最强的模型，也是默认的顺序模型。
Release-Acquire Ordering 实现同步，但不保证保证全局顺序一致的模型。
Relaxed Ordering 不能实现同步，只保证单个变量原子性的模型。

如下进行详细介绍。

基本概念

在介绍具体的内存序之前，这里先介绍基本的概念。

Modification Orders

一个原子变量的所有修改操作总是存在一个所有线程都认可的先后顺序，即使这些修改操作是在不同的线程中执行的，而这个顺序就是所谓的修改顺序 (Modification Order)，在 CPP Reference Memory Order 中包含了一些详细约束。

注意，每次运行的顺序可能不同，但是每次运行时所有线程看到的顺序总是一致的，无论使用哪种内存序 (即使最松散的 memory_order_relaxed 类型)，原子变量的操作总能满足修改顺序一致性。

#include <vector>
#include <atomic>
#include <thread>
#include <iostream>

#include <unistd.h>

std::atomic<int> a{0};

void writer(int start) {
    for (int i = start; i < 10; i += 2) {
        usleep(10);
        a.store(i, std::memory_order_relaxed);
    }
}

void reader(std::vector<int> *v) {
    for (int i = 0; i < 10; i++) {
        usleep(1);
        v->push_back(a.load(std::memory_order_relaxed));
    }
}

void dump(std::vector<int> &v) {
    for (int i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> v1, v2;
    std::thread w1(writer, 0), r1(reader, &v1), w2(writer, 1), r2(reader, &v2);

    w1.join(), w2.join(), r1.join(), r2.join();
    dump(v1), dump(v2);
    return 0;
}

有两个线程按照奇偶写入，另外两个线程则读取，为了便于观察各个线程之间增加了休眠时间，防止一直出现 8 9 这种不变的数字，如下是一个可能的执行结果。

1 2 5 6 9 9 9 9 9 9
0 2 5 6 8 9 9 9 9 9

首先，读取不太可能看到每次的修改结果，例如调度到读取线程时可能已经执行了多次；但是读取的每次修改顺序是一致的，例如 r1 看到 4 先于 7，那么 r2 同样也是看到 4 先于 7，反之亦然。

也就是有个全局层面的一致性顺序。

Happens Before

这是一个非常重要的逻辑概念，如果 A Happens Before B 那么操作 A 的结果对于操作 B 可见，可以是同一个线程间的两个操作，也可以是不同线程间的两个操作，以此可以解决数据竞争 (Data Race)。

个人认为，这决定了代码实际运行时的前后依赖关系，无论是否为多线程。

Sequenced Before 单线程

单线程很容易理解，语句按照顺序执行，前面的语句先于后面的语句执行，或者正式地说，前面的语句总是 sequenced-before 后面的语句。注意，同一语句的顺序是不确定的，详见 Order of Evaluation 中的介绍。另外，如果两个语句之间没有相互依赖关系，那么也无法保证顺序。

求值 (Evaluation) 实际上包含了两部分操作：A) Value Computation 计算表达式的值；B) Side Effect 则是读写对象。语言本身并未规定表达式的求值顺序，例如 f1()+f2()+f3()、func(f1(), f2(), f3()) 中三个函数可以是任意的排列顺序。同时，像 i = i++ + i 这种语句的行为也未定义。

显然，sequenced-before 具有传递性，如果 A sequenced-before K，且 K sequenced-before B，那么可以推断出 A sequenced-before 操作 B 。

而且 sequenced-before 可以直接构成 happens-before 的关系，也就是说，如果 A sequenced-before B 则 A happens-before B 。例如：

a = 42;            // (1)
cout << a << endl; // (2)

在单线程中，语句 (1) 在语句 (2) 前面，因此语句 (1) sequenced-before 语句 (2)，也就是说 (1) happens-before 语句 (2)，所以 (2) 可以打印出 (1) 赋值的结果。

Synchronizes-With VS. Inter-Thread Happens-Before

多线程要复杂很多，因为多线程是并发执行的，如果没有正确的同步操作那么可能无法保证两个操作间的 happens-before 关系。当通过一些方法 (例如，加互斥锁) 让不同线程的两个操作同步，那么称这两个操作有 synchronizes-with 的关系。

当线程 1 中的操作 A synchronizes-with 线程 2 中的操作 B，那么可以称操作 A inter-thread happens-before 操作 B，也就是线程间的 happens-before 关系，而且还允许 A 前面或 B 后面接一个 sequenced-before 操作，例如，当 B 同时 sequenced-before K，那也意味着 A inter-thread happens-before K。

注意，虽然 sequenced-before 和 inter-thread happens-before 都具有传递性，但 happens-before 是没有传递性的。

例如有如下操作。

void thread1() {
    a += 1;         // A
    mutex.unlock(); // B
}

void thread2() {
    mutex.lock();      // C
    cout << a << endl; // D
}

其中 mutex.unlock() 操作 synchronize-with mutex.lock() 操作，对于如上代码，可以推断出。

根据单线程中的语句顺序，有 A sequenced-before B 且 C sequenced-before D 。
因为 B synchronize-with C 且 C sequenced-before D，所以 B inter-thread happens-before D。
因为 A sequenced-before B 且 B inter-thread happens-before D，所以 A inter-thread happens-before D，最终 A happens-before D。

所以，在 D 中可以看到 A 的修改。

这里是由 mutex 完成 synchronize-with 操作的，实际上，针对单个原子变量的 release-acquire 也可以达到，从而可以优化性能，可以查看 Synchronize With 中的介绍。

其它

注意，happens-before 是语言在语义层面的概念，并不代表指令在 CPU 中执行时的实际顺序，为了优化性能，会在编译器以及 CPU 中在不破坏的前提下对指令进行重排。

extern int a, b;
int add() {
    a++;
    b++;
    return a + b;
}

虽然有 a++; happens-before b++;，因为两个变量没有依赖关系，实际编译后可能会先执行 b++ 操作，甚至是最后执行 a + b + 2 操作，因为这并不影响语义。

内存顺序

并发系统设计的时候，关键就是如何根据内存模型实现 synchronize-with 关系，也就是如何使用上述的六种内存顺序以及何种组合可以实现 synchronize-with 关系，如下表格是不同模型的支持能力。

memory order

Sequencial Consistent

对应了默认 memory_order_seq_cst 模型，所有线程看到的所有操作都有一个一致的顺序，即使这些操作是在不同线程中针对的不同变量，而之前修改顺序指的是单一变量，而这里是将这种一致性扩展到了所有变量。

注意，这里并不要求每次都一样，但每次运行中的每个线程看到的顺序都相同。

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

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

void thread2() {
    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(thread1), b(thread2), c(read_x_then_y), d(read_y_then_x);
    a.join(), b.join(), c.join(), d.join();
    assert(z.load() != 0); // (7)
}

因为 SeqCst 可以保证全局修改顺序，对应 (7) 处的断言永远不会失败，分析如下。

如果先执行 (1) 后执行 (2)，则 read_y_then_x() 中循环 (5) 退出时，能保证 y 为 true，此时 x 也必然为 true，因此 (6) 会被执行; 同理，反之亦然。

SeqCst 可以实现 synchronizes-with 关系，如果一个 SeqCst 的 load 操作在某个原子变量上读到了一个 SeqCst 的 store 操作在这个原子变量中写入的值，则 store 操作 synchronizes-with load 操作。上述示例中，有 (1) synchronizes-with (3) 和 (2) synchronizes-with (5) 。

注意，实现 Sequencial Consistent 模型存在一定开销，因为现在 CPU 通常有多核，每个核心还有自己的缓存，为了做到全局顺序一致性，每次写入操作都必须同步给其它核心，所以，如果不需要全局顺序一致，可以考虑其它更宽松的顺序模型。

Relaxed

对应 memory_order_relaxed 模型，此时只能保证操作的原子性和修改顺序一致性 (应该是单个变量)，无法实现 synchronize-with 关系，例如如下示例。

std::atomic<bool> x{false}, y{false};

void thread1() {
    x.store(true, std::memory_order_relaxed); // (1)
    y.store(true, std::memory_order_relaxed); // (2)
}

void thread2() {
    while(!y.load(std::memory_order_relaxed)); // (3)
    assert(x.load()); // (4)
}

在 thread1 中的操作针对的是不同变量，那么在某些线程看来，有可能是 x 先变成 true，在另外的线程可能是 y 先变成 true，所以，上述的代码 (4) 可能失败。

relaxed 顺序模型开销很小，在 x86 架构下不会生成额外指令，只需要编译器确保为原子操作。其中 std::shared_ptr 增加引用计数时用的就是 relaxed 模型，但是减少时，因为涉及到析构操作同步，所以不能使用。

Acquire Release

会涉及到 memory_order_acquire memory_order_release 和 memory_order_acq_rel 三种内存顺序，原子操作和内存序的支持度可以参考之前的表格。可以实现 synchronize-with 关系，如果一个 acquire 操作在同一个原子变量上读取到了一个 release 操作写入的值，那么这个 release 操作 synchronize-with 这个 acquire 操作。

std::atomic<bool> x{false}, y{false};

void thread1() {
    x.store(true, std::memory_order_relaxed); // 1
    y.store(true, std::memory_order_release); // 2
}

void thread2() {
    while(!y.load(std::memory_order_acquire)); // 3
    assert(x.load(std::memory_order_relaxed)); // 4
}

上述可以推导出 2 synchronizes-with 3，而且 3 sequenced-before 4 从而有 2 inter-thread happens-before 4；另外 1 sequenced-before 2 而 2 inter-thread happens-before 4 可以得到 1 inter-thread happens-before 4。

所以有 1 happens-before 4 也就是 4 能读取到 1 中写入值，断言不失败，即使 1/4 使用 relaxed 模型。

其开销相比 SeqCst 要小，在 x86 上 release/acquire 不会生成额外指令，编译器会确保所有指令不会重排到 acquire 前以及 release 之后，所以，这也是最常用场景。

Release Sequence

上述的 SeqCst 和 AcqRel 模型，要实现 synchronizes-with 关系必须要操作同一个原子变量。

std::atomic<int> x{0}, y{0};

void thread1() {
    x.store(1, std::memory_order_relaxed); // 1
    y.store(1, std::memory_order_release); // 2
}

void thread2() {
    y.store(2, std::memory_order_release); // 3
}

void thread3() {
    while (!y.load(std::memory_order_acquire));     // 4
    assert(x.load(std::memory_order_relaxed) == 1); // 5
}

上述例子中，对于 4 在 y 非 0 时会退出循环，此时可能读取到 2 或 3 写入的值，如果是后者则无法保证 2 与 4 的同步关系，那么 5 的断言就可能会失败。不过，并非只有 AcqRel 才构成 synchronizes-with 关系，为此引入了 Release Sequence 概念。

针对某个原子变量 M 的 Release 操作 A 完成后，接下来 M 上可能还存在一连串其它操作，主要包括两类操作(可以使用任意内存序)：A) 同一线程上的写操作；B) 任意线程上的 RMW 操作。将这一连串操作称为，以 Release 操作 A 为首的 Release Sequence 。

那么上述的 synchronizes-with 修改为，如果一个 Acquire 操作读取到了同一个原子变量上 Release 写入值，或者以这个 Release 操作为首的 Release Sequence 写入的值，那么可以断定，这个 Release 操作 synchronizes-with 这个 Acquire 操作。

如下是一个简单示例。

std::vector<int> data;
std::atomic<int> flag{0};

void thread1() {
    data.push_back(42); // 1
    flag.store(1, std::memory_order_release); // 2
}

void thread2() {
    int expected = 1;
    while (!flag.compare_exchange_strong(expected, 2, std::memory_order_relaxed)) // 3
        expected = 1;
}

void thread3() {
    while (flag.load(std::memory_order_acquire) < 2); // 4
    assert(data.at(0) == 42); // 5
}

bool compare_exchange_strong(T& expected, T desired, std::memory_order success, std::memory_order failure);
如果当前值等于 expected 时，用 desired 替换，返回 true；否则不做任何操作，同时将 expected 更新为当前值，并返回 false 。
另外，还有一个 compare_exchange_weak() 版本，允许在字段值和 expected 一样时返回 false，并且没有将字段值设置为 desire 的值，也就是 spuriously fail，某些平台上的性能会更好。

步骤 3 会一直循环等待 flag 的从 0 变为 1，然后原子将 flag 设置为 2，此时的 3 属于 2 的 Release Sequence，当循环 4 退出时，实际上已经读到了 3 写入的值，也就是以 Release 操作 2 为首的 Release Sequence 写入的值，所以有 2 synchronizes-with 4，因此 1 happens-before 5，那么 5 处的断言不会失败。

注意，3 处的 compare_exchange_strong 的内存顺序是 memory_order_relaxed，所以 2 与 3 并不构成 synchronizes-with 关系. 也就是说, 当循环 3 退出时, 并不能保证 thread2 能读到 data.at(0) 为 42。但是 3 属于 2 的 Release Sequence, 当 4 以 memory_order_acquire 的内存顺序读到 2 的 Release Sequence 写入的值时, 可以与 2 构成 Synchronizes With 的关系。

Consume

对应了 memory_order_consume 内存序，是 AcqRel 模型的特例，同时会涉及到数据间的相互依赖关系，为此需要引入 Carries Dependency 和 Dependency-Ordered Before 两个新概念。

原子操作内存序介绍

简介 #

原子操作 #

内存序 #

基本概念 #

Modification Orders #

Happens Before #

Sequenced Before 单线程 #

Synchronizes-With VS. Inter-Thread Happens-Before #

其它 #

内存顺序 #

Sequencial Consistent #

Relaxed #

Acquire Release #

Release Sequence #

Consume #

简介