Lecture 21: Memory Consistency

目录 · ← l19 · l21 →

Lecture 21: Memory Consistency

1. 章节标题与概述

Lecture 21: Memory Consistency（内存一致性模型：顺序一致性、宽松序、fence 与 DRF 契约）

• 本讲核心问题：“读一个地址应该返回最近一次写入的值”——可是”最近”到底是什么意思？ 讲义开篇（slide 3）就把这个看似显然的问题拆开：在线程内部，”最近”可以由 program order（程序序） 定义；但跨线程呢？如果定义为”物理时间上最近的那次写”，硬件根本做不到——”如果处理器之间通信需要 10 个周期以上，P0 就绝无可能知道 P1 在 2 个时钟节拍之前干了什么”。因此正确答案只能是：存在某个把所有线程的操作串起来的假想顺序（a hypothetical serializable order），读回来的值必须与这个顺序相容——而这个顺序不必是物理时间顺序。于是问题变成：我们要允许多少种串行化顺序？允许得越少，程序员越好写，硬件越慢；允许得越多，硬件越快，程序员越容易写出错的程序。这一讲就是在”正确性契约”和”性能”之间划出那条线。

• 涉及的主要硬件/软件机制：
  • 硬件侧：为了隐藏访存延迟而引入的三种重排来源——写缓冲（write buffer）（写延迟被”吃掉”，但其他核可能先看到我的读、后看到我的写）、乱序流水线 / 发射（out-of-order issue）与 Reorder Buffer（一条 cache miss 挂起时后续独立指令继续发射，因此访存被乱序执行）、分支预测与投机执行（speculative execution，预测错就 squash）；以及为把这些重排”圈回来”而提供的 fence / memory barrier 指令：Intel 的 MFENCE / LFENCE / SFENCE、隐式带锁的 xchg，和 C++11 的 std::atomic_thread_fence。芯片层面还依赖缓存一致性协议（MSI/MESI、BusRd/BusRdX/BusWB 事务）与互连这个串行化点，来保证”写何时算完成”这件事有唯一的仲裁者。
  • 软件侧：四种被模型允许或禁止的访存顺序约束（WX→RY、RX→RY、RX→WY、WX→WY）、由它们组合出的模型族（SC、TSO / Total Store Ordering、PC / Processor Consistency、PSO / Partial Store Ordering、WO / Weak Ordering、RC / Release Consistency）、acquire/release 语义、数据竞争（data race）与properly synchronized program、以及现代语言给出的 “SC for DRF”（data-race-free 程序获得顺序一致性）契约（C11 / C++11 / Java 5）。

• 在并行计算知识体系中的角色：这是”共享内存正确性”这条链上的最后一块拼图。前几讲分别回答了”多份缓存副本怎么保持一致”（缓存一致性 / MSI-MESI）、”怎么让它可扩展到多核”（目录一致性）、”同步原语怎么实现”（原子指令、锁、屏障）；本讲回答的是更高一层的问题：不同地址之间的可见顺序由谁定义。它把课程里所有”看起来能跑但偶尔错”的 bug 归因到一个统一的根源——程序里有数据竞争——并给出工程上的解法：要么用库提供的同步原语（lock/unlock/barrier）把程序变成 DRF，要么在无锁代码里精确地放置 fence 与 acquire/release。它也是下一讲 Fine-Grained Synchronization / Lock-Free Programming 的前置知识：无锁数据结构里每一处 relaxed / acquire / release 的取舍，都直接由本讲的一致性模型决定。

• 配套材料：
  • lectures/15_consistency.pdf（抽取文本 extracted/15_consistency.txt，共 40 页）——已公开，可在公开网络直接下载。Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）把 Oct 21 排为第 21 讲 “Memory Consistency”，该行的 slides/video 链接目前以 HTML 注释形式给出（注释原文：”slides/video from a previous offering; uncomment when posted for Fall 2026”），注释中的 slides 指向 lectures/15_consistency.pdf，video 指向一个归档 YouTube 链接。该 PDF 位于公开目录 https://www.cs.cmu.edu/~418/lectures/ 之下。两点说明（不是错误）：①文件编号 15 与 Fall 2026 讲次 21 不一致，且讲义首页写的是 “CMU 15-418/15-618, Fall 2025 / Lecture 15: Memory Consistency”——这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排）；②PDF 中有几页（如第 2、4 页，以及第 6、21 页的图示部分）在文本抽取中为空，因为它们本身是纯图片页或图多于文，本笔记对这些内容只依据同页可见文字与公开成熟知识展开，不冒充原文数据。
  • cs149_supp/sync_consistency.txt（抽取文本，共 60 页）——已公开。Stanford CS149（Fall 2025）Lecture 15: Memory Coherency and Consistency：前 20 页（slide 1–20）讲缓存一致性（MSI/MESI 状态机、目录一致性、伪共享实测 14.2 s vs 4.7 s、Core i7 存储层次延迟），从 slide 21 起进入 Memory Consistency：SC 的开关隐喻、”写缓冲如何改变内存行为”、TSO / PC / PSO / WO-RC、fence、数据竞争与 DRF、语言级内存模型。它是本讲最完整的公开文本来源之一，本笔记用它补足 CMU 讲义中只给图示的部分，并对齐两边的结论。
  • 讲义中引用的外部材料：Lamport 1979 的 SC 形式化（slide 19）；Gupta et al., “Comparative evaluation of latency reducing and tolerating techniques”, ISCA ‘91（slide 26 的性能数据出处）；Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A, Section 8.2 / 8.2.5（fence 指令规格）；ARM Barrier Litmus Tests and Cookbook；以及剑桥的弱内存模型文献列表 http://www.cl.cam.ac.uk/~pes20/weakmemory/。
  • 未发布 / 需登录：本讲的讲课录像（Panopto / YouTube）在 Fall 2026 日程表中被注释隐藏，属未发布；Ed 讨论区、Autolab、Canvas 均需登录，非公开。部分讲座（Performance Analysis/Profiling、Transactional Memory、AI in System Design 等）在 Fall 2026 尚未发布讲义，其历史学期 PDF 位于 /afs/cs/academic/class/15418-*/public/ 之下，需要 CMU 登录，属未公开。
  • 课程语境：Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。前一讲为 Lecture 20 “Guest Lecture”（Oct 19，讲义未公开），后一讲为 Lecture 22 “Parallel Deep Learning (data parallelism)”（Oct 23，对应公开 PDF 24-parallel_deep_learning_data_parallel.pdf）。

2. 核心概念与硬件/软件架构图解

2.1 先分清两个问题：Cache Coherence 与 Memory Consistency

• 定义与目的：讲义在 slide 8 把”并行内存层次结构的正确行为”明确拆成两半：
  1. Cache Coherence（缓存一致性）：对同一个 cache block 的所有 load/store 是否表现正确？
  2. Memory Consistency Model（内存一致性模型），有时也叫 Memory Ordering：对（即使位于不同 cache block 的）所有 load/store，整体是否表现正确？ CS149 的讲义（slide 24–25）把这条界线说得更直白：coherence 只保证”对 X 的写最终会传播到其他核”，consistency 决定的是”对 X 的写相对于对其他地址的读写，何时传播”。更进一步：”缓存一致性的目标是让有缓存的多核内存系统表现得好像缓存不存在；而 memory consistency 描述的是地址与地址之间允许的行为——无论系统里有没有缓存，这个问题都要回答。”
• 直观解释（”它是什么？”）：把共享内存想成同一家公司里的多块白板（不同地址）。
  • Coherence 管的是同一块白板上的一次涂改：所有人最终看到的是同一个笔迹序列，不会出现”A 看到 5、B 看到 3”这种对同一块板的分歧。它像”白板管理员”（互连上的串行化点）——一行的分歧由管理员仲裁。
  • Consistency 管的是两块白板之间的先后：我在 A 板上写了”货已到”，又在 B 板上写了”请取货”。别的同事先看到哪块板？coherence 对此一句话都没说——它只保证两块板上的新字最终都会传出去。于是完全可能：对方先看到 B 板的”请取货”，跑去一看 A 板还是旧字。
  • 这个类比的结论是：coherence 管”同一个地址的历史”，consistency 管”不同地址之间的相对顺序”；前者是缓存引起的，后者不是。
• 图 1：两个问题的作用范围（同一地址的时间线 vs 跨地址的相对顺序）

  ── Coherence 的问题范围：同一个地址 X 的一条时间线 ──────────────────────────
       address X 的时间线:   P0:W(5)   P1:R(5)   P2:R(5)   P2:W(10)   P1:R(10)
                             └────────────────┬──────────────────────────────┘
        不变量：SWMR（单写者多读者）+ 写串行化 + 读回"串行序中的最后一次写"
        允许并发：多个 S 态读者；一旦有人要 W，其他副本全部失效
        ★ 有缓存才有这个问题（多份副本）；没有缓存就不需要 coherence

  ── Consistency 的问题范围：不同地址之间的可见顺序 ──────────────────────────
       address X:   P0:W(X=1) ────────────────────────────►（何时对 P1 可见？）
       address Y:      P0:W(Y=1) ─────────────────────────►（何时对 P1 可见？）
                              ▲
                              └── 真正的问题在这里：X 的写与 Y 的写之间，
                                  P1 可能只看到其中一个（顺序被交换/被拖延）
        ★ 无论有没有缓存都要回答；它是一条"硬件/编译器 vs 程序"的契约
        ★ 不能用锁"修好"：锁修的是 mutual exclusion（互斥），
          而"多份副本"与"重排"是硬件实现导致的、锁管不到的现象

• 性能特征：coherence 的代价表现为一致性流量（一行 ping-pong、伪共享），可用”每条 cache line 字节数 × 事务数 / 互连带宽”来估算；consistency 的代价表现为被禁止的优化（写缓冲能否用、能否乱序发射、能否投机），最终体现在处理器利用率上——讲义 slide 26 引用 Gupta et al. 的数据：严格的 SC 实现即使有缓存，处理器利用率也只有 17%–42%。

2.2 为什么”最新值”无法定义：program order 与 physical time 的分离

• 定义与目的：讲义 slide 5 用一个经典例子把”跨线程的最近”逼到墙角（下面的 X 初值为 0，且这些是唯一的写）：

// Thread 0：把偶数写进 X          // Thread 1：把奇数写进 X        // Thread 2：读三次
for (i = 0; i < N; i += 2) {       for (j = 1; j < N; j += 2) {     A = X;
    X = i;                             X = j;                         ...
    ...                                ...                            B = X;
}                                  }                                  ...
                                                                      C = X;

讲义问：(A,B,C) 中哪些组合”明显非法”？ 例如 (4,8,1)、(9,12,3)、(7,19,31)。

• 你能确定的只有两条：① 同一线程的写必须与 program order 一致——所以观察到的偶数必须递增（奇数同理）；② 跨线程时，写必须与”线程的某个合法交错（valid interleaving）”一致——而不是与物理时间一致。

• 也就是说 (4,8,1) 是合法的（等价于”交错”里 T0 先写了 4、8，然后 T1 写了 1，之后 T2 才读），而 (8,4,…)（偶数递减）非法。

• 直观解释（”它是什么？”）：把三个线程想成三个厨师往同一口锅里撒调料，你站在锅边尝三次。你尝到的味道必须能由某个“按顺序一个个撒”的过程解释出来（哪怕实际上他们是同时撒的、撒的顺序你无从得知）。这就是”存在一个假想的串行交错”的含义——讲义 slide 7 特别强调：“这是一个假想的交错；机器并不一定真是这样执行的！”

• 图 2：SC 的”开关”模型（软件执行模型）vs 真实硬件（硬件结构）

【左】SC 的 switch 模型（Lamport 1979 / CS149 slide 31）：
      内存每一步只服务一个处理器的一条访存，服务完再随机挑下一个。
              +------------------------------------------+
              |  Memory   A=0  B=0  X=0   (单一串行序)   |
              +------------------------------------------+
                 ^          ^           ^          ^
    一次只放行一个|          |           |          |
              +-------+  +-------+   +-------+  +-------+
              |  P0   |  |  P1   |   |  P2   |  |  P3   |
              | A = 1 |  | B = 1 |   |       |  |       |
              | r1= B |  | r2= A |   |       |  |       |
              +-------+  +-------+   +-------+  +-------+
   规则：每个处理器内部按 program order 发射；内存一次执行到底。
   等价说法：所有访存存在一个全局串行序，且该序与每个线程的 program order 相容。

【右】真实硬件：为了藏住延迟，几乎一切都可以被重排（slide 9–13）
   program order（程序员看到的）            硬件实际做的事
   -------------------------------------    -----------------------------------
   x = *p;     (L1 miss, 100+ 周期)    --->  挂起这条 miss
   y = x + 1;  (真依赖 true dependence)--->  必须等 x，无法发射
   z = a + 2;  (无关)                  ---> 【越过上面的 miss 先发射】
   b = c / 3;  (无关)                  ---> 【越过上面的 miss 先发射】
   if (x != z) d = e - 7;              ---> 分支预测 + 投机执行；猜错则 squash
   结论（slide 9）："处理器在单线程内维持了 program order 的幻觉，但这个幻觉
   与物理时间毫无关系；从其他线程的视角看，一切皆有可能。"

2.3 硬件为什么会重排：写缓冲、乱序发射与投机执行

• 定义与目的：讲义 slide 10–13 给出重排的三个物理来源，并且强调”隐藏访存延迟对性能至关重要“：
  1. 写缓冲（write buffer）：在单处理器上隐藏写延迟的最简单办法。”（但它在多处理器上影响正确性）”。
  2. 乱序流水线（out-of-order pipelining）：”当一条指令卡住时，也许后面还有能执行的指令”——推论：访存可能被乱序执行！
  3. 分支预测 + 投机执行：条件分支不必等结果，先猜、先执行，猜错再回滚。 slide 13 给出微架构画面：取指与退休（graduate/retire）按序，但发射（issue）乱序；线程内依赖被保持，访存被重排。

• 直观解释（”它是什么？”）：把写缓冲想成快递代收点。你把包裹放到代收点（store 进写缓冲），就算”寄完了”，可以立刻去干别的；代收点随后慢慢发车（冲刷到一致性域）。问题是：你的朋友此时打电话问”我的包裹到了吗”（其他核的 load），代收点还没发车，他当然说”没有”——虽然你早就”寄”了。乱序流水线则像超市的多个收银台：前面那位顾客的扫码枪坏了（cache miss），后面排队的顾客会被引导到别的台子先结账（乱序发射）——结账（退休）顺序还是按照排队的号，但”谁先被服务”完全乱了。

• 图 3：写缓冲 + 乱序发射的硬件结构（含关键操作与延迟特征）

      +---------------------- Processor core ------------------------+
      |  Fetch(in-order) -> Decode -> Rename -> Issue(OUT-OF-ORDER)  |
      |                                              |               |
      |                                       +------v-------+       |
      |                                       | Reorder      |       |
      |                                       | Buffer (ROB) |---+   |
      |                                       +--------------+   |   |
      +----------------------------------------------------------|---+
                                                                 |
                                     +---------------------------v--------------+
        LOADS  <---------------------+--+  Load Queue (检查写缓冲 = store-to-  |
                                     |  |              load forwarding)      |
                                     |  +----------------+                    |
                                     |  +----------------v---+   +----------+ |
        WRITES --------------------->+--| L1 D-Cache / MSI |   |  Store   |-+--> 一致性域
                                     |  | 状态: M/E/S/I    |   |  Buffer  |      (L2/L3/互连)
                                     |  +------------------+   | (写缓冲) |      与互连的
                                     +-------------------------+----------+      串行化点
      关键操作与性能特征
      -------------------
      * load 命中 L1:            约 4 周期（CS149 slide 14 数据）
      * load 命中 L2:            约 10 周期
      * load 命中 L3 但行在别的核:  约 65 周期（shared）/ 约 75 周期（modified）
      * load 落到本地 DRAM:       约 30 ns ≈ 120 周期
      * load 落到远端 DRAM:       约 100 ns ≈ 400 周期（NUMA）
      * store: 只要写进缓冲就"完成"（对发射流水线而言），延迟被隐藏；
        但它对**其他核**何时可见，取决于何时从缓冲冲刷到一致性序 —— 这就是
        WX -> RY 被重排的物理来源，也是 x86-TSO 唯一放松掉的那一条约束。

• 性能特征：写缓冲把写延迟从关键路径上摘掉（这是 TSO 相对 SC 的全部收益来源），但它带来一个不可逆的正确性后果：本线程后面的读可能”绕过”本线程前面的写。乱序发射与投机执行把读延迟藏进指令级并行（ILP）里，代价是读与读、读与写之间的顺序也可能被交换。二者的共同本质：硬件的优化都是”对单线程语义无损”的，而对多线程语义是有损的（CS149 slide 48 的原话：”这些都是合法优化——如果程序只包含一条指令流的话”）。

2.4 Sequential Consistency（SC）：程序员的心智模型

• 定义与目的：Lamport 1979 形式化（slide 19；CS149 slide 30 记为 Lamport 1976，两者都指向同一篇工作）：
  • 每个处理器的访存按 program order 出现；
  • 所有访存出现在一个顺序（sequential）序中。 等价地（CS149）：所有操作在某个顺序序中执行，就像它们在操作一块单一共享内存，且每个线程的操作按程序序发生。讲义指出：”程序员隐含假设的任何顺序都被保持。”

• 直观解释（”它是什么？”）：SC 就是把多核当单核用：想象一台机器只有一条内存总线和一个开关，开关轮流接通一个处理器，让它把下一条访存执行完，再换下一个（CS149 slide 31 的 “switch metaphor”）。对程序员，这等价于”并发 = 交错的串行“——你不需要知道任何硬件细节，只需像分析单线程交错那样分析。这正是教科书式的共享内存语义。

• 图 4：SC 的实现方式（”一访问一停顿”）与它的性能灾难

  实现 SC 的两条规则（slide 22）：
  (1) 实现 cache coherence  ->  对同一地址的写被所有处理器以相同顺序观察到
  (2) 每个处理器：下一条访存必须等上一条"完成"才开始
      -> 每个处理器任何时刻只有 1 个 outstanding memory access

  什么叫"完成"（slide 23–24）？
    读：返回值被绑定（its return value is bound）时完成。
    写：新值对其他处理器"可见"时完成 —— 注意"可见"**不**意味着别人已经看到，
        而是意味着该写已经提交到 **HSO（hypothetical serializable order，
        假想可串行化顺序）**：HSO 中对该地址的后续读只能看到这个值或更晚的值。
        （讲义为简化假设写是原子的。）

  执行时间线（每一格都是一次访存，格子里的等待是硬性停顿）：
    LD ----[ 等 L 周期 ]----> LD ----[ 等 L 周期 ]----> ST ----[ 等 L ]----> LD ---
    |<---------------- 处理器利用率 = 理想发射时间 / 实际时间 ---------------->|
    ★ 讲义 slide 26：即使有缓存，处理器利用率也只有 17% - 42%
      （数据来源：Gupta et al., ISCA '91）

  气球类比（slide 25）：SC 相当于"在**每一个**有序的气体粒子之间都打一个扭结"
    —— 粒子完全不能乱动，性能自然崩坏。

• 性能特征：SC 禁止了三件价值极高的优化：写缓冲（W 无法被隐藏）、乱序发射（R 无法被隐藏）、编译器的寄存器分配与代码移动（code motion）。因此它的代价不是”多几条指令”，而是把内存延迟完整地暴露在关键路径上——延迟 L 有多大，损失就有多大（见第 4 节算例）。

2.5 解耦出四类 ordering，以及各模型放松了哪一条

• 定义与目的：CS149 slide 27 把”程序序中的两条相邻访存 op1 → op2”按类型分成四类，这样就能逐条讨论”哪些可以放松”：

讲义 slide 26–28 与 CS149 slide 37–49 用同一套图表达这件事：SC 保持全部四条；TSO/PC 只放松 WX→RY；PSO 再放松 WX→WY；WO/RC 在同步点之间放松全部四条。slide 28 直接给出 TSO 与 PSO 的图示对比，并指向 Intel SDM Vol. 3A 第 8.2 节。

• 直观解释（”它是什么？”）：把四条约束想成四道不同强度的”队规”：
  • WX→RY 是”寄完信再去问别人有没有给我寄信“——允许你在信还在路上的时候就去问（写缓冲）；
  • RX→RY 是”两个窗口同时问，谁先回答算谁的“——允许两个读乱序返回；
  • RX→WY 是”先打听清楚再下单“——允许你先把打听的请求发出去、把下单压后；
  • WX→WY 是”两封信的寄出顺序“——允许两封信被合并或换序装车。 放松的条数越多，硬件越自由、越快，而程序员需要自己补的”故事”越多。
• 表 1：主流内存一致性模型对比（综合 CMU slide 27–28、33、37–38 与 CS149 slide 43–51）

• 性能特征：模型越弱，”能藏起来的延迟”越多。CS149 slide 42 给出的对比曲线里，横轴是 SC（”Base”）与放松 W→R 的版本（”W-R”）：放松 WX→RY 之后，写延迟几乎被完全隐藏——这就是为什么”每一款现代处理器都使用写缓冲（Intel x86、ARM、RISC-V）“（CS149 slide 43），也因此都必须提供比 SC 更弱的内存模型。

2.6 fence：在气球上打一个跨线程可见的”扭结”

• 定义与目的：讲义 slide 33 用 Intel 的 MFENCE 说明 fence 的语义：
  • MFENCE 之前：该线程所有先前的读与写都必须完成，MFENCE 才能开始；
  • MFENCE 之后：该线程任何后续的读或写都必须等 MFENCE 结束才能开始。 讲义用气球类比总结：”fence 就是气球上的一个扭结——没有任何气体粒子能穿过它。” 好消息（slide 34）：xchg 隐式地做了这件事（x86 上带内存操作数的 xchg 自带 lock 语义，等价于全屏障）。

• 直观解释（”它是什么？”）：想象一列正在乱跑的孩子（重排的访存）。你不能让他们站好队（那会毁掉性能），但可以在走廊上放一道闸门：闸门左半边的孩子必须全部通过闸门之后，右半边的孩子才能开始通过。于是闸门两侧的相对顺序对走廊外的人（其他线程）是确定的，而同一侧内部依然可以乱跑。fence 的全部价值就在这个”局部有序、全局可观察“的折中上。

• 关键澄清（讲义 slide 35，最常见的误解）：“MFENCE 不会把值推给其他线程。” 它不是“让所有线程立刻看到最新值”的魔法操作；它只是让执行它的那个线程停顿。它真正产生的效果是：MFENCE 在跨线程可观察的偏序上引入了若干约束。

• 图 5：fence = 气球上的扭结（跨线程可观察的偏序）

  Thread 0 的气球（每个粒子 = 一条访存指令；编号 = program order）
    ... 3  1  5  2  4 | 8  6  9  7 | 11 10 12 ...
                      ^            ^
                      |            |
                   MFENCE        MFENCE     <-- 扭结：粒子无法穿越
  ┌──────────────────────────────────────────────────────────────────────────┐
  │ 扭结之前的集合 {…1,2,3,4,5} 与之后的集合 {6,7,8,9,…} 之间的相对顺序，   │
  │ 对所有线程都是一致的可观察事实（跨线程偏序）；                            │
  │ 但每个集合**内部**仍然是乱序的 —— 这正是"打扭结"而不是"排队"的意义。     │
  └──────────────────────────────────────────────────────────────────────────┘

  四个线程放 fence 的效果（slide 35 的示意图）：
       Thread 0:  4  3  1  5  2 | 5  1  4  3  2
       Thread 1:  2  3  4  1  5 | 3  5  2  1  4
       Thread 2:  1  5  4  2  3 | 2  3  4  5  1
       Thread 3:  3  2  5  1  4 | 4  1  5  2  3
                              ^
                        MFENCE 把时间轴切成"段"，段与段之间的先后
                        对所有线程可见；段内任意乱序。

• Intel 的三种 fence（讲义 slide 38 + CS149 slide 51）：

• 性能特征：fence 的代价是排空（drain）：MFENCE 必须等到所有未完成的 store 从写缓冲冲刷到一致性序。若写缓冲里有 k 条未提交的 store、每周期能冲刷 1 条，则代价 ≈ k 个周期再加流水线扰动；空缓冲时约 20–40 周期（3 GHz 下约 7–13 ns），缓存/互连拥塞时可达成百周期——但注意这只是“排空”那一部分的成本：示例一在真实 x86 上实测到的端到端边际成本是 +43 ns/轮（≈133 周期），因为 fence 还额外牺牲了“读与写重叠”这个优化。所以 fence 的正确用法是”少而准“：能一次 fence 覆盖一批共享更新，就绝不做”每元素一次 fence”（见第 4 节的 fence 吞吐算例）。

2.7 数据竞争、properly synchronized program 与 DRF 契约

• 定义与目的：讲义 slide 30–31 给出严格定义：
  • 冲突（conflict）：两次访存访问同一地址，且至少一次是写；
  • ordering：按 program order (po) 或 dependence order (do)（若 op2 读到 op1 的结果，则 op1 → op2）；
  • 数据竞争（data race）：两次冲突的访存在不同处理器上，且中间没有别的访存把它们排好序（not ordered by intervening accesses）；
  • properly synchronized program（正确同步的程序）：所有同步都被显式标识，并且所有数据访存都通过同步而被排序。

• 关键定理（”为什么我们还能活下去”）：CS149 slide 54 给出结论——“同步的程序在非 SC 系统上产生 SC 的结果”：”If there are no data races, reordering behavior doesn’t matter（没有数据竞争，重排就无关紧要）”，因为访存已被同步排好序，而同步强制了顺序一致性。slide 59 把它抬到语言层：C11 / C++11 / Java 5 保证”对无数据竞争的程序提供顺序一致性”（SC for DRF）——编译器会替你插入应对硬件内存模型所需的同步；而“如果你的程序有数据竞争，则没有任何保证”。

• 直观解释（”它是什么？”）：把程序想成一份会议纪要。同步操作（lock/unlock/barrier/acquire/release）就是纪要里的”分节标题”；DRF 意味着每一段共享数据的讨论都被某个分节包住了。这种情况下，同一节内部谁先谁后无所谓（那是”私人活动”，slide 32 的措辞：临界区内”插入数据结构的节点”本质上是 private 的，随便重排都行），而节与节之间的先后是硬性的。反过来说：没有分节标题的纪要，谁读都可能读出不同的时间线——那就是数据竞争（未定义行为），也是本讲所有”诡异 bug”的统一来源。

• 图 6：release/acquire 如何把两段”私人活动”缝成跨线程的偏序（软件执行模型）

   Thread A (producer)                        Thread B (consumer)
   -------------------                        -------------------
   data = 42;              (1)
        |  po（program order）
        v
   flag.store(1, release)  (2)  ===== synchronizes-with =====>  (3) flag.load(acquire)
                                                                     |  po
                                                                     v
                                                             r = data;            (4)
   ── 偏序图（happens-before DAG）─────────────────────────────────────────────
        (1) --po--> (2) --sw--> (3) --po--> (4)
        于是 (1) happens-before (4)：消费者在 (4) 处**必然**读到 42。
   ── 若把 (2)/(3) 换成 relaxed ───────────────────────────────────────────────
        (2) 可与 (1) 重排；消费者侧 (4) 也可能被提前发出
        => 可能出现 (3) 看到 flag=1 而 (4) 读到 data=0
   ── 若用 WO（Weak Ordering）而不是 RC（slide 33、37）──────────────────────
        WO：lock 和 unlock **两侧**都必须等先前操作全部完成（过于保守）
        RC：unlock 前只需保证"我的写"完成，lock 后只需保证"我的读"不早于它
            => 单个同步操作要等的操作数减少，这就是 RC 相对 WO 的收益（slide 37：
               "Overly Conservative" 的箭头正好画在 WO 多余的那一侧）

• 性能特征：DRF + RC 的组合把”一致性模型的复杂度”从应用代码里赶进库里：应用程序员看到的是 lock/unlock、barrier、atomic<int>，而 acquire/release 的具体位置由库作者决定（slide 40 的总结：”in practice: complexities often encapsulated in libraries that provide intuitive primitives”）。库作者则必须为每一次同步事件支付 fence/原子的代价——这就是第 4 节要算的账。

3. 代码示例与性能分析

说明：以下四个示例都是自包含、可直接编译运行的程序，用于把讲义中的”结果可能性 / fence 位置 / 一致性流量”变成可测量的事实。硬件相关的观测（例如 x86 上是否出现 (0,0)）依赖具体微架构、核数与线程绑定；请按注释里的 taskset 把线程固定到不同物理核上再测量，否则同一物理核上的超线程会掩盖重排现象。

3.1 示例一：Store Buffering（SB）石蕊测试——用实验测出 x86 放松了哪一条

石蕊测试（litmus test）是内存模型的”最小判别程序”：它小到可以逐条推演，又真到能在硬件上跑出结果分布。本示例把同一个 SB 程序放在三种顺序强度下各跑 $10^6$ 轮，统计四种结果组合的出现次数。

// litmus_sb.cpp —— Store Buffering (SB) 石蕊测试
//   同一个 SB 程序在三种"顺序强度"下的行为对比：
//     RELAXED : 两侧 store/load 都用 memory_order_relaxed
//               -> x86 上编译成普通 mov，写留在写缓冲里（真正的"宽松"）
//     FENCED  : 同样用 relaxed，但在**本线程的 store 与 load 之间**插入
//               atomic_thread_fence(seq_cst)（x86 上是一条 full barrier）
//     SEQ_CST : 两侧都用 seq_cst 原子操作（x86 的 store 编译成 xchg）
//   每个"轮次"统计 (r0, r1) 的四种组合出现次数，并给出每轮耗时。
//
// 编译: g++ -O2 -std=c++17 -pthread litmus_sb.cpp -o litmus_sb
// 运行: taskset -c 0,1 ./litmus_sb 1000000     # 必须绑到两个不同的物理核
//
// 两个实测踩过的坑（都写在代码里，别踩第二次）：
//   1) mode 必须是**编译期常量**（下面的模板参数）。若把 mode 当运行时变量，
//      gcc -O2 会把 relaxed 与 seq_cst 两条路径**合并**、统一生成 xchg，
//      于是 "relaxed" 实验悄悄变成 seq_cst 实验，结论完全反了。
//   2) fence 必须夹在**本线程 store 与 load 的中间**。放在 store 之前只是排空
//      上一轮遗留的写缓冲，对 WX->RY 毫无作用（实测 (0,0) 照样大量出现）。
#include <atomic>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <thread>

static constexpr int NT = 2;                 // 只需要两个线程
enum Mode { RELAXED = 0, FENCED = 1, SEQ_CST = 2 };

std::atomic<int> X{0}, Y{0};                 // 两条被跨线程观察的"消息"
std::atomic<int> arrived{0};                 // 已到达栅栏的线程数
std::atomic<int> generation{0};              // 栅栏世代，单调递增
long count[2][2];                            // count[r0][r1]
int  r[NT];                                  // 本轮各线程读到的对方值

// 简易 sense-reversing 栅栏（它本身就是一段 acquire/release 同步代码）：
// 返回 true 表示"我是最后一个到达者"，由它负责本轮结果的记录与变量归零。
static bool barrier_wait() {
    int g = generation.load(std::memory_order_acquire);       // 先记住当前世代
    if (arrived.fetch_add(1, std::memory_order_acq_rel) == NT - 1) {
        arrived.store(0, std::memory_order_relaxed);          // 重置计数
        generation.fetch_add(1, std::memory_order_release);   // 放行其余线程
        return true;
    }
    while (generation.load(std::memory_order_acquire) == g) { }   // 自旋等世代变化
    return false;
}

template <int MODE>
static void worker(int id, long iters) {
    // 编译期常量：RELAXED / FENCED 用 relaxed，只有 SEQ_CST 用 seq_cst
    constexpr std::memory_order ORD =
        (MODE == SEQ_CST) ? std::memory_order_seq_cst : std::memory_order_relaxed;
    for (long it = 0; it < iters; ++it) {
        barrier_wait();                        // A: 上一轮结果已记录、X/Y 已归零
        if (id == 0) {
            X.store(1, ORD);                                   // (1) 发布
            if (MODE == FENCED)                                // (2) 关键位置！
                std::atomic_thread_fence(std::memory_order_seq_cst);
            r[0] = Y.load(ORD);                                // (3) 观察对方
        } else {
            Y.store(1, ORD);
            if (MODE == FENCED)
                std::atomic_thread_fence(std::memory_order_seq_cst);
            r[1] = X.load(ORD);
        }
        if (barrier_wait()) {                  // B: 两个 load 都已完成
            count[r[0]][r[1]]++;               // 最后一个到达者独占记录
            X.store(0, std::memory_order_relaxed);             // 归零，准备下一轮
            Y.store(0, std::memory_order_relaxed);
        }
    }
}

static void run(const char* name, void (*fn)(int, long), long iters) {
    count[0][0] = count[0][1] = count[1][0] = count[1][1] = 0;
    r[0] = r[1] = 0;
    X.store(0); Y.store(0); arrived.store(0); generation.store(0);
    auto t0 = std::chrono::steady_clock::now();
    std::thread a(fn, 0, iters), b(fn, 1, iters);
    a.join(); b.join();
    auto t1 = std::chrono::steady_clock::now();
    double s = std::chrono::duration<double>(t1 - t0).count();
    std::printf("%-10s %9ld %9ld %9ld %9ld %8.3f %8.1f\n", name,
                count[0][0], count[0][1], count[1][0], count[1][1],
                s, s / double(iters) * 1e9);
}

int main(int argc, char** argv) {
    long iters = (argc > 1) ? std::atol(argv[1]) : 1000000L;
    std::printf("%-10s %9s %9s %9s %9s %8s %8s\n",
                "mode", "(0,0)", "(0,1)", "(1,0)", "(1,1)", "time/s", "ns/round");
    run("relaxed",   &worker<RELAXED>, iters);
    run("fenced",    &worker<FENCED>,  iters);
    run("seq_cst",   &worker<SEQ_CST>, iters);
    return 0;
}

【代码做什么？】

1. 建立”轮次”结构：主线程只负责 join；两个 worker 线程每一轮跑完全相同的三步——栅栏 A → 一次写 + 一次读 → 栅栏 B。栅栏用 sense-reversing 风格实现：先记住当前世代 g，用 fetch_add(acq_rel) 计数，最后一个到达者重置计数并 release 地推进世代，其余线程 acquire 地自旋等待世代变化。栅栏 A 同时承担两个职责：保证上一轮的 X、Y 已归零，并让两个线程尽可能同时开始（否则重排窗口会消失）。
2. SB 的两次访存：id==0 做 X=1; r0=Y;，id==1 做 Y=1; r1=X;。这正是讲义 slide 16 那个”跨地址顺序”问题的最小形式：两次访存地址不同（不是 coherence 问题）、至少一次是写（是冲突）、中间没有任何同步（是数据竞争）。
3. 三种模式必须是编译期常量：MODE 作为模板参数，ORD 才是真正的 compile-time constant。这样 RELAXED / FENCED 路径生成的是普通 mov（写留在写缓冲里），而 SEQ_CST 路径生成 xchg。这一点不是严格的： 如果改用运行时变量传 mode，gcc -O2 会把两条路径合并并统一生成 xchg，于是”relaxed 实验”实际跑的是 seq_cst——本笔记在调试时就撞上了这个坑（见下文”两个坑”）。
4. fence 的精确位置：FENCED 模式的 fence 夹在 (1) 本线程的 store 与 (3) 本线程的 load 之间。这是整个实验的成败关键：它让”我的写已提交到一致性序”成为”我的读可以发出”的前提条件。若把 fence 放成 fence; store; load，它就只是排空了上一轮遗留的写缓冲，对 WX→RY 一点用都没有。
5. 结果记录与归零：由栅栏 B 的最后一个到达者统一记录 count[r0][r1] 并把 X、Y 归零，避免两个线程同时写统计结构造成新的竞争；同时它保证归零发生在下一轮的栅栏 A 之前（release/acquire 传递），因此每一轮都从 X=Y=0 开始。程序最后按模式打印四种结果的次数、总时间与每轮纳秒数。

【并行机制与性能解说】

• 硬件上发生了什么：两个 worker 绑在不同物理核上（taskset -c 0,1，本机 core 0 与 core 1 各自独占一个物理核、无 SMT 兄弟），X、Y 所在的行通过一致性协议在两个核的私有缓存之间转移。
  • RELAXED：X=1 进写缓冲后立即发射 r0 = Y 的读请求。读请求不必等写提交，于是两个线程的读很可能都在对方的写提交之前被服务 ⇒ (0,0) 这个 SC 明令禁止的结果被硬件真的产生出来。
  • FENCED / SEQ_CST：读被强制推迟到自己的写提交之后，于是 (0,0) 不可能出现（因为若两边都读到 0，就会推出”我的写提交在你的读之后”与”你的写提交在我的读之后”同时成立，见第 7 节 Q1 的环论证）。
• 实测记录（表 2）：AMD EPYC 7V13（Zen 2，双路，两个核同 socket，实测主频约 3.1 GHz），g++ -O2 -std=c++17 -pthread，taskset -c 0,1 ./litmus_sb 1000000，共跑三次；每次 100 万轮。

• 可以从数据里读出的四条结论：
  1. (0,0) 在 relaxed 模式下确实出现，占比 13%–30% ⇒ 这不是”理论上的可能”，而是本机 x86 硬件反复产生的事实；它直接坐实了”x86 只是 TSO，允许 WX→RY 被写缓冲重排“，也解释了 CS149 slide 43 为什么要把 x86 的内存模型单独命名为 “incompletely specified form of TSO”。
  2. (0,0) 在 fenced 与 seq_cst 模式下三次运行恒为 0 ⇒ fence 与 seq_cst 原子操作确实禁止了这个结果，与第 7 节 Q1 的 happens-before 环论证一致。这就是”内存模型是契约，不是概率”的含义。
  3. (1,1) 的比例是一个”时序指纹”：relaxed 下几乎为 0（写缓冲让读抢在对方写提交之前），fenced 下升到 16.8%（两边的读都被推到自己的写提交之后），seq_cst 下只有 7.2%（xchg 带来的全局序约束使两侧更难”同时”看到对方）。同一个 SB 程序在三种顺序强度下，结果分布形态明显不同——这正是”顺序强度”的可测量后果。
  4. fence 的边际成本：relaxed 474 ns/轮 → fenced 517 ns/轮，约 +43 ns/轮（≈133 周期 @3.1 GHz）。这 43 ns 包含两部分：排空写缓冲，以及读不再能与写重叠——后者才是大头，因为 relaxed 模式的性能恰恰来自”读绕过写”这个优化。第 4.6 节估计的”一次 mfence 排空约 20–40 周期”只覆盖了前者，端到端代价要高得多。（同一模式在不同运行之间的耗时可有几十个百分点的波动——每轮都要在两道人造栅栏上同步，测量装置本身对线程相位极其敏感，因此只有”是否为 0”这类结构性结论可以直接采信，具体比例只能当量级参考。）
  5. 绝对量级同样值得注意：每轮耗时接近 500 ns，而两次访存本身只需几十纳秒——时间几乎全花在两道人造栅栏上。做内存模型实验时，”测量装置”的开销往往比被测现象大一个量级，这也是必须用 Work/Span 而不是只报总时间来解读它的原因（见下）。
• 两个实测踩过的坑（本笔记的调试记录，本身就有教学价值）：
  1. 编译器会把”宽松”悄悄变成”严格”：当 mode 作为运行时变量时，gcc -O2 把 relaxed 与 seq_cst 两条分支合并，统一生成 xchg（objdump 可见），于是两个模式的计数几乎完全一致（(0,0) 都是 0、(1,1) 分别是 29289 与 29276）——“我的 relaxed 实验显示没有重排”其实是编译器替你把重排禁掉了。改用模板让 mode 成为编译期常量后，relaxed 立刻跑出 45 万次 (0,0)。教训：内存模型实验必须核对生成的汇编，-O2 不是旁观者，它是参与者。
  2. fence 放错位置等于没放：把 fence 写成 fence; store; load（在 store 之前）时，(0,0) 依然以 70% 的比例大量出现——因为那条 fence 只排空了上一轮遗留的写缓冲，对本轮 store→load 的顺序毫无约束。fence 的语义是”我之前的访存都必须完成“，所以它必须出现在需要被它保护的 store 之后、需要被它约束的 load 之前。
  3. 栅栏本身会”掩盖”被测现象：本实验每轮都同步，两个线程之间存在约半个一致性往返的固有相位差；这个差值可与”写提交延迟”相比，因而任何一种每轮强制同步的石蕊测试都无法干净地测量重排窗口的真实概率。所以上表的 (0,0) 比例的绝对值不应当被当作”硬件重排概率”，只有”是否为 0“这一条是模型层面的确定结论。工业级做法是用专门的模型检查/枚举工具（如 herd7/litmus7 这类工具链）或动态检测器（ThreadSanitizer）来验证，而不是靠”跑一遍看结果”。
• Work（总工作量）：每轮固定 2 次访存 + 2 次栅栏 + 1 次记录与归零。$W(n) = n \cdot \Theta(1)$，其中 $n$ 是轮数（$10^6$）；Work 与线程数、并行度无关，它就是被观察的事件总数。
• Span（关键路径）：每轮的跨度 = 栅栏 A 的最慢到达者 + 一次写（+ 可能的 fence）+ 一次读 + 栅栏 B 的最慢到达者。若栅栏的一次跨核往返记为 $T_b$、读的行转移记为 $L$、fence 的排空与去重叠代价记为 $T_f$，则单轮跨度 $\approx 2T_b + L + T_f$，总跨度 $S(n) = \Theta(n(2T_b + L + T_f))$。
• 并行度 = Work / Span：$W/S \approx \Theta(1)/\Theta(2T_b+L+T_f)$ —— 只由常数项决定，与 $n$ 无关，实际就是 2（两个线程）。实测 $474\text{–}517$ ns/轮与 $2T_b + L$ 的量级吻合（本机跨核一致性地往返在百纳秒量级）。这说明石蕊测试是一个延迟测量装置，不是可并行计算：Work/Span 读法在这里的正确用法是”并行度 = 2 是结构上界，加线程只会增加栅栏排队”。
• 瓶颈：延迟，而非带宽。全程序只碰两条 cache line，带宽消耗可忽略；时间全部花在”跨核一次往返”与 fence 上。因此它的可扩展性上限是 2（两个线程）。
• 与讲义结论的对应：这个程序把 slide 9（”从其他线程的视角，一切皆有可能”）、slide 27–29（TSO 可以用写缓冲，写延迟被有效隐藏）、slide 33（MFENCE 的语义与”扭结”）、slide 39（”不要只用普通访存做同步”）四条结论，变成了一张可复现、可解释、且带踩坑记录的计数表。

3.2 示例二：用 release/acquire 写一个无锁 SPSC 队列（正确同步的典范）

// spsc_ring.cpp —— 单生产者单消费者（SPSC）环形队列，只用 acquire/release
// 编译: g++ -O3 -std=c++17 -pthread spsc_ring.cpp -o spsc_ring
// 运行: taskset -c 0,1 ./spsc_ring 50000000
//
// 设计要点（每一条都对应讲义里的一个概念）：
//   * head_ / tail_ 各自 alignas(64)：避免两个索引落在同一 cache line 上
//     -> 这是"伪共享（false sharing）"的标准防御手段
//   * 生产者只写 tail_，消费者只写 head_：索引变量的写者唯一
//     -> 满足 SWMR（单写者多读者）不变量，把写争用降到最低
//   * 数据写入缓冲区后，用 release store 发布 tail_
//   * 读数据之前，用 acquire load 观察 tail_
//     -> 构成 "synchronizes-with"，让"数据已写好"先于"索引已推进"对其他线程可见
//   * 空闲时才用 relaxed load 看对方索引（它已经是本线程缓存的副本）

#include <atomic>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <thread>

template <typename T, size_t N>            // N 必须是 2 的幂
class SpscRing {
    static_assert((N & (N - 1)) == 0, "N must be a power of two");
    static constexpr size_t MASK = N - 1;

    alignas(64) std::atomic<uint64_t> head_{0};   // 消费者写，生产者读
    alignas(64) std::atomic<uint64_t> tail_{0};   // 生产者写，消费者读
    alignas(64) T buf_[N];                        // 数据区（双方都会碰）

public:
    bool push(const T& v) {
        const uint64_t t = tail_.load(std::memory_order_relaxed);       // 只有我在写 tail_
        if (t - head_.load(std::memory_order_acquire) == N) return false;  // 满
        buf_[t & MASK] = v;                                          // (1) 写数据（普通访存）
        tail_.store(t + 1, std::memory_order_release);               // (2) 发布
        return true;
    }
    bool pop(T& out) {
        const uint64_t h = head_.load(std::memory_order_relaxed);       // 只有我在写 head_
        if (h == tail_.load(std::memory_order_acquire)) return false;   // (3) 空 -> acquire
        out = buf_[h & MASK];                                        // (4) 读数据
        head_.store(h + 1, std::memory_order_release);               // (5) 回收槽位
        return true;
    }
};

int main(int argc, char** argv) {
    const long NMSG = (argc > 1) ? std::atol(argv[1]) : 50000000L;
    SpscRing<uint64_t, 1024> q;
    std::atomic<uint64_t> checksum{0};

    auto t0 = std::chrono::steady_clock::now();

    std::thread producer([&] {
        for (long i = 0; i < NMSG; ++i)
            while (!q.push(static_cast<uint64_t>(i))) { }   // 满则自旋
    });
    std::thread consumer([&] {
        uint64_t sum = 0, v;
        for (long i = 0; i < NMSG; ++i)
            while (!q.pop(v)) { }                            // 空则自旋
        checksum.store(sum, std::memory_order_relaxed);
    });
    producer.join(); consumer.join();

    auto t1 = std::chrono::steady_clock::now();
    double s = std::chrono::duration<double>(t1 - t0).count();
    std::printf("%ld 条消息, %.3f s, %.1f M msg/s, 有效载荷 %.2f GB/s\n",
                NMSG, s, NMSG / s / 1e6, NMSG * 8.0 / s / 1e9);
    return 0;
}

【代码做什么？】

1. push（生产者）：先用 relaxed 读自己的 tail_（只有这个线程写它，所以 relaxed 完全安全，也不会产生额外顺序代价）；再用 acquire 读 head_ 判断是否满——这一步的 acquire 保证”消费者已经完成对槽位的读取、并把 head_ 推进”这件事对我可见。然后把数据写进 buf_（(1) 普通访存），最后用 release store 推进 tail_（(2)）——release 的含义正是：在 (2) 之前的写（包括 (1)）必须先于 (2) 对其他线程可见。
2. pop（消费者）：对称地，先 relaxed 读自己的 head_，再用 acquire 读 tail_（(3)）判断是否为空——这个 acquire 与生产者的 release synchronizes-with，从而保证 (1) 写在 (4) 读之前可见。读完数据（(4)）后 release 地推进 head_（(5)），告知生产者槽位已回收。
3. 对齐与写者唯一：head_ 与 tail_ 各自 alignas(64)，保证它们不共享 cache line；buf_ 也按 64 对齐以避免与索引变量凑到一行。加上”每个索引只有一个写者”的设计，这个队列在没有任何锁、没有任何 fence 指令的前提下就是数据竞争自由的：所有共享访问要么是同线程私有（relaxed 索引），要么被 release/acquire 排序。
4. 测量：跑 $N$ 条消息、统计 msg/s 与有效载荷带宽（8 B/消息）。注意这里刻意使用 while(!push(...)) 的空转形式，让生产者/消费者在队列满/空时自旋，从而测的是队列本身的吞吐极限。

【并行机制与性能解说】

• 硬件上发生了什么：生产者与消费者跑在两个不同核上，tail_ 这一行在生产者核上处于 M 态，消费者读它时会触发一致性事务（行被共享/转移）；head_ 同理反向流动。buf_ 里的同一行会用生产者写、消费者读（true sharing，真共享，是必要的通信，不是伪共享），一个 64 B 行能装下 8 个 uint64_t，所以数据行的转移成本被 8 条消息摊薄，而索引行的转移成本是每条消息一次——这正是下一条要批处理优化的原因。
• Work（总工作量）：$W(N) = N$ 次 push + $N$ 次 pop = $2N$ 次常数代价操作，即 $W(N) = \Theta(N)$。其中每次操作包含：2 次原子索引访问 + 1 次缓冲区访存。
• Span（关键路径）：队列的数据流依赖是元素级的（第 $i$ 个元素必须先被 push 才能被 pop），但这条链是跨线程流水：生产者的 $N$ 次 push 之间没有数据依赖（各自的 tail_ 值由本线程顺序推进，store 走写缓冲即可），消费者的 $N$ 次 pop 之间也没有。真正的跨线程腿只有一条：“第 $i$ 个元素的 (2) release store 必须被 (3) acquire load 观察到，第 $i$ 个槽位才能被安全复用”。在稳定的流水状态里（消费者落后生产者若干个槽位），这条腿被流水线重叠掉，单元素的跨度退化到”一次本地索引更新 + 一次写缓冲入队”的几拍量级，即 $S(N) = \Theta(N)$（常数很小）。
• 并行度 = Work / Span：$W/S = 2N / \Theta(N) = \Theta(1)$，具体约为 2（生产与消费两条流水线），上界永远是 2——环形队列的结构决定了它不可能用 8 个线程加速，它是通信结构而不是可并行计算。所以 Work/Span 在这里的正确读法是：并行度 = 2 意味着”任意多核下最多 2× 吞吐”，衡量它的指标必须是”每秒消息数 / 有效载荷带宽”，不是”加速比”。
• 瓶颈与量化（按本笔记假设计算，标注为推导值）：
  • 设需要 $10^8$ msg/s、每消息 8 B：有效载荷 = 0.8 GB/s，但一致性以 64 B 行为单位搬运，索引行的流量被放大 8 倍左右，实际一致性流量 ≈ 6.4 GB/s。在 20 GB/s 的互连上这已占 32% 的带宽——纯通信结构的算术强度（arithmetic intensity）为 0 FLOP/Byte，它在 Roofline 图上永远贴着最左边（见第 4.5 节）。
  • 若每条消息都要求一次索引行转移、每次转移按 ~30 ns 计，则 $10^8$ 条消息需要 $10^8 \times 30\ \text{ns} = 3\ \text{s}$ 的串行化点时间——这才是真正的天花板。
  • 优化方向：批处理（batching）。让 pop 一次 acquire 后连续消费多个元素（例如把 tail_ 读一次、循环取 8 个），或让 push 一次写 8 个再发布一次 tail_：索引行转移次数下降 8 倍，fence/原子操作次数下降 8 倍，吞吐提升接近 8 倍，代价是平均延迟上升（消息在队列里多等一会儿）——这是吞吐 vs 延迟的经典取舍，也是后面第 4.6 节”fence 吞吐上限”的直接推论。

3.3 示例三：伪共享实测——把并行度从 8 压回 1

// false_sharing.cpp —— 复刻 CS149 讲义 slide 17 的伪共享实验
//   两种布局：8 个计数器挤在同一行 vs 每个计数器独占一行（alignas(64)）
//
// 编译: g++ -O3 -std=c++17 -pthread false_sharing.cpp -o false_sharing
// 运行: taskset -c 0-3 ./false_sharing 8 25000000
//       （8 线程，每线程 2500 万次自增 = 总计 2 亿次自增）
//
// 讲义（CS149 slide 17）在 4 核系统上用 8 线程测得：
//      未 padding: 14.2 s      已 padding: 4.7 s      （约 3.0 倍差距）
// 差异**完全来自一致性流量**（artifactual communication），与算法无关。

#include <atomic>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <thread>
#include <vector>

static constexpr int CACHE_LINE = 64;

// 布局 A：8 个 atomic<long> 连续放置 -> 8 * 8 B = 64 B，正好压在一条 cache line 上
// 布局 B：每个计数器独占一条 cache line（C++11 的 alignas 等价于讲义里的
//         struct { int counter; char padding[CACHE_LINE_SIZE - sizeof(int)]; }）
struct alignas(CACHE_LINE) PaddedCounter {
    std::atomic<long> v{0};
};

static inline std::atomic<long>& slot_of(std::atomic<long>& a) { return a; }
static inline std::atomic<long>& slot_of(PaddedCounter& p)     { return p.v; }

template <typename Counter>
static double run(const char* tag, int nthreads, long iters) {
    std::vector<Counter> c(nthreads);
    std::vector<std::thread> th;
    th.reserve(nthreads);

    auto t0 = std::chrono::steady_clock::now();
    for (int i = 0; i < nthreads; ++i)
        th.emplace_back([&c, i, iters] {
            std::atomic<long>& slot = slot_of(c[i]);          // 每个线程只碰自己那一格
            for (long k = 0; k < iters; ++k)
                slot.fetch_add(1, std::memory_order_relaxed);  // 原子读-改-写
        });
    for (auto& t : th) t.join();
    auto t1 = std::chrono::steady_clock::now();

    double s = std::chrono::duration<double>(t1 - t0).count();
    double per_op_ns = s / (double(nthreads) * double(iters)) * 1e9;
    std::printf("%-28s %8.3f s   %7.1f ns/自增\n", tag, s, per_op_ns);
    return s;
}

int main(int argc, char** argv) {
    int  nt    = (argc > 1) ? std::atoi(argv[1]) : 8;
    long iters = (argc > 2) ? std::atol(argv[2]) : 25000000L;

    double a = run<std::atomic<long>>("未 padding（同行，伪共享）", nt, iters);
    double b = run<PaddedCounter>   ("已 padding（独占一行）    ", nt, iters);
    std::printf("speedup(padded / unpadded) = %.2fx\n", a / b);
    return 0;
}

【代码做什么？】

1. 两种内存布局：std::atomic<long> 数组里 8 个元素恰好占 64 B = 一条 cache line；PaddedCounter 用 alignas(64) 强制每个计数器独占一行（64 B 里只有 8 B 有效，48 B 是”浪费”，但换来零一致性争用）。
2. 每个线程只访问自己的那一格：slot = slot_of(c[i])。在语言层面这是完全数据竞争自由的（不同对象、不同线程），在硬件层面却不是：布局 A 里 8 个线程写的是同一条 cache line 的不同字节，MSI 协议只认 cache line——谁要写，就必须先把整行”抢”过来（独占），别人的副本失效。这就是 false sharing（伪共享）。
3. fetch_add(relaxed)：relaxed 只说明顺序无关紧要，不说明原子性可以省——读-改-写仍然是原子的，仍然要求独占所有权。因此它必然触发一致性事务，正好用来把伪共享的代价隔离出来。
4. 测量：分别报告总时间与每次自增的平均纳秒数；后者比总时间更能揭示”每次操作到底付了多少一致性代价”。

【并行机制与性能解说】

• 硬件上发生了什么：布局 A 中，8 个线程轮流向同一条行做原子自增，每次自增都要把该行从”别人手里”抢回来（BusRdX / 目录失效），行在 8 个核之间持续 ping-pong。行本身始终是热的（从不下沉到 DRAM），但这些行转移事务全部要经过互连这个串行化点——于是”8 个逻辑上完全独立的操作”被硬件变成了一条串行链。布局 B 中每个线程的行长期停留在自己核的 M 态，事务数从 $\Theta(W)$ 掉到 $O(1)$（每个线程一次初始获取），自增退化成本地 L1 的原子操作。
• Work（总工作量）：$W = P \times I$ 次原子自增（$P = 8$ 线程、$I = 2.5\times10^7$）$= 2\times10^8$ 次。Work 在两种布局下完全相同——这正是伪共享”完全是人为（artifactual）通信”的含义。
• Span（关键路径）：
  • 布局 A（同行）：因为每一次自增都必须垄断整条 cache line，所有 $W$ 次自增在物理上被串成一条链：$S_A = W \cdot T_{\text{coh}}$，其中 $T_{\text{coh}}$ 是”一次行转移 + 串行化点排队”的等效时间。
  • 布局 B（独占行）：每个线程的 $I$ 次自增在自己的行上串行，线程之间互不相干：$S_B = I \cdot T_{\text{local}}$，$T_{\text{local}}$ 是本地原子操作的等效时间。
• 并行度 = Work / Span：
  • 布局 A：$W/S_A = W/(W \cdot T_{\text{coh}}) = 1/T_{\text{coh}}$ ——与线程数无关，等价于”并行度 1”。伪共享把 $P = 8$ 的并行度压回了 1，这是本讲最锋利的一句结论。
  • 布局 B：$W/S_B = (P \cdot I)/(I \cdot T_{\text{local}}) = P / T_{\text{local}}$，即并行度退化为 $P$（受物理核数 4 限制）。
• 与实测对账（本笔记推导，讲义只给了两个时间）：讲义数据是 8 线程/4 核下 14.2 s vs 4.7 s（3.0×）。把”总计 $2\times10^8$ 次自增”作为假设（讲义未给出 MANY_ITERATIONS），则布局 A 的每次自增成本 ≈ $14.2\ \text{s} / 2\times10^8 \approx 71$ ns（3 GHz 下约 213 周期），远高于单次 L3 命中的 ~40 周期（CS149 slide 14）或”行在别的核且已修改”的 ~75 周期——差额就是互连串行化点上的排队与失效风暴；布局 B 的每次成本 ≈ 23.5 ns（约 70 周期），这是 8 线程挤在 4 个核上做本地原子操作的合理水平。两者比值 3.0×，与讲义实测一致。
• 本笔记在本机的复现：AMD EPYC 7V13（Zen 2，taskset -c 0-3，每线程 $2.5\times10^7$ 次自增、共 $2\times10^8$ 次）。8 线程（4 核）：未 padding 2.388 s（11.9 ns/次），已 padding 0.133 s（0.7 ns/次），speedup = 17.9×；4 线程（4 核）：未 padding 0.138 s，已 padding 0.016 s，8.5×。绝对时间比讲义数据（14.2 s / 4.7 s）小一个量级——那是历史机器与不同的迭代次数，但”并行度从 8 掉回 1”的机制与方向完全一致，且效应在现代多核上更强（17.9× ≫ 3.0×）。这再次说明：该现象的可比量是比值与机制，不是绝对秒数。
• 一致性流量账（把 256 MB / 20 GB/s 当作单位换尺）：布局 A 中约 $2\times10^8$ 次行转移 × 64 B = 12.8 GB 的一致性流量。参考量纲：一个 256 MB 的数组在 20 GB/s 带宽下遍历一次至少 256 MB / 20 GB/s = 12.8 ms；12.8 GB 是它的 50 倍，即仅”搬运”就要 640 ms，再加上串行化点每事务数十纳秒的排队，总时间进入秒级——与 14.2 s 同量级。这个 3.0× 的差距没有一行代码是”算”出来的，全部是通信。
• 瓶颈：一致性事务的串行化吞吐（不是 DRAM 带宽，也不是算力）。同一现象的”单次操作”读数：本机实测未 padding 时每次自增 11.9 ns（≈37 周期 @3.1 GHz），它把一次完整的行转移与串行化排队都摊在了单次自增上。修复手段：alignas(64) / 手动 padding（讲义 slide 16 的 char padding[CACHE_LINE_SIZE - sizeof(int)]）、每线程私有累加 + 末尾归约（把 $W$ 次远程原子操作变成 $P$ 次）。

3.4 示例四：Peterson 锁与 fence 的位置（讲义 slide 39 的练习题）

// peterson_fence.cpp —— Peterson 互斥算法在宽松内存模型上的正确 fence 放置
// 编译: g++ -O2 -std=c++17 -pthread peterson_fence.cpp -o peterson_fence
// 运行: taskset -c 0,1 ./peterson_fence 2000000
//
// 程序：两个线程各自进入临界区 iters 次，每次对**非原子**的 shared 计数器加一。
//       若互斥正确，最终 shared == 2*iters；否则出现"丢失更新"（lost update）。
// 两种实现：BROKEN（只用 relaxed，无 fence） 与 FIXED（fence 放在正确位置）。
//
// 讲义 slide 39 的练习题：
//     boolean want[2] = {false,false};  int turn = 0;
//     want[i] = true;  turn = j;
//     while (want[j] && turn == j) continue;
//     ... critical section ...
//     want[i] = false;
//   问：应该在哪里加 fence、加哪一种？
// 本文件的 FIXED 版本给出答案，并在第 7 节 Q1 详细论证。

#include <atomic>
#include <cstdio>
#include <cstdlib>
#include <thread>

static std::atomic<int> want[2];
static std::atomic<int> turn{0};
static long shared = 0;          // 故意用普通 long：由锁保护，靠 happens-before 保证安全
static bool use_fence = true;

// ---------- 正确版本：fence 恰好放在需要的地方 ----------
static void lock_fixed(int i) {
    const int j = 1 - i;
    want[i].store(1, std::memory_order_relaxed);                    // (a) 声明意图
    std::atomic_thread_fence(std::memory_order_seq_cst);            // F1: (a) 必须先于 (b) 提交
    turn.store(j, std::memory_order_relaxed);                       // (b) 让出优先权
    std::atomic_thread_fence(std::memory_order_seq_cst);            // F2: 上面的写提交后才允许下面的读
    while (want[j].load(std::memory_order_relaxed) &&
           turn.load(std::memory_order_relaxed) == j) { }           // (c) 等待
}
static void unlock_fixed(int i) {
    std::atomic_thread_fence(std::memory_order_seq_cst);            // F3: 临界区内所有写先提交
    want[i].store(0, std::memory_order_relaxed);                    // (d) 释放
}

// ---------- 错误版本：完全没有 fence（在 x86 上"多数时候也能跑"）----------
static void lock_broken(int i) {
    const int j = 1 - i;
    want[i].store(1, std::memory_order_relaxed);
    turn.store(j, std::memory_order_relaxed);                       // 可能被重排到 (a) 前面
    while (want[j].load(std::memory_order_relaxed) &&
           turn.load(std::memory_order_relaxed) == j) { }
}
static void unlock_broken(int i) {
    want[i].store(0, std::memory_order_relaxed);
}

static void worker(int id, long iters, long* local_errors) {
    long prev = 0;
    for (long k = 0; k < iters; ++k) {
        if (use_fence) lock_fixed(id); else lock_broken(id);
        long now = shared + 1;          // 读-改-写：必须有互斥保护，否则丢失更新
        shared = now;
        if (use_fence) unlock_fixed(id); else unlock_broken(id);
        prev = now;
    }
    *local_errors = prev;               // 仅用于阻止编译器把循环优化掉
}

int main(int argc, char** argv) {
    long iters = (argc > 1) ? std::atol(argv[1]) : 1000000L;
    for (int fixed = 1; fixed >= 0; --fixed) {
        use_fence = (fixed == 1);
        want[0] = want[1] = 0; turn = 0; shared = 0;
        long e0 = 0, e1 = 0;
        std::thread t0(worker, 0, iters, &e0), t1(worker, 1, iters, &e1);
        t0.join(); t1.join();
        std::printf("%-10s shared = %ld (期望 %ld)  %s\n",
                    fixed ? "FIXED" : "BROKEN", shared, 2 * iters,
                    shared == 2 * iters ? "OK" : "!! 丢失更新 !!");
    }
    return 0;
}

【代码做什么？】

1. Peterson 算法的三段式：want[i]=1（声明意图）→ turn=j（把优先权让给对方）→ 自旋等待 want[j] && turn==j 不成立。这是讲义 slide 39 给出的骨架（”stripped-down version of a 2-process mutex”）。
2. FIXED 版本的三个 fence：
   • F1 位于 want[i]=1 与 turn=j 之间——保证”我声明了意图”先于“我让出优先权”对其他线程提交。否则两个线程可能都看到对方还没声明意图，同时进入临界区。
   • F2 位于 turn=j 之后、自旋读之前——保证上面对 want/turn 的写提交之后才开始读。这正是 acquire 语义。
   • F3 位于退出临界区、清 want[i] 之前——保证临界区内的数据写先提交，再宣告”我走了”（release 语义）。没有它，下一个进入者可能看到 want[i]==0 但看不到临界区里的修改。
3. BROKEN 版本：全部使用 relaxed（x86 上就是普通 MOV，编译器/硬件都可自由重排两条写与两次读），于是 F1/F2/F3 的保证全部丢失。
4. 正确性判据：shared 是非原子变量，递增是”读-改-写”三步。互斥被破坏时，两次递增会丢一次，最终 shared < 2*iters。这个判据无需读内存模型就能理解，但只在统计意义下有效：互斥被破坏时未必每轮都丢更新。本机实测（taskset -c 0,1，op 固定在两个物理核上）在 50 万次迭代时 BROKEN 版本丢了 4 次更新、20 万次时丢了 2 次、而 10 万次时一次都没丢——“跑一次没错”完全不能说明程序是对的。注意 BROKEN 版本在 x86 上经常”看起来正常”（因为 x86 只放松 WX→RY，而这里的危险重排主要是 WX→WY 与 RX→RY），这正说明”在我的机器上能跑“不是正确性——真正的探测器是 3.1 节的石蕊测试。
5. 可移植性说明：want/turn 用 std::atomic + relaxed 配合 atomic_thread_fence(seq_cst)，属于 C++11 允许的 fence-fence 同步写法；等价的更”现代”写法是把它们换成 acquire/release 语义的原子操作。在 x86 上，F1、F2 的最小硬件实现是”在 (a) 与 (b) 之间一条 mfence“（x86 本身就禁止 load→load 重排，所以 (c) 里的两次读不需要额外硬件屏障，但编译器仍需被约束——这就是为什么用 std::atomic 而不是 volatile）。

【并行机制与性能解说】

• 硬件上发生了什么：两个线程在不同核上反复争抢 want/turn 所在的行，与锁本身的存储布局强相关——讲义 slide 31 提醒”shared data 事实上对其他线程始终可见”，因此 want[0] 与 want[1] 若落在同一行，会产生伪共享式的额外流量（把 want[2] 各自 padding 到独立行是常见优化）。临界区本身把两个线程串行化：这是设计意图（互斥），不是缺陷。
• Work（总工作量）：$W = 2 \cdot I$ 次”进临界区 + 一次读-改-写 + 出临界区”，每次是常数代价操作（含 1 次 acquire 序列与 1 次 release 序列），故 $W = \Theta(I)$。
• Span（关键路径）：临界区是硬串行的——所有 $2I$ 个临界区段必须一个接一个执行。每个临界区段之间还夹着一对”释放 → 获取”的通信（至少要等 want[i]=0 的写在对方核上可见，或等一次自旋迭代），耗时约一次跨核往返 $L \approx 30\text{–}100$ ns。所以 $S = 2I \cdot (T_{\text{cs}} + L)$。
• 并行度 = Work / Span：$W/S = (2I)/(2I(T_{\text{cs}}+L)) \approx 1/(T_{\text{cs}}+L)$——互斥本身的并行度恒为 1。这是 Amdahl 定律最直接的实例：设临界区占单线程总工作量的比例 $f$（考虑自旋等待则更高），则加速比上界 $\le 1/f$（讲义视角下，”不考虑计算的锁，永远是串行瓶颈“）。把 $f = 5\%$ 代进去：$1/0.05 = 20\times$，再多的核也到不了 20 倍以上。
• fence 的成本：这里每个临界区进出各一次 fence 序列。按一次 mfence 的排空代价 ≈ 20–40 周期 ≈ 7–13 ns（3 GHz）保守估算（示例一实测的端到端边际成本约 43 ns/轮，量级更大），$2\times10^6$ 次进出（$I = 10^6$）至少要 28–52 ms 的纯 fence 开销；若临界区本身只有几十纳秒，则同步开销与临界区工作量同量级——这就是为什么 slide 40 的结论是”把复杂度封装进库“：库作者才需要在这里斤斤计较。

• 瓶颈：串行化 + 跨核往返延迟。降低办法只有三类：缩小临界区（减少 $T_{\text{cs}}$）、减少进出次数（批处理 / 合并、把多次更新合成一次）、换用乐观并发（无锁数据结构 / CAS 重试），后者正是下一讲的主题。

• 表 2：四个示例的 Work / Span / 并行度 / 瓶颈汇总

4. 性能模型与复杂度分析

4.1 SC 的代价：从”一访问一停顿”推出 17%–42% 的利用率

模型假设（本笔记的推导参数，用于解释讲义 slide 26 引用的 Gupta et al. 数据量级）：

• 处理器理想发射宽度 = 2 条指令/周期（即理想 $CPI_{\text{ideal}} = 0.5$ 周期/指令）；
• 访存指令占全部指令的比例 $f_m = 20\%$（每 5 条指令一次访存）；
• 每次访存的完整延迟为 $L$ 周期（SC 要求访存串行完成）。

SC 下每条指令的平均周期数：

处理器利用率（相对理想发射）：

结论：当实际访存延迟落在 4–10 周期（L1/L2 命中为主、缓存有效的理想情况）时，模型给出 20%–38.5% 的利用率，与讲义引用的 17%–42% 落在同一区间。这就是”严格的顺序一致性即使有缓存也不够快”的定量表述：$L$ 每增加 1 个周期，利用率就掉 $0.2/(0.5+0.2L)^2 \times 0.5$ 那么多——延迟越大的机器，SC 越不可接受。

4.2 TSO 的收益：把写延迟从关键路径上摘掉

改动一处假设：写缓冲生效，因此只有 load 会造成停顿。设访存指令中 40% 是写（即写指令占全部指令 $f_w = 8\%$、读指令占 $f_r = 12\%$）：

再算一笔”写缓冲必须能排空”的账：写指令率 $= \text{IPC} \times f_w = 2 \times 8\% = 0.16$ 写/周期；每次写 8 B ⇒ 需要的持续写带宽 $= 0.16 \times 8\ \text{B} \times 3.0\ \text{GHz} = \mathbf{3.84\ GB/s}$。如果写缓冲的冲刷速率低于这个值，缓冲会填满，处理器又被逼回到”等写完成”——TSO 的收益是有条件的。CS149 slide 42 的”W-R”曲线给出的正是这个结论：放松 WX→RY 后写延迟几乎被完全隐藏，这是全部现代处理器都使用写缓冲（Intel x86 / ARM / RISC-V）的根本原因。

4.3 AMAT 与”多核比单核慢在哪”

AMAT（Average Memory Access Time） $= \sum_{i} (\text{第 } i \text{ 级的访问频率} \times \text{该级延迟})$（CS149 slide 14 的公式）。

CS149 给出的 Core i7 Xeon 5500 近似延迟：L1 命中 ~4 周期；L2 命中 ~10 周期；L3 命中（行未被共享）~40 周期；L3 命中（行在另一个核、共享态）~65 周期；L3 命中（行在另一个核、已修改）~75 周期；本地 DRAM ~30 ns（~120 周期）；远端 DRAM ~100 ns（~400 周期）。

算例（访问频率分布两种情形）：

结论（CS149 slide 14 的原话精神：”只有不到百分之几的访存变成这样，影响就已经很显著”）：AMAT 从 6.3 → 9.8 周期，恶化 55.6%，而变化的只是2% + 1% = 3% 的访问。$AMAT_{\text{multiprocessor}} > AMAT_{\text{uniprocessor}}$，差值全部来自共享与远端性。这也解释了为什么”某条数据行此刻在谁手里”（M 态在别的核 ⇒ 75 周期）会直接决定本讲的性能故事：一致性模型的强弱，决定了行必须多频繁地回到一致性序，从而决定了这些昂贵命中出现的频率。

4.4 伪共享的通信量算例（含强制的量纲换算）

• 基准量纲：一个 256 MB 的数组，在 20 GB/s 的带宽下遍历一次至少需要 $256\ \text{MB} / 20\ \text{GB/s} = 0.256/20\ \text{s} = \mathbf{12.8\ ms}$。这是”内存/互连带宽能做什么”的尺子。
• 伪共享场景：$P = 8$ 个计数器挤在一行，总自增 $W = 2\times10^8$ 次。
  • 每次自增要求独占该行 ⇒ 每次一次行转移（64 B）⇒ 一致性流量 $= 2\times10^8 \times 64\ \text{B} = \mathbf{12.8\ GB}$。
  • 12.8 GB 是 256 MB 的 50 倍 ⇒ 纯搬运时间 $= 50 \times 12.8\ \text{ms} = \mathbf{640\ ms}$。
  • 还要叠加串行化点的代价：互连一次只能处理一个一致性事务，若等效每事务 30 ns，则 $2\times10^8 \times 30\ \text{ns} = \mathbf{6\ s}$。两者叠加与讲义实测的 14.2 s 同量级（讲义未给出迭代次数，此处的 $2\times10^8$ 是量级假设）。
  • 加 padding 后：每个线程的行长期处于自己核的 M 态，一致性流量从 $\Theta(W)$ 降到 $O(P)$，实测降到 4.7 s（3.0× 提升）。
• 对本讲的寓意：伪共享是”一致性协议制造的、与算法无关的通信“。内存一致性模型讨论的是”顺序”，而伪共享讨论的是”顺序被强制的频率”——两者是同一枚硬币的两面：越弱的模型允许越多的本地缓冲与乱序，就越少把行拉回一致性序；但只要有写共享（真共享或伪共享），行就必须回来。

4.5 Roofline 与算术强度：一致性相关的代码为什么永远贴着图的最左边

机器参数：$16$ 核 $\times\ 3.0\ \text{GHz} \times 8$ 宽 SIMD $\times\ 2$（FMA）= 768 GFLOPS 峰值；内存/互连带宽 20 GB/s。

机器平衡点（machine balance）：

本讲各类代码的算术强度：

定量结论：

• 队列在 $10^8$ msg/s 时有效载荷 = $10^8 \times 8\ \text{B} = 0.8\ \text{GB/s}$，但一致性以 64 B 行为单位，线路流量约 $6.4\ \text{GB/s}$（放大 8 倍），占 20 GB/s 的 32%；要把它降到 5% 以下，必须让每条消息的分摊行流量 ≤ 3.2 B，即每行至少服务 20 条消息（批处理）。
• 因为 $AI \ll AI^{*}$，本讲所有优化都不能靠增加算力：唯一的杠杆是减少被搬运的字节数（padding、批处理、私有累加 + 末尾归约）和减少被拉回一致性序的次数（更弱的顺序约束、更长的批）。

4.6 fence / 原子的吞吐上限，与 Amdahl 的汇合

fence 吞吐：一次 mfence 需要排空写缓冲，估 20–40 周期（3 GHz 下 6.7–13.3 ns）；示例一在真实 x86 上实测的端到端边际成本为 +43 ns/轮（≈133 周期 @3.1 GHz）——比纯排空估计大 3 倍以上，因为 fence 同时取消了“读绕过写”的重叠。下面用保守的 20–40 周期做上限估计，实际只会更紧。若程序中”每个元素一次 fence”，则单核上限

也就是说：在 3 GHz 的核上，同步事件的”指令级”上限大约是每秒一亿次量级。若算法天然需要 $10^9$ 次同步事件/秒，唯一的出路是批处理（把 $k$ 次更新合并到一次 fence 之后，上限提高 $k$ 倍）——这与 4.5 节”队列需要每行服务 20 条消息”的结论从两个不同方向指向同一个设计。

Amdahl 与锁：设程序中必须互斥执行（或必须经过一次 fence 的顺序）的部分占单线程总时间的比例 $f$，其余完全可并行，则

• $f = 5\%$ ⇒ 上限 20×；$f = 10\%$ ⇒ 上限 10×。
• 在 16 核机器上，$f = 5\%$ 时实际加速比 $= 1/(0.05 + 0.95/16) = 1/0.1094 = \mathbf{9.1\times}$（而非 16×）——同步事件把”16 核”打折成”9 核等效”。
• 反过来看乐观的一面：把”每次操作一次 fence”改成”每 20 次操作一次 fence”，$f$ 从（例如）10% 降到 0.5%，上限从 10× 抬到 200×。这正是 “为常见情况优化“（CS149 slide 55：”most memory accesses are not conflicting, so don’t design a system that pays the cost as if they are”）的定量含义。

5. 关键要点

1. 不要用普通访存做同步。 讲义 slide 39 的第一条 take-away 原话就是：”DON’T use only normal memory operations for synchronization；DO use either explicit synchronization operations (e.g., xchg) or fences“。石蕊测试（示例一）与 Peterson 锁（示例四）都表明：仅靠”写一个标志、读一个标志”的实现，在宽松模型上会得到正确性完全无法保证的程序——而且它常常”看起来能跑”。
2. Cache coherence 与 memory consistency 是两个正交的问题，别混为一谈。 coherence 只约束同一地址（SWMR + 写串行化 + 读回串行序中的最后一次写），它的存在理由是”多份副本”；consistency 约束的是不同地址之间的可见顺序，与有没有缓存无关。因此 CS149 slide 3 才会追问”这是互斥问题吗？加锁能修好吗？——不能“。加锁修的是竞争，不是副本与重排。
3. 顺序一致性是程序员的心智模型，而硬件为性能必须比它弱。 “所有访存存在一个与各线程 program order 相容的全局串行序”这句话给了我们推理的抓手，但它的直接实现（每个处理器同时只有一个 outstanding 访存）把利用率压到 17%–42%。于是实际机器分成 TSO（x86，只放松 WX→RY）、PSO、WO/RC 等档次，并统一用 fence（MFENCE/LFENCE/SFENCE/xchg）与 acquire/release 把需要的顺序”钉”回来。
4. 宽松模型下”正确”的定义是 DRF：先把程序变成无数据竞争，再谈性能。 同步把程序切成若干段，段内可任意重排（那是”私人活动”），同步点处形成跨线程偏序（”充分顺序”）。C11 / C++11 / Java 5 给出的契约是 SC for DRF：无数据竞争的程序在弱硬件上表现得像 SC；有数据竞争的程序没有任何保证（未定义行为）。因此工程上的正确做法是”用库提供的同步原语“（lock/unlock、barrier、std::atomic），让库作者去处理内存模型细节。
5. fence 不推值，只在跨线程偏序上打”扭结”；它的成本必须被摊薄。 MFENCE 不会让别的线程立刻看到最新值（slide 35 的常见误解），它只是让执行它的那个线程停顿：先前访存必须完成、后续访存不得提前。气球类比里它是”没有任何粒子能穿过的一个结“。一次 fence 的排空代价约 20–40 周期（示例一实测端到端约 43 ns/轮），单核同步事件上限约 $10^8$/s 量级 ⇒ 一切”每元素一次 fence/原子操作”的设计都应改成批处理，把成本摊到多个操作上。

6. 常见陷阱与注意事项

• 把 coherence 与 consistency 混为一谈，并以为加锁能修一致性问题。 缓存一致性问题来自”数据在多个缓存里有多份副本”（硬件实现导致的），锁管的是互斥——即使你的锁完全正确，不同地址之间的可见顺序依然不受它约束。反过来，也不要以为”多核程序错了就是没加锁”：SB 石蕊测试里根本没有共享数据的读写冲突逻辑，它错在顺序。
• 以为 fence 是”让所有核刷新到最新值”的魔法。 MFENCE 不把值推给其他线程，它只让本线程停顿。写一个 mfence 并不会”通知”别人；它改变的是本线程访存之间的相对顺序，以及由此产生的跨线程可观察偏序。把 fence 当成”内存同步按钮”会导致在错误的位置加错误数量的屏障——既慢又不对。
• 用 volatile（或普通变量）当同步原语。 讲义反复强调”processor 与 compiler 都在重排”：volatile 只约束编译器对该变量的访问次数/顺序，既不提供原子性，也不提供内存顺序，更不会生成 mfence。正确的工具是 C++11 的 std::atomic + 合适的 memory_order（acquire/release/seq_cst），或平台提供的原子内建函数 + fence。
• 以为 x86 就是 SC，从而在 x86 上”验证通过”就发布代码。 x86 是 TSO：它允许 WX→RY 重排（写缓冲），所以 Store Buffering 的 (0,0) 在 x86 上是允许的——示例一在本机实测到它以 13%–30% 的比例反复出现（而加上 fence 或改用 seq_cst 后三次运行恒为 0）；x86 也不保证编译器不重排（编译器可以证明两个不同对象的访问不别名而换序），示例一中“运行时 mode 被 -O2 合并成 xchg”就是活生生的例子。同一份代码在 ARM/Power（更宽松）上会以更高的频率失败。判断标准只有一条：程序是否 DRF，以及是否在正确位置使用了正确的原子操作。
• 忽略伪共享（false sharing）——它能把并行度直接压到 1。 两个线程写不同变量、但落在同一条 64 B cache line 上时，MSA/MSI 协议只认行：每次写都要独占整行，行在核之间 ping-pong，产生完全人为的通信。CS149 实测 8 线程 14.2 s（未 padding）vs 4.7 s（padding）；本讲 Work/Span 分析给出的解释是：未 padding 时并行度 $W/S \approx 1$，padding 后恢复为 $\approx P$。防御手段：alignas(64) / 手动 padding、每线程私有累加 + 末尾归约。
• 把同步事件做成”每元素一次”，忽略 fence/原子的吞吐上限与批处理。 一次 mfence 约 20–40 周期、一次跨核原子往返约 30–100 ns，二者都远大于一次普通 ALU 操作。SPSC 队列若不批处理，每条消息就要一次索引行转移（$AI = 0$，线路流量放大 8 倍）；改成”每行服务 20 条消息”后，同样的硬件可以跑出高得多的吞吐——代价是延迟。吞吐 vs 延迟必须显式设计，而不是让默认实现替你决定。
• 只在小规模/单核/同核超线程下测试。 同一物理核上的两个 SMT 线程共享 L1，一致性往返退化为本地命中，重排窗口消失，几乎所有内存序 bug 都测不出来。必须用 taskset（Linux）或 numactl 把线程绑到不同物理核上，并重复多轮（内存序 bug 是统计性的，单次运行成功毫无意义）。

7. 思考题（带答案）

Q1. 讲义 slide 20 的例子：P0 执行 A = 1; Ready = 1;，P1 执行 x = Ready; y = A;（A、Ready 初值均为 0）。(a) 为什么 (x, y) = (1, 0) 在 SC 下不可能？(b) 在 x86（TSO）上它可能吗？(c) 讲义 slide 37 在 P0 和 P1 上各标了 3 个候选位置（[1] A=1 之前、[2] A=1 与 Ready=1 之间、[3] Ready=1 之后；[4] x=Ready 之前、[5] x=Ready 与 y=A 之间、[6] y=A 之后），哪些是必要的？

【答案】

(a) SC 下的矛盾（happens-before 成环）：把 P0 的两条访存记为 $a: A{=}1$、$b: Ready{=}1$，P1 的记为 $c: x{=}Ready$、$d: y{=}A$。SC 保证每个线程的访问按 program order 出现在全局串行序中，即 $a \to b$、$c \to d$。

• 若 $y = 0$（即 $d$ 读到初值），说明在串行序中 $d$ 早于 $a$（因为 $A$ 唯一的写是 $a$）；
• 若 $x = 1$（即 $c$ 读到了 $b$ 写的值），说明在串行序中 $b$ 早于 $c$；
• 合并得：$a \to b \to c \to d \to a$ —— 一个环，意味着某个事件必须发生在它自己之前，矛盾。因此 (x,y) = (1,0) 在 SC 下不可能（可能的结果只有 (0,0)、(0,1)、(1,1)）。讲义提示的正是这套推理：”we know a→b and c→d by program order; b→c implies a→d; y==0 implies d→a which leads to a contradiction”。

(b) x86-TSO 下呢？ 这个结果需要 Ready=1 在 A=1 之前提交（一个 WX→WY 的破坏）或者 y=A 被提到 x=Ready 之前（一个 RX→RY 的破坏）。而 x86-TSO 只放松 WX→RY：同一处理器的两次 store 按程序序提交，两次 load 不互相重排。因此在 x86 硬件上，这个特定例子本身是安全的（这也是它”看起来从来不报错”的原因）。但三点必须注意：① 编译器仍然可能把 A=1; Ready=1; 换序（两者不别名，编译器完全有权重排），也可能把 y = A 提前——所以软件层面依然需要约束（用 atomic + release/acquire，或编译屏障）；② 在 PSO/WO/RC 或 ARM/Power 上，这一条会被硬件直接破坏（这正是讲义 slide 20 说”but real hardware will do this!”的语境）；③ 严谨的做法是不依赖”我猜这台机器不会”，而是显式表达意图。

(c) 哪些 fence 是必要的？

• 必要的是 [2]（P0 侧，位于 A=1 与 Ready=1 之间）与 [5]（P1 侧，位于 x=Ready 与 y=A 之间）。它们分别提供 release 语义（”数据写好之前不发布标志”）与 acquire 语义（”拿到标志之后才读数据”）。在 x86 上，[5] 的硬件效果由”load 不与 load 重排”免费提供（但编译器约束仍需 atomic 或编译屏障），[2] 需要一条 mfence（或把 Ready=1 写成 release store）。
• [1]/[3]/[4]/[6] 是”保守但多余”的：它们把一个额外的次序强加给某一段，换来更长的停顿而不增加任何必要的保证。[1]/[3] 只延长了 P0 的停顿（[3] 甚至要等 Ready=1 提交完成才能继续，而后面没有需要等待的访存）；[4]/[6] 同理。讲义的图示专门把 WO（Weak Ordering）标成 “Overly Conservative“，就是为了对比：WO 要求在同步点两侧都等先前操作全部完成，而实际上只有一侧需要对的一类操作——这正是 Release Consistency（RC） 的出发点。
• 工程落点：现代代码不该手写这六个位置的取舍，而应写成 A = 42; flag.store(1, std::memory_order_release); 与 while (flag.load(std::memory_order_acquire) == 0); use(A); ——把 fence 的种类与位置交给 acquire/release 语义与编译器。

Q2. 某同学说：”我的多线程代码用 pthread_mutex 保护了所有共享数据，所以在 x86 上正确，在 ARM 上也一定正确。” 请用数据竞争与 SC for DRF 判断这个说法，并指出它在什么情况下会失效。

【答案】

说法基本正确，但有一个前提必须被检查：程序是否真的”所有共享访问都被保护”，即是否 DRF。

1. 理论基础：C11 / C++11 / Java 5 为无数据竞争（data-race-free）的程序提供顺序一致性保证（”SC for DRF”，CS149 slide 59）。pthread 的 lock/unlock（以及 C++ 的 std::mutex）在实现上是用 acquire/release 语义的原子操作做的：unlock 释放（release），lock 获得（acquire）。因此同一把锁保护的临界区之间建立了 happens-before 关系：前一个临界区里的所有写在下一个临界区开始前对后者可见。只要程序在锁的串行化下没有并发冲突访问，它在 ARM 上跑出的结果与 SC 机器一致——这正是讲义”properly synchronized programs yield SC results”与”relaxed models 的复杂度被封进库”的结论。
2. 失效情形一：程序其实有数据竞争（最常见）。例如：某个共享变量漏加锁；或者用”双检锁（double-checked locking）”在锁外读一个标志/指针来决定是否加锁——那个锁外的读与写者构成数据竞争，于是整个程序的保证全部失效（未定义行为）。此时在 x86 上”看起来对”是因为 TSO 较强、编译器恰好没重排；在 ARM 上，即使 pthread_mutex 实现完全正确，程序依然可能读到未初始化的对象。结论：锁的正确性只覆盖它保护的东西；锁外的裸访存会把 DRF 契约打碎。
3. 失效情形二：把”同步”做在共享内存之外。用 volatile、std::atomic 的 relaxed 顺序、”时间上看起来够久”的自旋等非同步手段来传递数据，都会破坏 DRF。
4. 失效情形三：锁的粒度和数据布局。即使 DRF 成立，若两个线程各自加不同的锁却更新同一条 cache line 上的两个变量，程序依然 DRF（语言层面安全），但性能会因为伪共享退化（实测可达 3×；见示例三）——语义正确不等于性能可接受。
5. 正确的实践：用同一个同步对象覆盖”发布数据”和”访问数据”两侧；优先使用语言/库提供的原语而不是自造标志位；用 ThreadSanitizer 之类的动态工具找数据竞争；并记住一句判据——“用锁保护了所有共享数据” 必须被证明，而不能被假定。

Q3. （定量）某系统：3.0 GHz、16 核、cache line 64 B、互连带宽 20 GB/s，一次一致性事务（行转移 + 串行化点排队）平均 40 ns。程序处理 $10^8$ 个元素，每元素 8 B，且每个元素都要做一次落在同一条 cache line 上的原子 fetch_add。请估算：(a) 串行化点需要多久？(b) 需要多少一致性带宽？(c) 改成”每线程私有计数器 + 末尾一次归约”后是多少？(d) 用第 4 节的机器平衡点解释这组数字。

【答案】

(a) 串行化点的时间：所有 $10^8$ 次原子操作都落在同一条 cache line 上，而每次 fetch_add 都要求该行的独占所有权，因此被互连这个唯一的串行化点排成一条链：

（等价地说，串行化点的事务吞吐上限 $= 1/40\ \text{ns} = 2.5\times10^7$ 事务/s，要完成 $10^8$ 次就得 4 s。这与线程数、核数无关——并行度被压成 1，正是示例三”伪共享把并行度压回 1”的定量版本。）

(b) 一致性带宽：

• 若每次原子操作都触发一次 64 B 行转移：$10^8 \times 64\ \text{B} = 6.4\ \text{GB}$，占用带宽时间 $6.4\ \text{GB} / 20\ \text{GB/s} = \mathbf{0.32\ s}$。
• 有效载荷只有 $10^8 \times 8\ \text{B} = 0.8\ \text{GB}$ ⇒ 有效载荷率 $\mathbf{0.8\ GB/s}$（仅 4% 的带宽），而线路流量 6.4 GB/s（放大 8 倍）占带宽的 32%。
• 参照量纲：256 MB 数组在 20 GB/s 下遍历一次需 12.8 ms；6.4 GB 是它的 25 倍，即纯搬运 0.32 s。
• 对比 (a)：0.32 s（带宽）≪ 4.0 s（串行化延迟） ⇒ 这个程序不是带宽受限，而是被一致性事务的延迟-吞吐串行化点限制。这是本讲最容易被误判的一类性能问题：盯着”带宽够不够”看不出问题，必须看”事务是不是被串行化了”。

(c) 私有计数器 + 末尾归约：

• 把 16 个计数器用 alignas(64) 各自放到独立行，每个线程只更新自己的：同一条行被多个核抢的情况消失，每次 fetch_add 退化为本地 L1 的原子操作（~几个周期），一致性事务数从 $10^8$ 降到 $O(P)$（外加归约时的 $P$ 次行转移）。
• 数据布局改为：改为各线程在寄存器/本地变量里累加（连原子操作都不需要），最后 $P$ 个线程各做一次 fetch_add 到全局计数器：原子操作数从 $10^8$ 降到 16，一致性流量近似为 0。
• 上界由”每个线程在本地处理 $10^8/16 = 6.25\times10^6$ 个元素”决定：即使按每个元素 2 个周期估算，单线程 $\approx 1.25\times10^7$ 周期 $\approx 4.2\ \text{ms}$，16 线程并行远优于 4.0 s（提升可达百倍量级），并且剩下的开销是纯本地操作。

(d) 用机器平衡点解释：该机器峰值 $16 \times 3.0\ \text{GHz} \times 8\ \text{SIMD} \times 2(\text{FMA}) = \mathbf{768\ GFLOPS}$，带宽 20 GB/s ⇒ 机器平衡点

而本题的代码算术强度为 $0$（纯原子操作 + 数据搬运）。也就是说它离平衡点差着无穷远：增加算力、增加核数、提高频率都毫无用处，唯一的杠杆是”减少被拉回一致性序的次数”。这组数字（4.0 s vs 4.2 ms）说明：在共享内存并行里，决定性能的往往不是有多少核心，而是有多少操作被迫共享同一条 cache line、以及它们被迫按什么顺序发生——而”顺序由谁定义”，正是本讲（Memory Consistency）要回答的问题。