C/C++ 中的内存序问题

在现代多核处理器环境下编程，内存序 (memory order) 是一个永远绕不开的话题。 同时，在阅读 CPython 等大型项目的源码时，也时不时会遇到各种关于内存序的操作，比如在 free-threaded build 下的引用计数问题。 本文尝试对 C/C++ 中的内存序问题进行总结。

原子操作

内存序问题源于原子操作和现代 CPU/编译器优化带来的乱序执行问题。 首先需要说明的是，原子操作本身并不会带来内存序问题，例如:

// <stdatomic.h>
int a = atomic_load(&ptr); // thraed A
atomic_store(&ptr, b);     // thread B

分别在两个线程中执行，无论何时 CPU 都会保证对 ptr 地址的读写是原子的 (另外还有 atomic_fetch_add、atomic_fetch_sub 等操作)。 即原子操作本身并不会带来并发和同步之类的问题，而是当原子操作和其他非原子操作同时出现时，这些非原子操作是否在其他线程的原子操作后被观测到，这才是内存序问题。 也就是说，内存序问题有两个必要条件: (1) 涉及多线程的原子操作，(2) 这些原子操作伴随着其他非原子操作。

现代 CPU 上的内存序

目前主流 CPU 和编译器支持的内存序主要有 ^{1 2}:

• relaxed
• acquire
• release
• acq-rel
• seq-cst

其中 acquire 仅针对 load 操作，而 release 仅针对 store 操作；acq-rel 则针对的是 load-modify-store 操作 (例如 fetch add)，而 seq-cst (顺序一致性) 则强调的是针对原子变量操作序列的全局一致性 (见下文)。 因此，要搞懂内存序问题，最重要的就是弄懂前面三种内存序 ³。 假设现在有一个原子变量 X，

这里我们说的重排是指在编写高级语言程序的时候在逻辑上表达的顺序。 假设现在有两个线程 1、2 分别对 X 进行写和读，内存序并不是说我们能够确定 1 和 2 两个线程对同一个原子变量的读写顺序 (到底是 1 在前面还是 2 在前面，这个要靠条件变量等其他机制确定)。 而是说，如果此时线程 2 的读发生在了线程 1 的写操作之后，那么线程 1 针对其他非原子变量 (地址) 的读写是否能被线程 2 观测到。 可以看出来，relaxed 是最松弛的，它并不保证非原子操作的跨线程可见性。 而 acquire 和 release 语义则要求编译器给针对 X 的原子操作施加一些 side effects。 所以我们说，如果采用了非 relaxed 的内存序，那么原子操作会引入一个隐式的线程内屏障 (memory fense) 和一次跨线程同步 (synchronization)。

首先对于原子写操作，release 要求如果在这之前 (用高级语言编写程序时的逻辑语序，就是我们代码中的前后位置关系) 有对其他变量的写，那么它要求编译器不要把这些写重排到这个原子写之后，这样能保证当其他线程读到 X 的某一次写的时候，伴随着这一次原子写的针对其他非原子变量的更新已经写到过对应的位置了。 类似地，针对原子读操作，acquire 要求我如果读到了一次其他 release 的 X 的值，那么伴随着这次 release 所附加的其他针对非原子变量的写也一定被更新到了对应的地址中。

搞懂了这三个概念，那么接下来的 acq-rel 就比较简单了，它是针对 RMW (read-modify-write) 操作的，例如 fetch add。 它保证了一次 RMW 操作中的读遵循 acquire 语义，而写操作遵循 release 语义。

那么最后一个 seq-cst 是用来做什么的呢？ 要知道上面我们讨论过的内存序都是针对同一个原子变量的，而如果你想要保证多个原子变量间读写的全局一致性，那么就需要采用最为严格的 seq-cst 序，假设我们有这样一份代码:

std::atomic<int> x(0), y(0);
std::atomic<int> z(0);

void write_x() { // thread 1
    x.store(1, std::memory_order_seq_cst); // (1) seq-cst store
}

void write_y() { // thread 2
    y.store(1, std::memory_order_seq_cst); // (2) seq-cst store
}

void read_x_then_y() { // thread 3
    while (!x.load(std::memory_order_seq_cst)); // (3) seq-cst load
    if (y.load(std::memory_order_seq_cst)) {     // (4) seq-cst load
        z++;
    }
}

void read_y_then_x() { // thread 4
    while (!y.load(std::memory_order_seq_cst)); // (5) seq-cst load
    if (x.load(std::memory_order_seq_cst)) {     // (6) seq-cst load
        z++;
    }
}

如果采用 std::memory_order_seq_cst 的话，那么 z 的值不是 1 就是 2，这是因为如果线程 1 和线程 2 二者都在 3、4 之前执行，那么线程 3、4 都会进入 if 分支，z 的值会是 2；而如果是以 1-3-2-4 这样的顺序执行的话，那么 z 的值就会是 1。 而如果采用 std::memory_order_acq_rel 或者更弱的内存序的话，z 最终的值有可能是 0，这是因为线程 3 和线程 4 看到的 x 和 y 的更新顺序有可能不一样，即 3 有可能看到 x = 1, y = 0，而 4 有可能看到 y = 1, x = 0 这样的情况，此时二者都不会执行 z++。 这是因为 acq-rel 或者更弱的内存序只保证了单个原子操作和其他非原子操作之前的可见性关系，而此时线程 1 和线程 2 都只有一个原子操作，它们之前的关系无法被 acq-rel 约束。 而如果你想要保证跨线程间的多个原子操作的一致性，就需要采用最强的 seq-cst，也就是说，顺序一致性保证了全局所有线程看到的变量的更新顺序是一致的，仿佛好像它们就发生在一个线程里面。

一些常见的使用用例

• 环形缓冲区实现的无锁队列，
  • SPSC: producer (tail = relaxed = acquire, tail = release), consumer (head = relaxed, tail = acquire, head = release)
  • SPMC: producer (tail = relaxed, head = acquire, tail = release), consumer (head = acquire, tail = acquire, head = CAS(acq-rel, relaxed))
• 多线程引用计数，incref 用 relaxed，decref 用 seq-cst (采用了 biased reference counting BRC ⁴)

一个常见的 pattern 是 (来自 free-threaded CPython 中的 DECREF 操作，省略了一些无关的操作):

static int
_Py_DecRefSharedIsDead(PyObject *o, const char *filename, int lineno)
{
    // ...
    Py_ssize_t new_shared;
    Py_ssize_t shared = _Py_atomic_load_ssize_relaxed(&o->ob_ref_shared);
    do {
        new_shared = shared - (1 << _Py_REF_SHARED_SHIFT);
    } while (!_Py_atomic_compare_exchange_ssize(&o->ob_ref_shared,
                                                &shared, new_shared));
    // ...
    return 0;
}

其中先采用 relaxed 序读取 shared ref count，然后尝试进行更新，利用 CAS 指令判断目标地址是否在更新的过程中发生变化:

static inline int
_Py_atomic_compare_exchange_ssize(Py_ssize_t *obj, Py_ssize_t *expected, Py_ssize_t desired)
{ return __atomic_compare_exchange_n(obj, expected, desired, 0,
                                     __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); }