（二）多线程那些事儿：原子类型数据和内存序

1. concepts

1.1 怎么理解原子性

在编程领域，原子性指操作不可再分割，类似原子在日常理解中不可分割（虽从科学角度原子可细分）。以常见的 i++ 为例，它并非原子操作，实际包含三个步骤：读 i 值、i 值加 1、写回 i 值。这是因为数据存储在内存等设备，而计算在 CPU 中进行，即使简单计算也需数据在内存与 CPU 间传输。

不仅 i++ 整体不是原子操作，“读 i 值” 本身也可能并非原子。比如当 i 值跨越多个缓存行时，CPU 读取操作可能分步进行，如从某地址读取长度为 3 行的数据，内存逐行返回。在此期间，若数据跨多行，读取第一行时第二行可能被其他操作改动。如果不好理解，不妨以一个复杂结构体为例子。如 struct Foo { int a1;... int a1000; }，当一个线程读取该结构体，还未读完所有成员（如 a1000）时，a1000 可能已被其他线程改动，导致读取到理论上不应存在的 “新旧混合” 数据。不过，多数计算机架构能保证像 int 这类简单数据的读取具有原子性，但这并非理所当然，不能想当然认为读操作一定就是原子的。

总之，代码中的一行指令，在计算机内部可能对应若干机器指令及众多晶体管操作。若这些指令、这些操作不可被打断、分割，不会受其他操作干扰破坏，就是原子性的。

1.2 如何保证`atomic`的原子性？是否有锁？

如今的处理器大多支持原子指令，像在 x86 架构中，会使用 LOCK 前缀，其他平台也有各自特定的原子操作指令。这些指令通过锁住总线或缓存行，确保在当前线程的相关指令执行完毕前，其他线程无法对被锁定的数据进行操作，从而实现阻塞。

若硬件不支持原子指令，就需借助更为复杂的软件层面方法来实现原子操作，这里暂不深入探讨。

std::atomic 内部存在优化机制。对于简单数据类型，它能够借助原子指令，以非 mutex（互斥锁）的方式达成原子性；但对于复杂数据类型，可能就需要用到锁。

部分数据类型的读操作，在 C++ 代码中看似一行，对应到指令操作其实也是一行，这种情况下无需锁住总线就能实现原子性；然而，部分数据类型的读操作，C++ 代码虽为一行，对应指令操作却可能多达几十行。为保证原子性，首条指令或许就是请求锁住总线，最后一条指令则是解除总线锁定。

通常，原子指令大多较为简单，本身就是单一的不可打断操作；而有锁操作往往需要通过锁住总线来实现。

1.3 为何`atomic`禁止拷贝与复制

由于std库具有跨平台特性，并非每个平台都具备完善的原子操作指令。例如，对于“读取某一地址起始、长度为 3 行的数据”这一操作，部分平台可提供原子操作支持，而有些则无法做到。在缺乏良好原子操作指令的平台上，std::atomic的原子性需借助锁来保障。这意味着std::atomic<T>内部可能存在一个mutex（互斥锁）变量，而mutex本身是不可拷贝的，所以std::atomic<T>也不可拷贝。

那么，为什么mutex不可拷贝呢？从语义层面看，锁支持拷贝这一说法本身就略显怪异，但仅以此作为不支持拷贝的理由并不充分。我们不妨通过反证法来深入思考：假设锁是可拷贝的，那么应采用浅拷贝还是深拷贝呢？深浅拷贝的概念通常针对对象内部存在指针或引用类型的数据，而原子对象并非此类，所以这里只考虑普通拷贝。若进行拷贝，其目的是什么呢？难道是创建一把新锁去锁定同一个对象？需注意，“锁定对象”只是一种抽象理解，实际上锁的作用是确保某段代码区间同一时间仅有一个线程能够执行。那是否就重复保护了？保护谁了？无论怎样设想，若mutex拷贝出一把新锁，其保护内容都会变得难以界定，逻辑混乱。那能否让新拷贝的锁不保护任何内容，仅作为一把新创建的锁呢？如此一来，这实际上就是构造一把新锁，而非拷贝的概念了。

事实上，当希望对一个atomic对象拷贝的时候，其实也只是取其值，而非整个原子对象。如果拷贝出来的值，仍希望是原子的，则再通过这个值构造一个新的原子对象就好了，而非拷贝。

1.4 atomic 类型能有什么成员函数？怎么用？

操作	对应函数（接口）	对应操作符
读取	`T load(memory_order order = memory_order_seq_cst) const noexcept;`	转换操作符：`operator T() noexcept;`
存储	`void store(T desired, memory_order order = memory_order_seq_cst) noexcept;`	赋值操作符：`operator=(T desired) noexcept;`
加法/自增	`T fetch_add(T arg, memory_order order = memory_order_seq_cst) noexcept;`	`operator+=(T arg) noexcept;` 后置自增 `operator++(int)`
减法/自减	`T fetch_sub(T arg, memory_order order = memory_order_seq_cst) noexcept;`	`operator-=(T arg) noexcept;` 后置自减 `operator--(int)`
按位与	`T fetch_and(T arg, memory_order order = memory_order_seq_cst) noexcept;`	`operator&=(T arg) noexcept;`
按位或	`T fetch_or(T arg, memory_order order = memory_order_seq_cst) noexcept;`	`operator\\|=(T arg) noexcept;`
按位异或	`T fetch_xor(T arg, memory_order order = memory_order_seq_cst) noexcept;`	`operator^=(T arg) noexcept;`
交换	`T exchange(T desired, memory_order order = memory_order_seq_cst) noexcept;`	——（无对应操作符）
比较交换（弱）	`bool compare_exchange_weak(T& expected, T desired, memory_order success, memory_order failure) noexcept;`	——（无对应操作符）
比较交换（强）	`bool compare_exchange_strong(T& expected, T desired, memory_order success, memory_order failure) noexcept;`	——（无对应操作符）

为什么同时提供函数接口，和操作符接口？ 操作符（如赋值和类型转换）默认使用严格的内存序memory_order_seq_cst），而函数版本允许开发者根据具体场景指定其他内存序（例如 relaxed、acquire/release），以便进行更细粒度的性能调优。

1.5 自定义的 atomic 有什么限制？

基础要求 要让自定义类型T能使用std::atomic<T>，该类型必须满足Trivially Copyable条件，具体包含以下几点： 1. 拷贝语义方面：得有平凡的拷贝构造函数与赋值运算符。这意味着不能有用户自定义的拷贝或移动操作。 2. 析构函数方面：析构函数必须是平凡的，不能包含任何自定义操作。 3. 基类与成员方面：所有基类和非静态数据成员也都要是 Trivially Copyable 类型。
尺寸与对齐限制
- 尺寸方面：通常情况下，类型T的大小得小于或等于std::atomic<T>::is_always_lock_free所规定的最大尺寸（一般是 8 字节）。
- 对齐方面：类型T的对齐要求要和alignof(std::atomic<T>)保持一致，不然就需要使用alignas来进行显式对齐。

2. 内存序

2.1 什么是指令乱序？

内存序本质上用于限制编译器以及 CPU 对指令执行顺序的重排程度。对指令执行顺序进行重排，本质上是为了提升单核性能。现代 CPU 采用诸如冒险预测以及超标量流水线等技术，导致指令乱序执行，使得代码操作不一定按照编写顺序依次发生。至于 CPU 指令乱序如何提升性能的具体原因，将在 “计算机组成 - CPU 章节” 中进一步探讨，此处暂不展开。

在单线程场景下，C++作为编译型语言，能够充分利用程序上下文信息生成正确代码。例如int a = 0; a = a + 1;，编译器基于完整代码，必定能保证先定义后操作的顺序。而对于a = a + 1; b = true;这类情况，编译器无法确定a与b的计算先后顺序，但在单线程环境中，这种不确定性并无影响。

然而，在多线程场景下，指令顺序变得至关重要。例如，一个线程执行a = a + 1; b = true;，另一个线程执行while(!b){}; print(a);，即等待b为真时输出a的值。此时，a和b的计算顺序将直接影响第二个线程的执行结果。为解决多线程环境下的指令乱序问题，主要有以下两种思路：

上锁机制：对执行a = a + 1; b = true;的代码块以及while(!b){}; print(a);的代码块分别上锁，确保这两个操作不能同时进行，然后通过std::condition_variable来协调执行先后顺序，从而避免问题。
限制乱序行为：允许两个操作同时进行，但保证特定的执行顺序，如确保先执行a = a + 1;，再执行b = true，以此保证程序正确性。

对于第一种思路，此处不再赘述。而限制乱序行为主要通过两种方式实现：

内存屏障：以AB|CD为例，内存屏障可保证AB操作在CD之前执行，但不保证AB内部以及CD内部的执行顺序。
内存序：通过指定某个指令必须在特定操作之前或之后执行来保证顺序。例如在上述例子中，通过指定内存序，使得b = true这一写操作，在a = a + 1之后执行，具体来说是保证b的赋值操作是作用域内（{}或者函数内）最后一条写操作，这样就能保证多线程环境下的执行顺序正确。

需要注意的是，内存序主要用于指定操作的顺序，改变指令的乱序行为，且这一操作与原子性并无直接关联。在单线程环境下，由于不存在数据共享问题，无需指定内存序，编译器会在保证安全的前提下尽力进行指令乱序优化。而在多线程环境中，对于共享的非原子类型的数据，一般通过锁机制来保证数据安全。只有对于共享数据的原子类型数据，才需要借助内存序来确保数据访问顺序的正确性。

因此也就原子类型数据提供指定内存序的行为。

2.2 谁会对指令重排？

编译器重排：

编译器为优化程序性能，在生成机器代码时可能调整指令顺序。例如，对于如下 C++代码：

int a = 5;
int b = 3;
int c = a + b;

如果编译器分析发现a = 5和b = 3这两条指令不存在数据依赖关系，为提高执行效率，可能会交换它们的顺序。或者，对于条件语句中的指令，若符合优化条件，编译器可能将某条指令移至条件分支外部。编译器重排通常是安全的，因为它会保证在单线程环境中，重排后的程序行为与原程序一致。这是编译器基于对代码整体逻辑和性能优化的考量，在不改变单线程语义的前提下，对指令顺序进行的调整，以期望提升程序在目标机器上的执行效率。

CPU 重排：

现代 CPU 为进一步提高执行效率，在执行指令时也可能改变指令顺序。例如，假设存在一条指令需要从内存中读取数据，但由于内存访问延迟，该指令暂时无法执行。此时，CPU 可能会先执行后续不依赖该数据的指令。从汇编层面看，若有指令序列LOAD A, [mem]（从内存地址mem加载数据到寄存器A）、ADD B, A（将寄存器A与B相加）、SUB C, D（寄存器C减去D），当LOAD A, [mem]因内存延迟等待时，CPU 可能会先执行SUB C, D。CPU 还可能通过并行执行多个指令来提升整体处理速度。与编译器重排类似，这种在 CPU 层面的重排一般也是安全的，因为 CPU 会确保在单核环境下，重排后的程序执行结果与原程序保持一致。CPU 重排是利用硬件特性，在不影响单核执行逻辑正确性的基础上，对指令执行顺序进行动态调整，从而充分发挥硬件资源的效能。

需要注意的是，在多线程环境下，无论是编译器重排还是 CPU 重排，都可能引发数据竞争和同步问题，导致程序出现非预期的行为。这是因为不同线程对共享数据的访问顺序可能因重排而改变，从而破坏程序的正确性。

2.3 使用`std::mutex`时可能的乱序行为

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

std::mutex mtx;
std::condition_variable cv;
bool ready = false;
int data = 0;

void producer() {
    {
        std::unique_lock<std::mutex> lock(mtx);
        data++;
        ready = true;
    }
    cv.notify_one();
}

void consumer() {
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, []{ return ready; });
    std::cout << "Data: " << data << std::endl;
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join();
    t2.join();
    return 0;
}

上面这个是使用std::mutex的例子，我会从这个例子出发，进而对比使用原子变量控制内存序时，两者的区别是什么。

lock(): 如果互斥锁可用，则锁定；否则，让出 CPU。
wait(ready): 如果 ready 条件满足，则继续执行；否则，让出 CPU。
unlock(): 解锁互斥锁。
notify(cv): 通知。
wait(cv, ready): 如果条件变量 cv 满足，则执行。
reg: 寄存器

| mutex_producer |
| -------------- |
| lock()         |
| move reg data  |
| add reg 1      |
| move data reg  |
| move ready true|
| unlock()       |
| notify(cv)     |
| ...            |

| mutex_consumer |
| -------------- |
| wait(cv, ready)|
| print data     |
| unlock()       |
| ...            |

mutex_producer在调用lock()后，在这之内的所有数据，如data和ready的数据总线都被锁住了，其他地方无法访问这些数据，如果其他核同时持有这些数据，则会通过MESI协议将数据状态置为失效，然后需要重新从其他缓存或者内存同步。因此，内存上的这个数据被锁住了，其他核心上的这个数据失效了，这个时候这个数据就是被独占的。

而我们总能相信单线程的指令乱序不会导致单线程内部逻辑出错，也就是说mutex_producer和mutex_consumer内部的乱序是无所谓的，内部的依赖关系都能被正确处理。而锁又保证了mutex_consumer总能在mutex_producer之后执行，因此是没问题的。

小问题：如果unlock()排在了notify(cv)之前会怎么样？ unlock()和notify(cv)这种多线程才存在的依赖关系，在单个核心的乱序行为会被控制吗？一句话回答，不会，这两个哪个在前，哪个在后都可以。因此原问题等价于下面两种实现，哪个才是正确的。

void producer() {
    {
        std::unique_lock<std::mutex> lock(mtx);
        data++;
        ready = true;
    }
    cv.notify_one();
}

void producer2() {
    {
        std::unique_lock<std::mutex> lock(mtx);
        data++;
        ready = true;
        cv.notify_one();
    }
}

一句话回答，表现都正确，即都是线程安全。但是前者效率更好一些。我这里也首先表明一下，这里面潜藏的隐患是什么：如果生产者notify了，但是还没有让出锁；消费者被唤醒，但是却拿不到锁，这会不会有问题？会不会随后让出cpu，然后这个数据就一直没消费了？

不会。在 C++ 的条件变量机制中，线程被唤醒后（无论是虚假唤醒，还是调用notify）必须先获取锁，才能检查条件。这一顺序由 std::wait() 的底层实现强制保证，确保线程安全。如果被唤醒，锁被占用了，则进入 Ready 队列等待锁，持续竞争 CPU，不主动让出资源；拿到锁之后，如果条件不满足，就会让出锁和 cpu 资源，重新回到Block状态。即这次 notify 不会被消费。

2.4 使用原子变量下时可能的乱序行为

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

std::atomic<bool> ready(false);
int data = 0;

void producer() {
    data++;
    // 此操作逻辑上等同于 ready = true，为写操作
    ready.store(true, std::memory_order_relaxed);
}

void consumer() {
    // 此操作逻辑上等同于检查 ready，为读操作
    while (!ready.load(std::memory_order_relaxed)) {
        // 等待 ready 变为 true
    }
    std::cout << "Data: " << data << std::endl;
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join();
    t2.join();
    return 0;
}

上述代码对应的伪汇编代码：

wait(): 如果 ready 条件满足，则继续执行；否则，让出 CPU。

| atomic:producer | atomic:producer |
| --------------- | --------------- |
| move reg data   | ready           |
| add reg 1       | ...             |
| move data reg   | move reg data   |
| ...             | add reg 1       |
| ready           | move data reg   |
| ...             | ...             |
| ...             | ...             |

| atomic:consumer |
| --------------- |
| wait(ready)     |
| print data      |
| ...             |
| ...             |

从理论上来说，如果生产者完成生产任务并将标志位 ready 设置为 true，消费者便会开始消费，此时期望获取到的产品 data 值为 1。如果选择了严格的内存序，那std::memory_order_sql_cst就都没有问题，但上面代码是std::memory_order_relaxed，这个内存序并不能保证ready是最后一个内存写操作。因此由于指令执行顺序的不确定性，data 的输出值既可能是我们期望的 1，也有可能是初始值 0。

使用 atomic（原子操作）作为同步手段时，情况则有所不同。消费者虽然要等到 ready 为 true 才会输出 data，但由于指令重排的存在，ready 的设置操作有可能在 data 修改数值之前执行，也有可能在之后执行。这就导致在 atomic 模式下，消费者获取到的 data 值无法得到有效保证。究其本质，当我们使用 atomic 进行同步时，以 atomic 相关的原子操作为核心，其前后的代码操作并不一定具备原子性，这就可能引发非预期的行为。

2.5 内存序有哪些？

memory_order_relaxed（宽松内存序）：
- 此内存序仅确保原子操作自身具备原子性，不提供任何关于同步或顺序方面的保证。这意味着在多线程环境下，该原子操作与其他线程中的操作之间不存在特定的顺序关系。
- 这种内存序适用于类似计数器这样的场景，在这些场景中，并不需要进行跨线程的同步操作，仅关注对计数器值的原子更新。例如，在单线程环境下对某个计数器进行频繁自增操作，使用 memory_order_relaxed 既能保证自增操作的原子性，又能获得较好的性能，因为无需额外的同步开销。
memory_order_consume（消费内存序）：
- 该内存序保证当前线程中，依赖于该原子变量的后续操作不会被重排到该原子操作之前。与 memory_order_acquire 相比，memory_order_consume 的限制更窄，它仅对那些实际依赖于该原子变量值的操作起作用，而 memory_order_acquire 则保证所有后续操作不会被重排到该原子操作之前。
- 例如，当一个线程读取一个原子变量，并且后续操作是基于这个读取的值进行的（如根据读取的标志位决定是否执行某个函数），使用 memory_order_consume 可以确保这些依赖操作不会被提前到读取操作之前执行。不过，使用 memory_order_consume 需要更谨慎，因为它要求对依赖关系有清晰的界定，否则可能导致难以察觉的错误。
memory_order_acquire（获取内存序）与 memory_order_release（释放内存序）：
- memory_order_acquire：在当前线程中，此内存序保证所有后续的内存操作不会被重排到该获取操作之前。也就是说，一旦执行了带有 memory_order_acquire 的原子操作，后续对内存的访问（读或写）在执行顺序上会遵循该原子操作之后的顺序，不会提前到该原子操作之前执行。
- memory_order_release：与之相对，在当前线程内，memory_order_release 确保所有之前的内存操作不会被重排到该释放操作之后。即一旦执行了带有 memory_order_release 的原子操作，之前对内存的访问（读或写）在执行顺序上会保持在该原子操作之前，不会推迟到该原子操作之后执行。
- 这两种内存序常用于锁的获取与释放场景。例如，当一个线程获取锁（类似 memory_order_acquire 的语义）后，能确保后续对共享资源的访问是在获取锁之后进行的；而当一个线程释放锁（类似 memory_order_release 的语义）前，能保证对共享资源的修改都已完成，不会被重排到释放锁之后，从而确保其他获取锁的线程能看到正确的共享资源状态。
memory_order_acq_rel（获取 - 释放内存序）：
- 这种内存序同时具备 memory_order_acquire 和 memory_order_release 的语义。也就是说，对于执行此内存序的原子操作，在当前线程中，既保证后续的内存操作不会被重排到此操作之前，又保证之前的内存操作不会被重排到此操作之后。
- 它适用于读 - 修改 - 写这类操作场景。例如，在多线程环境下对共享变量进行先读取值，然后根据读取的值进行修改，最后再写回的操作，使用 memory_order_acq_rel 能确保该操作在内存访问顺序上的正确性，同时兼顾获取和释放内存序的语义要求。
memory_order_seq_cst（顺序一致性内存序）：
- 该内存序提供了全局的顺序一致性保证，即所有线程看到的内存操作顺序都是一致的。这是一种非常严格的内存序，它确保了所有线程对内存的访问都按照一个全局统一的顺序进行，就好像所有线程的操作都是顺序执行的一样。
- 然而，由于这种严格的顺序保证需要额外的同步开销，所以 memory_order_seq_cst 通常是最强的内存序，但也可能对程序性能产生一定影响。在对性能要求极高且对操作顺序一致性要求不那么严格的场景下，可能需要权衡是否使用该内存序。

不同操作支持什么内存序？
1. Store 操作（存储操作，即写操作）：
  - memory_order_relaxed
  - memory_order_release
  - memory_order_seq_cst
2. Load 操作（加载操作，即读操作）：
  - memory_order_relaxed
  - memory_order_consume
  - memory_order_acquire
  - memory_order_seq_cst
3. Read - modify - write（读 - 改 - 写）操作：
  - memory_order_relaxed
  - memory_order_consume
  - memory_order_acquire
  - memory_order_release
  - memory_order_acq_rel
  - memory_order_seq_cst
所有操作的默认内存序为 memory_order_seq_cst。这意味着在未显式指定内存序时，编译器会按照最严格的顺序一致性内存序来处理原子操作，以确保程序在多线程环境下的正确性，但可能会牺牲一定的性能。在实际编程中，开发者可根据具体需求，在保证程序正确性的前提下，选择更合适的内存序来优化性能。

2.6 内存序如何实现的？

编译器层面
- 编译器在实现内存序时，会借助插入特定的内存屏障指令来对指令重排进行限制。例如常见的 mfence（全内存屏障指令），它能确保在该指令之前的所有内存访问操作都已完成，才会执行后续的内存访问操作，有效地防止了指令跨越该屏障进行重排；sfence（存储内存屏障指令）则主要针对存储（写）操作，保证在它之前的所有存储操作都对内存可见后，才允许后续的存储操作执行，从而在编译器生成代码阶段，保障了内存操作顺序符合内存序的要求。通过这些内存屏障指令的合理插入，编译器能够在优化代码性能的同时，满足不同内存序所规定的操作顺序限制。总结：编译器通过插入如 mfence 和 sfence 等内存屏障指令，实现对指令重排的限制，保障内存操作顺序。
CPU 层面
- CPU 利用缓存一致性协议来保障跨核心的内存操作顺序。以 MESI 协议为例，MESI 是一种广泛应用于多核 CPU 缓存系统的协议，它定义了缓存行（Cache Line）的四种状态：Modified（已修改）、Exclusive（独占）、Shared（共享）和 Invalid（无效）。当一个 CPU 核心对内存中的数据进行读写操作时，MESI 协议会协调各个核心之间缓存的状态变化。比如，当一个核心修改了共享数据，该数据所在的缓存行状态会变为 Modified，同时其他核心中对应的缓存行状态变为 Invalid，这样就保证了其他核心在下次访问该数据时，能从主存或者拥有最新数据的核心缓存中获取到正确的值，从而确保了跨核心的内存操作顺序和数据一致性。总结：CPU 通过缓存一致性协议（如 MESI 协议），协调各核心缓存状态变化，确保跨核心内存操作顺序与数据一致性。
硬件层面
- 不同的硬件架构，像 x86 和 ARM，在对内存序的支持上存在差异。x86 架构通常对内存序有较强的默认保证，很多情况下无需额外的内存屏障指令就能满足较严格的内存序要求；而 ARM 架构则相对灵活，开发者可能需要更精细地控制内存序。为了让开发者能在不同硬件平台上以统一的方式编写代码，C++ 标准库通过抽象机制将这些硬件层面的差异进行了屏蔽。开发者在使用 C++ 的原子操作和内存序相关功能时，无需关心底层具体的硬件架构细节，只需要依据 C++ 标准库提供的接口和规则来确保程序的内存操作顺序符合需求，提高了代码的可移植性和通用性。总结：不同硬件架构对内存序支持有别，C++ 标准库通过抽象屏蔽差异，提升代码可移植性与通用性。

2.7 六种内存序怎么用？

todo: 我前面展开内存序的时候更多是从理解和原理出发，并没有太结合实际说明什么场景下使用什么内存序。这一小段会补充说明。

2.8 什么是先行发生，什么是并行发生？

todo：这个概念也是配合具体设置内存序的。之后补充。

3. 原子幻觉

3.1 什么是原子幻觉？

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

class MinMaxTracker {
  private:
    std::atomic<int> min_{INT_MAX};

  public:
    void update(int value) {
        if (value < min_.load()) {
            min_.store(value);
        }
    }

    int get_min() const { return min_.load(); }
};

void worker(MinMaxTracker& tracker, int id) {
    for (int i = 1000; i > 0; --i) {
        tracker.update(id * 1000 + i);
    }
}

int main() {
    MinMaxTracker tracker;
    std::vector<std::thread> threads;

    for (int i = 0; i < 4; ++i) {
        threads.emplace_back(worker, std::ref(tracker), i);
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << "Min value: " << tracker.get_min() << std::endl;
    return 0;
}

这段代码旨在找出最小值，然而，它存在问题。那么，问题出在哪里呢？其实，这属于典型的原子幻觉问题。

    if (value < min_.load()) {
        min_.store(value);
    }

在多线程环境下，当value < min_.load()这个条件为真时，由于其他线程也可能同时在执行update函数，竞争对min_的操作，在执行到下一行min_.store(value)之前，min_的值极有可能已被其他线程改变。此时，再用value去覆盖min_的值就可能导致错误结果。原子操作保证的是单个操作不可被打断，但多个原子操作组合起来的时候，就不再具有原子性。这种因疏忽而误以为组合的原子操作仍具备原子特性的错觉，就被称为原子幻觉。

为避免这种原子幻觉带来的问题，可以使用互斥锁来保证update函数中操作的原子性。例如，在MinMaxTracker类中添加一个std::mutex成员变量，在update函数中先锁定互斥锁，完成比较和存储操作后再解锁。或者，也可以使用std::atomic提供的compare_exchange_weak或compare_exchange_strong方法，通过比较并交换操作，以原子方式完成整个更新过程，确保结果的正确性。

3.2 CAS 技术

针对上述的原子幻觉问题，可以用 CAS 解决（注意，CAS 是无锁编程的一种重要技巧，不一定和原子幻觉直接挂钩，这里只是通过原子幻觉问题，引入 CAS 技术。CAS 技术还可以用在其他无锁编程地方，比如说无锁的线程安全队列。）

3.2.1 什么是 CAS？

通过前面的示例，我们已了解到具备原子性的变量可用于同步，发挥类似 lock()/unlock() 对的功能。而在实现无锁编程时，一种常见的借助原子变量达成此目的的技巧便是 CAS。

CAS，即 Compare-And-Swap（比较并交换），是一项广泛应用的原子操作，常用于实现无锁编程。它依赖硬件支持的原子指令，以此保障多线程环境下的操作安全性。

以下为一个简单的 CAS 操作示例代码：

bool CAS(int* addr, int expected, int desired) {
    if (*addr == expected) {
        *addr = desired;
        return true;
    }
    return false;
}

在标准库中，上述 CAS 操作被封装成了以下两种形式：

操作	对应函数（接口）	对应操作符
比较交换（弱）	`bool compare_exchange_weak(T& expected, T desired, memory_order success, memory_order failure) noexcept;`	——（无对应操作符）
比较交换（强）	`bool compare_exchange_strong(T& expected, T desired, memory_order success, memory_order failure) noexcept;`	——（无对应操作符）

参数类型分析：在 compare_exchange_weak() 函数中，第一个参数 expected 采用引用类型，它实际上等价于前面自定义 CAS(int* addr, int expect, int desired) 函数中的 expected 参数，用于表示我们期望目标地址处的值。而 compare_exchange_weak() 函数中的 desired 参数同样对应自定义 CAS 函数中的 desired 参数，即我们想要替换成的新值。此外，compare_exchange_weak() 函数后面的 success 和 failure 参数均为内存序相关参数，分别用于指定当比较交换操作成功和失败时所采用的内存序。

compare_exchange_weak()（弱版本）：

允许伪失败：此版本的一个重要特点是即使当前值与预期值相等，操作也有可能失败。这种失败并非由于数据本身的问题，而是源于硬件实现的一些限制。例如，在某些特定平台上，底层的 CAS 指令可能会偶尔出现失败情况。
适合循环使用：鉴于可能出现伪失败，在实际应用中，compare_exchange_weak() 通常需要放在循环结构中反复尝试，直至操作成功。这样可以确保在遇到伪失败时，程序仍能继续尝试达成预期的比较交换操作。
性能更高：在某些硬件环境下，compare_exchange_weak 的实现相比 compare_exchange_strong 更为高效。这是因为其实现可能利用了硬件的特定特性，以牺牲一定的操作确定性来换取更好的性能表现。
例如，对于 compare_exchange_weak() 函数，当目标变量的原始值与预期值一致时，存储操作仍有可能不成功。在这种情况下，变量的值不会发生改变，并且 compare_exchange_weak() 函数的返回值为 false。这种情况可能出现在缺少单条 CAS 操作（“比较 - 交换”指令）的机器上。当处理器无法保证该操作能够自动完成时，比如线程操作导致指令队列从中间关闭，且另一个线程安排的指令被操作系统替换（尤其在线程数多于处理器数量的情况下），就会出现这种所谓的“伪失败”（spurious failure）。其根本原因在于时间上的竞争条件，而非变量值本身的问题。

compare_exchange_strong()（强版本）：与弱版本不同，compare_exchange_strong() 函数具有更强的确定性。只要实际值与期望值不相符，该函数就能保证返回 false，即不会出现伪失败的情况。这意味着在当前值等于预期值时，操作一定会成功完成比较交换。

使用建议：综合来看，由于 compare_exchange_weak() 虽然可能出现伪失败，但在循环使用时能保证最终达成目标，且在某些硬件上具有性能优势，所以在很多场景下，使用 compare_exchange_weak 搭配循环是一种较为通用的做法。然而，具体的选择还需根据实际应用场景的需求和硬件环境等因素来综合考量。例如，在对操作确定性要求极高，性能要求相对较低的场景中，compare_exchange_strong 可能更为合适。

3.3 CAS 解决原子幻觉

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

class MinMaxTracker {
  private:
    std::atomic<int> min_{INT_MAX};
    std::atomic<int> max_{INT_MIN};

  public:
    void update(int value) {
        int old_min = min_.load();
        while (value < old_min && !min_.compare_exchange_weak(old_min, value)) {
        }
    }

    int get_min() const { return min_.load(); }
};

void worker(MinMaxTracker& tracker, int id) {
    for (int i = 0; i < 1000; ++i) {
        tracker.update(id * 1000 + i);
    }
}

int main() {
    MinMaxTracker tracker;
    std::vector<std::thread> threads;

    for (int i = 0; i < 4; ++i) {
        threads.emplace_back(worker, std::ref(tracker), i);
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << "Min value: " << tracker.get_min() << std::endl;
    return 0;
}

原代码中的问题是将读取和写入操作分开，导致竞态条件。改进后的代码使用 CAS 循环，相当于将”读取-比较-写入”封装为原子操作：

CAS 操作是原子性的，它执行以下逻辑：

比较：检查min_的当前值是否等于old_min
交换：
- 如果相等，则将min_设置为value，返回true
- 如果不相等（说明其他线程已修改），则将old_min更新为当前值，返回false
循环重试：如果 CAS 失败（返回false），则重新读取最新值并重试，直到成功

3.4 CAS 的 ABA 问题

todo: ABA 问题之后看情况再补充。

在这个场景中，即使出现 ABA 问题（值从 A 变为 B 再变回 A）也不会影响正确性，因为我们只关心值本身，而不关心它的变化过程。但部分场景会在意这个问题。

CAS 的 ABA 问题
- 因为 CAS 需要在操作值的时候检查值有没有发生变化，如果没有发生变化则更新。但是一个值原来是 A，变成了 B，又变成了 A，那么使用 CAS 进行检查时会发现它的值没有发生变化，但实际上却变化了。
- CAS 只关注了比较前后的值是否改变，而无法清楚在此过程中变量的变更明细，这就是所谓的 ABA 问题。
- 解决思路：
  - 使用版本号（如 MySQL 的 MVCC）。在变量前面追加版本号，每次变量更新的时候把版本号加一，那么 A-B-A 就变成了 1A-2B-3A，从而解决 ABA 问题。
- ABA 问题
  - CAS 需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是 A，变成了 B，又变成了 A，那么使用 CAS 进行检查时会发现它的值没有发生变化，但是实际上却变化了。这就是 CAS 的 ABA 问题
  - 常见的解决思路是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A-B-A 就会变成1A-2B-3A，由于每个过程值都会有对应的版本，所以我们在修改过程中需要传入期望版本和当前的值，数据库的多版本并发控制也类似
  - 添加时间戳：添加世时间戳也可以解决。查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间，这样也能保证，方法很多但是跟版本号都是异曲同工之妙
- 无限循环问题（自旋）
  - 如果 CAS 不成功，则会原地自旋，如果长时间自旋会给 CPU 带来非常大且没必要的开销
  - 可以使用 java8 中的 LongAdder，分段 CAS 和自动分段迁移
  - 自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。如果 JVM 能支持处理器提供的 pause 指令那么效率会有一定的提升，pause 指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使 CPU 不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起 CPU 流水线被清空（CPU pipeline flush），从而提高 CPU 的执行效率
- 只能保证一个共享变量的原子操作
  - 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环 CAS 的方式来保证原子操作，但是对多个共享变量操作时，循环 CAS 就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量 i=2，j=a，合并一下 ij=2a，然后用 CAS 来操作
  - 可以用 AtomicReference (java)，这个是封装自定义对象的，多个变量可以放一个自定义对象里，然后他会检查这个对象的引用是不是同一个。如果多个线程同时对一个对象变量的引用进行赋值，用 AtomicReference 的 CAS 操作可以解决并发冲突问题

4. 内存屏障

todo: 内存屏障之后看情况再补充。

内存屏障（也称为内存栅栏）是一种 CPU 指令，它确保屏障之前的所有操作完成后才执行屏障之后的操作。内存屏障可以防止编译器和处理器对指令重排序。

Load Barrier：加载屏障，确保所有在屏障前的读操作完成后，才执行屏障后的读操作。
Store Barrier：存储屏障，确保所有在屏障前的写操作完成后，才执行屏障后的写操作。
Full Barrier：全屏障，同时具有加载屏障和存储屏障的功能。

内存屏障(Memory Barrier),也被称为内存栅栏,是一种同步原语,用于防止指令重排,确保特定的内存操作顺序.

在多核处理器系统中,为了提高性能,处理器和编译器可能会对指令进行重排.这种重排可能会导致在多线程环境中出现问题,因为一个线程看到的内存操作顺序可能与另一个线程看到的顺序不一致.

内存屏障可以防止这种情况的发生.它可以强制特定的内存操作顺序,例如:

Load Barrier(加载屏障):保证在屏障之前的所有加载操作,都在屏障之后的加载操作之前完成.
Store Barrier(存储屏障):保证在屏障之前的所有存储操作,都在屏障之后的存储操作之前完成.
Full Barrier(全屏障):同时包含加载屏障和存储屏障,保证在屏障之前的所有内存操作,都在屏障之后的内存操作之前完成.

在 C++中,你可以使用std::atomic_thread_fence函数来创建一个内存屏障.例如,std::atomic_thread_fence(std::memory_order_acquire)会创建一个加载屏障,std::atomic_thread_fence(std::memory_order_release)会创建一个存储屏障,std::atomic_thread_fence(std::memory_order_seq_cst)会创建一个全屏障.

5. 总结

坦率地说，我觉得在国内技术团队里，真正透彻理解并能娴熟运用内存序的人并不多。毕竟，实际开发中需要如此精细优化性能的场景相对少见。当任务耗时较长时，采用锁机制和无锁机制保障线程安全，二者在任务耗时上的差异或许仅有百分之一。

所以，我反对在未进行性能测试的情况下，就贸然使用std::atomic开展无锁编程。要是在使用mutex（互斥锁）时出了错，多调试几次往往就能找出问题所在。然而无锁编程一旦出错，很可能是内存序设置不当所致，这类错误通常具有偶发性。而且，CPU 对内存序的排序行为影响显著，不同厂家生产的 CPU，其乱序行为很可能各不相同。就拿本文中的代码来说，我尝试采用宽松内存序，本希望能跑出失败结果，却根本无法复现。这种错误的偶发性，以及受机器和操作系统影响的特性，会给代码的可维护性带来极大挑战。我在查阅资料的过程中，经常能看到不少因使用内存序进行无锁编程而“翻车”的案例。

99. quiz

1. 无锁编程的时候，无脑使用严格内存序可以吗？

todo: 补充实测数据。

我一开始认为无锁编程的时候，是可以无脑使用严格内存序。但是进一步了解后，感觉严格内存序的开销也许不比上锁的开销小。既然如此，如果用了无锁编程，就得正确使用正确内存序。不然就老实用上锁编程。

性能对比，等我实测。

2. 多核 CPU 的缓存及缓存一致性维护

在多核 CPU 环境下，每个核心都配备高速缓存以加速数据访问。但多个核心同时操作同一份数据时，易引发数据不一致问题。例如，CPU 核心 A 和 B 都缓存了变量x，若 A 修改x值，B 仍使用旧缓存值，就会出现数据不一致情况。为此，多核 CPU 采用特定机制来保障缓存一致性。而保障缓存一致性常见的协议就是MESI协议。

MESI 协议概述：MESI 协议是常用的缓存一致性协议，其名称源于四个状态：Modified（已修改）、Exclusive（独占）、Shared（共享）和 Invalid（无效），每个缓存行都具备其中一种状态来表明当前状况。其核心原理就一句话，写入时，持有修改权的核心通知其他核心对应缓存行无效，确保各核心缓存与主内存数据一致。
MESI 协议原理：
- Modified（已修改）：此状态下缓存行数据已被修改，与主内存数据不一致，且仅有一个 CPU 核心可持有。
- Exclusive（独占）：缓存行数据与主内存一致，且仅一个核心持有。
- Shared（共享）：缓存行数据与主内存一致，多个核心可同时持有。
- Invalid（无效）：该缓存行数据无效，不可使用。
缓存一致性操作：
- 读取操作：若 CPU 核心读取的缓存行状态为 Invalid，需从主内存或其他核心缓存获取最新数据。
- 写入操作：CPU 核心写入缓存行时，要通知其他核心将该缓存行状态设为 Invalid。