算法与数据结构 / 并发数据结构 · 从 CAS 到无锁队列与内存回收 / 内存序 待审核 6 / 6
relaxed · acquire-release · seq_cst

内存序

前五页把每条原子指令当作一个不可分割的点，线程之间的差别只在这些点的排列。真实硬件比这个模型宽松：编译器会重排指令，CPU 会乱序执行与推测执行，各核的写入要经过 store buffer 才到达共享缓存。于是「T1 先写 A 后写 B」并不意味着 T2 会按同样的顺序看见它们。

原子操作的第二个参数管的就是这件事。C++ 把它叫 memory order，Java 用 volatile 与 VarHandle 的几档访问模式表达同一组语义。

1 · 两条规则的操作模型

本页的模型只有两条规则，其余全部由它们推出：

每个地址保留全部写入的历史，每个线程对每个地址各有一个「已看到第几条」的读视野。relaxed 与 acquire 载入可以读回视野之后的任意一条，含旧的那条；只有 seq_cst 载入被钉在最新的一条上。<br> release 写入随身带一份写者当时的读视野快照。acquire 载入读到这样一条写入时，把快照并进自己的视野。

第一条给出「读到过期值」，第二条给出同步边。两条合起来就是 release-acquire 的操作语义。

模型的边界要先说清楚：它覆盖读到过期值这一类现象，不模拟 store buffer 的提交次序，也不模拟推测执行。经典 litmus test 的结论它都给得出来，但它不是形式化的 C++ 内存模型，seq_cst 那一档尤其被简化成了「载入必读最新」。

2 · message passing

最常见的一种用法：一个线程写好数据再置标志，另一个线程见标志就读数据。

图 2-1 · message passing 与环形队列发布的 litmus test，穷举全部执行并按结果归类。可切换写侧与读侧的 order，下方矩阵给出九种组合各自的违例条数。

四条访问全用 relaxed 时，穷举得到 13 条可行执行，其中 1 条出现「标志已置、数据仍旧」。这一条不是模型的怪癖：写侧的两次写之间没有任何次序约束，读侧的第二次载入也不必读到最新值。

写侧改 release、读侧改 acquire 之后，可行执行降到 12 条，违例的那条消失。少掉的正是被同步边排除的那些。

只补一侧不管用，矩阵里看得最清楚：release 配 relaxed 仍有 1 条违例，relaxed 配 acquire 同样有 1 条。同步边要两端都在场——一端建立，一端接收。

3 · 环形队列为什么只需要 acquire-release

高频交易里的无锁环形队列 的发布动作与 message passing 同构：producer 先把数据拷进槽位，再推进 counter；consumer 先读 counter，判定这一段可读，再去读槽位。把 data 换成 slot、flag 换成 counter，是同一张图。

它需要的保证只有一条：看见 counter 已推进，就一定看得见 counter 推进之前拷进去的字节。这正是 release-acquire 给的，一分不多。

seq_cst 能给同样的保证，但它还额外要求全部 seq_cst 访问落在一个全局总序上。这条要求在环形队列里用不上——只有一个 producer 和它的 consumer 之间需要对齐，不存在第三方需要跟这两个线程的相对顺序取得一致。多要的这一层在 x86 上是一条 mfence，在 ARM 上是 dmb ish，纳秒级路径上首先要被干掉的就是它。

4 · store buffering

seq_cst 并非总是多余。有一类结果只有它排得掉。

两个线程各写一个变量，再各读对方那个。直觉上至少有一个线程应该看见对方的写：谁后写，谁就该看见先写的那个。实际上两边都读到 0 是可能的。

图 4-1 · store buffering litmus test 的全部执行与结果分布。可在 relaxed、acquire、seq_cst 三档之间切换，对照两边都读到 0 的执行条数。

relaxed 下的 20 条执行里有 6 条如此。换成 acquire 一条不少，仍是 6 条——acquire 只建同步边，不要求载入读到最新值。只有 seq_cst 把可行执行压到 6 条，违例归零。

这个结果在 x86 上真实可观察，成因是各核的 store buffer：写入先落进本核的缓冲区，随后才对其他核可见，而本核自己的读会从缓冲区直接取值。x86 的内存模型不重排 store-store 与 load-load，唯独允许 store 被后面的 load 越过，恰好就是这一种。

5 · 该用哪一档

建议 · 默认写 seq_cst。C++ 的原子操作不带 order 参数时就是它，这个默认值是刻意选的：seq_cst 下的程序可以用「所有原子操作有一个全局顺序」来推理，而这是唯一一种人不容易想错的模型。放松到 acquire 与 release 需要能说清「哪一条同步边保护哪些数据」，放松到 relaxed 则需要证明这些访问之间根本不需要任何次序。

有两处 relaxed 通常安全：一是纯计数器，只要总数最终正确、中间值无人依赖；二是 shared_ptr 那样的引用计数的递增（递减不行，它要与析构建立同步边）。除此之外，relaxed 的每一次使用都该配一段说明它为什么够用的注释。

注 · 本页模型的第一版让 acquire 载入也读最新值。跑 store buffering 时它给出「acquire 排除了两边读 0」，与真实硬件相反——acquire 在 x86 与 ARM 上都拦不住 store buffering。改成「只有 seq_cst 钉最新值」之后，message passing 那一侧的结论没有变化（release-acquire 仍然排除违例，因为同步边不依赖新鲜度），store buffering 这一侧才对上。两个 litmus test 分别卡住了模型的两个维度：一个查同步边，一个查新鲜度，缺一个就会做出一个自洽却错误的模型。

6 · 参考文献

  1. Boehm, H.-J., & Adve, S. V. (2008). Foundations of the C++ concurrency memory model. Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, 68–78.
  2. Batty, M., Owens, S., Sarkar, S., Sewell, P., & Weber, T. (2011). Mathematizing C++ concurrency. Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 55–66.
  3. Sewell, P., Sarkar, S., Owens, S., Nardelli, F. Z., & Myreen, M. O. (2010). x86-TSO: a rigorous and usable programmer's model for x86 multiprocessors. Communications of the ACM, 53(7), 89–97.
  4. Adve, S. V., & Gharachorloo, K. (1996). Shared memory consistency models: a tutorial. Computer, 29(12), 66–76.
  5. Sewell, P. C/C++11 mappings to processors. 各 memory order 在 x86、ARM、POWER 上分别编译成什么指令。https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html