Lecture 15: Implementing Synchronization

目录 · ← l14 · l16 →

Lecture 15: Implementing Synchronization

1. 章节标题与概述

Lecture 15: Implementing Synchronization（同步原语的实现：从原子指令到可扩展的锁与屏障）

• 本讲核心问题：同步原语（synchronization primitive）的语义（”互斥”、”屏障”）很容易用一句话说清，但高效地实现它们却完全由硬件细节决定：一条原子指令在总线上究竟产生多少流量？P 个处理器同时抢一把锁时，瓶颈是锁本身还是互连？屏障的延迟能不能从 O(P) 降到 O(log P)？讲义开篇就把范围钉死在两件事上——(1) 保证互斥（mutual exclusion）的原语：锁（locks）、原子原语（atomic primitives，如 atomic_add）、事务（transactions）；(2) 事件通知（event signaling）的原语：屏障（barriers）、标志（flags）。

• 涉及的主要硬件/软件机制：
  • 硬件侧：原子读-改-写指令（read-modify-write），包括 test-and-set（TAS）、x86 lock cmpxchg（compare and exchange，比较并交换）、atomic_increment / fetch-and-add（原子取号加）；支持这些指令的缓存一致性协议（snooping MSI/MESI，以及 BusRd / BusRdX / BusWB 三类总线事务）；互连（总线/环）作为一致性顺序的串行化点；以及底层的内存一致性模型（memory consistency model，如 TSO）与 fence（内存屏障）。
  • 软件侧：三种”锁算法族”——自旋类（test-and-set、test-and-test-and-set (TTAS)、指数退避）、取号类（ticket lock）、队列/数组类（array-based lock、MCS queue-based lock）；以及屏障的四种实现——朴素共享计数器、两计数器正确版本、sense reversal（感知翻转）、combining tree（合并树）。配套的 Stanford CS149 讲义补充了这些原语赖以成立的地基：一致性不变量、伪共享（false sharing）、顺序一致性（SC）/ 全存储序（TSO）、数据竞争（data race） 与 DRF（data-race-free） 契约。

• 在并行计算知识体系中的角色：本讲是”共享内存并行”这条主线上从硬件机制到编程原语的最后一公里。前面几讲（缓存一致性、目录一致性、侦听实现、内存一致性）解释了”硬件如何让 P 个核看到一个一致的内存”；本讲回答”程序员/运行时库如何在这个内存之上造出锁与屏障，并且让代价不随 P 爆炸”。它同时给出了一条贯穿全课程的量纲：同步不产生任何计算，它只消耗延迟、带宽与程序员的心智——因此锁的可扩展性、屏障的 span、伪共享的流量，最终都要用 work-span 与带宽预算来结算。它也是下一讲（Fine-Grained Synchronization, Lock-Free Programming）的直接前提：理解了 TAS/CAS 的代价，才明白为什么要用细粒度锁与无锁数据结构。

• 配套材料：
  • lectures/16_synchronization.pdf（抽取文本 extracted/16_synchronization.txt，共 29 页）：Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）把 Sep 30 排为第 15 讲 “Implementing Synchronization”，该行的 slides 链接目前以 HTML 注释形式给出（”slides/video from a previous offering; uncomment when posted for Fall 2026”），注释中的 slides 指向 lectures/16_synchronization.pdf。该 PDF 目前位于公开的 https://www.cs.cmu.edu/~418/lectures/ 目录下，可在公开网络直接下载。讲义首页写的是 “CMU 15-418/15-618, Fall 2025 / Lecture 16: Implementing Synchronization”——这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排），不是错误。
  • cs149_supp/sync_consistency.txt：Stanford CS149（Fall 2025）Lecture 15: Memory Coherency and Consistency 的公开讲义抽取（60 页），已公开，作为本讲底层支撑使用（MSI/MESI 状态机、目录一致性、伪共享实测 14.2 s vs 4.7 s、SC/TSO/PC/PSO/WO-RC、fence、DRF 契约）。
  • 讲义中的性能图注明 “Figure credit: Culler, Singh, and Gupta”，即经典教材《Parallel Computer Architecture: A Hardware/Software Approach》的图；MCS 锁算法注释指向经典论文《Algorithms for Scalable Synchronization on Shared Memory Multiprocessors》。
  • 讲课录像（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 创建。

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

2.1 同步事件的三个阶段：把”锁”拆成三个可独立优化的部件

• 定义与目的：讲义把任何一次同步事件拆成三个阶段（slide 3）：
  1. Acquire method（获取方法）：线程如何尝试获得对受保护资源的访问权；
  2. Waiting algorithm（等待算法）：当访问尚未被授予时，线程如何等待；
  3. Release method（释放方法）：临界区工作完成后，线程如何让其他线程获得该资源。 这个拆分的价值在于：锁的性能问题几乎从不均匀分布在三个阶段上。TAS 锁的灾难在 waiting（等待者不停地写，制造总线风暴）；ticket 锁的代价在 acquire（一次原子取号）；MCS 锁的胜利也在 release（精确唤醒下一个，只写一个字节）。把三者分开，就能一眼看出该改哪一段。

• 直观解释（”它是什么？”）：想象只有一个洗手间的办公室。Acquire = 你走过去拧门把手（拧的方式决定了你会不会把整层楼的人都吵醒）；Waiting = 发现门锁着，你怎么办（站在门口不停拧把手 = 忙等待；回工位等同事喊你 = 阻塞）；Release = 你出来后怎么通知下一个人（喊一声”下一位” = 精确唤醒；把门敞开让所有人一起冲 = TAS 式惊群）。同一间洗手间，三种策略的性能差一百倍。

• 三个阶段在五种原语上的展开（表 1）：

• 性能特征：三个阶段的时间量级完全不同——acquire 是”一次原子操作往返”（几十到几百周期，取决于该行在谁手里）；waiting 是”重复次数 × 每次往返“（这才是 TAS 崩溃的根源）；release 是”唤醒几个等待者 × 每个等待者产生的事务数“（这是 MCS/数组锁取胜的地方）。

2.2 硬件结构：私有缓存 + 共享互连 + 原子操作 = 同步的地基

• 定义与目的：同步原语的实现必须建立在一个具体的硬件模型上：P 个核各有私有 L1/L2（保存 cache line 的状态位 M/E/S/I），共享一条互连（总线或环）；互连是一致性事务的串行化点，因此也是”谁先拿到锁”的物理仲裁者；原子读-改-写指令（TAS / CAS / fetch-add）则是唯一能绕过”LOAD-TEST-STORE 非原子”陷阱的硬件机制。

• 直观解释（”它是什么？”）：把共享内存想成一间有 P 个读者的阅览室，每个人手里都有一份复印页。要读，只要手里有复印件（S 态）即可，本地零成本；要改，必须先让所有其他人的复印件作废（BusRdX → Invalidate），然后才能独占涂改（M 态）。这条”改之前先清场”的规则，就是所有同步原语性能代价的物理来源：任何一次原子的写，都是一次”清场广播”。而互连就像阅览室里唯一的传声筒——同一时刻只有一个人在说话。

• 图解（图 1）：典型多核 + 私有缓存 + 共享互连的硬件结构，以及三类一致性事务

        +--------------+  +--------------+  +--------------+  +--------------+
        |   Core 0     |  |   Core 1     |  |   Core 2     |  |   Core 3     |
        | T0      T1   |  | T2      T3   |  | T4      T5   |  | T6      T7   |  <- 线程/SMT
        +------+-------+  +------+-------+  +------+-------+  +------+-------+
               |                 |                 |                 |
        +------v-------+  +------v-------+  +------v-------+  +------v-------+
        | L1D  32 KiB  |  | L1D  32 KiB  |  | L1D  32 KiB  |  | L1D  32 KiB  |
        | 每行带状态位  |  |   M / E /    |  |              |  |              |
        |  (~4 cyc)    |  |   S / I      |  |              |  |              |
        +------+-------+  +------+-------+  +------+-------+  +------+-------+
               |                 |                 |                 |
        +------v-------+  +------v-------+  +------v-------+  +------v-------+
        | L2  256 KiB  |  | L2  256 KiB  |  | L2  256 KiB  |  | L2  256 KiB  |
        |  (~10 cyc)   |  |              |  |              |  |              |
        +------+-------+  +------+-------+  +------+-------+  +------+-------+
               |                 |                 |                 |
  =============+=================+=================+=================+==========
     共享互连 (总线 / 环) —— 一致性事务的【串行化点】, 同一时刻只有 1 个事务
        BusRd  : 我要一份只读副本 (别人可以继续持有 S)
        BusRdX : 我要独占并修改  -> 让所有其他副本失效 (Invalidate)
        BusWB  : 我把脏行写回 (write-back), 由我提供数据给请求者
  =============+=================+=================+=================+==========
               |                 |                 |                 |
        +------v-----------------v-----------------v-----------------v-------+
        |      共享 L3 (含目录 directory, 包含性 inclusive)  (~40 cyc unshared) |
        +--------------------------------+-----------------------------------+
                                         |
                                  +------v-------+
                                  |     DRAM     |  local ~120 cyc / remote ~400
                                  +--------------+

• 关键操作与性能特征（数据取自配套 CS149 讲义给出的 Core i7 Xeon 5500 量级，用于建立”预算感”）：
  • L1 命中 ≈ 4 周期：这是 TTAS 等待者”在本地缓存副本上自旋”的成本——几乎免费的等待；
  • L3 命中、行未被共享 ≈ 40 周期；行被别的核共享 ≈ 65 周期；行在别的核里是脏的（modified in another core）≈ 75 周期：这三个数字就是”一次穿越互连的一致性事务”的价目表，也是同步原语延迟的主要构成；
  • 本地 DRAM ≈ 120 周期（约 30 ns）；远端 DRAM ≈ 400 周期（约 100 ns）；
  • 带宽视角：一条 64 B 的 cache line 每被”抢走一次”就要占满互连传一次。若互连数据带宽等效为 8 B/cycle，则一次一致性行传输 = 8 个互联周期；这是本讲所有数值算例的交换率基准（延迟 ~75 周期，带宽 8 B/周期/行）。
  • 吞吐量含义：正因为”一次原子的写 = 一次清场广播”，同步原语的可扩展性本质上是一个互连流量问题：每次同步事件产生多少个事务、每个事务多大、P 增大时事务数是否增长（O(1) / O(P) / O(P²)）。

2.3 忙等待 vs 阻塞式同步：为什么在并行程序里”自旋”往往是正确的

• 定义与目的：
  • Busy waiting（忙等待 / spinning）：while (条件 X 不成立) {}，然后执行”假定 X 成立”的逻辑。线程不放弃处理器。
  • Blocking synchronization（阻塞式同步）：if (X 不成立) block until X 成立;——由 OS 调度器把线程换下处理器（de-schedule），让别的线程跑；典型例子是 pthread_mutex_lock。
  • 目的：在”等多久”与”等待期间谁用 CPU”之间做选择。

• 直观解释（”它是什么？”）：自旋 = 在电梯门口原地按按钮；阻塞 = 回工位干活，让前台打电话叫你。操作系统课程教”自旋是坏的”，因为在超售（oversubscribed）的机器上，你按按钮的时候别人没 CPU 可用，纯粹烧电。但讲义明确指出：在性能关键的并行程序里，我们通常不超售系统（机器上不会同时跑好几个 CPU 密集程序），这时自旋反而更好——因为没有别的活要干，把 CPU 让出去只会换来两次上下文切换的开销。讲义还特意提醒一个容易混淆的点：“自旋浪费处理器”与”用多线程交错执行来隐藏访存延迟”是两件不同的事，不要拿后者为前者辩护。

• 讲义给出的”自旋优于阻塞”的四种情形（slide 6）：
  1. 调度开销大于预期等待时间（OS 上下文切换是微秒量级，而抢一把锁可能只要几百纳秒）；
  2. 尾延迟（tail latency）效应：阻塞/唤醒的排队会让延迟分布的长尾变长；
  3. 处理器的资源本来也没别的任务要用（不超售）；
  4. 需要自旋的现实接口示例：OSSpinLockLock(&lock)、pthread_spin_lock(&spin)。
• 图解（图 2）：两种等待策略的执行模型与代价

 (a) 忙等待 (spinning): 等待者持续占用执行单元, 反复访问同步变量
    core0 : [T&S][T&S][T&S][T&S][T&S][T&S][T&S] |== 临界区 ==| [T&S][T&S]...
                     ^ 每次 T&S 都可能产生一次互连事务 (见 2.6)
    core1 : |================ 临界区 (持有锁) ================| [ 自旋 ]...
    core2 : [T&S][T&S][T&S][T&S][T&S][T&S][T&S][T&S][T&S][T&S]...
            代价 = 自旋指令的执行 + 互连事务流量; 收益 = 零调度延迟, 一旦
                   锁释放立刻能上 (亚微秒级响应)

 (b) 阻塞 (blocking): 失败即让出 CPU, 由 OS 调度器在锁释放时唤醒
    core0 : [try]--[阻塞/让出]........(OS 不调度我)........[被唤醒][得到锁][临界区]
    core1 : [      临界区      ][unlock -> 唤醒 core0 ]
            代价 = 2 次上下文切换 (µs 级) + 调度器排队延迟;
            收益 = 等待期间 CPU 可用于其它线程 (只有真有别的活时才划算)

• 性能特征：自旋的代价是互连流量 + 执行单元占用（可测量为”每次失败尝试的事务数”），阻塞的代价是两次上下文切换 + 调度延迟（微秒级）。判据很干脆：预期等待时间 < 上下文切换开销 ⇒ 自旋；否则阻塞。这也是为什么”混合锁”（先自旋一小会儿，再阻塞，如 Linux futex、Java 的偏向锁/自适应自旋）在实践中胜出。

2.4 朴素锁为什么错：LOAD-TEST-STORE 不是原子的

• 定义与目的：讲义用一个”看起来对、实际错”的锁作为热身（slide 8）：

  lock:
    ld   R0, mem[addr]     ; 把锁字读进 R0
    cmp  R0, #0            ; 和 0 比较
    bnz  lock              ; 非 0 说明别人持有 → 回到顶部重试
    st   mem[addr], #1     ; 认为锁空闲 → 置 1, 进入临界区
  unlock:
    st   mem[addr], #0     ; 释放: 写 0
  

• 直观解释（”它是什么？”）：这就是“看没人举手，我就直接进会议室”——看（load）和坐（store）之间有一个时间窗。类比：停车场只剩一个车位，两辆车都”看到”空位，然后都倒进去。错误的原因是 LOAD-TEST-STORE 不是原子操作（not atomic）：P0 读到 0，P1 也读到 0，P0 写 1，P1 也写 1 —— 两个线程同时认为自己持有锁，互斥彻底失效（这是数据竞争 data race 的最经典形态）。

• 要点：修好它的唯一办法是让”读—判断—写”变成一条不可分割的硬件指令，即原子读-改-写（atomic read-modify-write）：TAS、CAS、fetch-add 都属于这一类。

2.5 Test-and-Set 锁：用一条原子指令换来正确性，却换来一场总线风暴

• 定义与目的：test-and-set（TAS）指令语义（slide 9）：ts R0, mem[addr] = 把 mem[addr] 读入 R0，并且若原值为 0 则把它设为 1（整个读+条件写原子完成）。于是锁可以用两条指令实现：

  lock:
    ts   R0, mem[addr]
    bnz  R0, lock          ; 返回非 0 ⇒ 锁已被别人持有, 继续自旋
  unlock:
    st   mem[addr], #0
  

• 直观解释（”它是什么？”）：TAS 就像“伸手抢座位”：伸手和坐下是同一下动作，不可能两个人同时坐下。代价是：每一次尝试伸手，都会把旁边所有拿着座位复印件的人手里的复印件作废（一次 BusRdX + 对所有共享者的 Invalidate）——即使锁已经被别人占着，即使你明知抢不到。

• 图解（图 3）：TAS 锁在互连上的实际时序（对应 slide 10/11 的流量图）

时间轴  ------------------------------------------------------------------>
P0 (持有者)
   |-- BusRdX: 拿独占行, 写 1 -->|========== 临界区 (持有锁) ==========|
                                                                      |-- unlock:
                                                                      |  BusRdX 再拿
                                                                      |  独占行, 写 0 -->|
P1 (等待者)
   |            T&S --BusRdX--> 失败(读到 1) ----> T&S --BusRdX--> 失败 ----> T&S 成功 -->
   |            ^                ^                 ^
   |            |                |                 |
   每次失败的 T&S 都要: 抢互连 -> 发 BusRdX -> 让 P0 的副本失效 -> 读回 1 -> 失败
   |<------- 一次失败 T&S 的往返 ≈ 40~75 周期 (取决于争用) ------->|
P2 (等待者)
   |              T&S --BusRdX--> 失败 ---------> T&S --BusRdX--> 失败 ---------> ...
互连 (总线)
   |##失效##|##失效##|##失效##|##失效##|##失效##|##失效##|##失效##|##失效##|
   ^ 满载! 同一时刻只有 1 个事务能上总线; 等待者越多, 总线越挤

讲义给出的两条结论:
  (1) 总线争用使"锁的移交"变慢: 持有者 unlock 时也必须排队等总线
  (2) 图中未画出但同样致命: 总线争用也拖慢【临界区本身】的执行
      (临界区里的访存同样要从这条拥挤的互连上过)

• 性能特征（slide 13/14）：基准程序是 P 个处理器合计执行 N 次 lock(); critical-section(c); unlock();，并把临界区时间扣掉，只留取锁/放锁的时间；横轴是处理器数。曲线随 P 急剧上升，原因是”总线争用 → 锁移交变慢 + 临界区也被拖慢“。讲义给出的理想锁应具备的五条性质，以及 TAS 锁的成绩单：

2.6 Test-and-Test-and-Set（TTAS）：把”等待”从写操作改成读操作

• 定义与目的：TTAS（slide 15）的核心思想是把等待与尝试分开：先在本地缓存副本上做只读自旋（命中 L1，零互连流量），只有观察到锁被释放（*lock == 0）时才用 TAS 真正去抢：

  void Lock(int* lock) {
    while (1) {
      while (*lock != 0);                 // 另一个处理器持有锁时: 只在本地缓存副本上自旋
      if (test_and_set(*lock) == 0)       // 锁被释放了: 这才去抢
        return;
    }
  }
  void Unlock(volatile int* lock) { *lock = 0; }
  

• 直观解释（”它是什么？”）：TAS 锁是每个人都在不停地拧门把手；TTAS 锁是大家坐在自己工位上盯着门口的灯（读本地副本），灯一变就集体冲过去抢（TAS）。因为”盯着看”是本地缓存命中（4 周期），互连上几乎没人说话；只有当门真的开了，才会发生一次”惊群”式抢锁。

• 图解（图 4）：TTAS 的互连流量（对应 slide 16/17）

P1 (持有者)  |--BusRdX, 写 1-->|===== 临界区 =====|--BusRdX, 写 0-->|
                                                       ^ 释放时向所有共享者发 Invalidate
P2 (等待者)  [BusRd: 拿一份只读副本, 停在 S 态]
             [只在本地 L1 上反复读 => 大量本地命中, 零互连事务]
                                        ^被 Invalidate^
                                                       |--BusRdX--> 抢(成功/失败)
P3 (等待者)  [BusRd: 拿只读副本][本地读][本地读]...    ^被 Invalidate^
                                                       |--BusRdX--> 抢(败) --> 回去本地读
互连
   | BusRd |      (长时间空闲: 大家都在本地读)      | Invalidate ×(P-1) | BusRdX ×(P-1) |
                                                     ^ 一次释放: 每个等待者 1 次失效

• 性能特征（slide 18）：
  • 无竞争时延迟略高于 TAS：必须先 test（读）再 test-and-set，多一次步骤；
  • 互连流量大幅下降：每次锁释放，每个等待者只产生 1 次失效，即 O(P) 次失效——对比 TAS 是”每个等待者每次测试都产生一次失效”（与等待时长成正比，可以差几个数量级）。讲义进一步指出：如果所有 P 个处理器都缓存了这一行，那么总体互连流量是 O(P²) 量级；
  • 可扩展性改善（因为流量降了）；存储不变（1 个 int）；仍然没有公平性。
  • 注意残留成本：一次释放后仍会有 P-1 个等待者同时发 BusRdX（惊群），输掉的那些还要重新 BusRd 把行读回来继续自旋——这部分流量仍然随 P 线性增长，这正是后面 ticket / array / MCS 锁要解决的问题。

2.7 退避（Back-off）：用”少问几次”换”少堵总线”

• 定义与目的：抢占失败后先等一会儿再重试（slide 19）：

  void Lock(volatile int* l) {
    int amount = 1;
    while (1) {
      if (test_and_set(*l) == 0) return;    // 抢到就返回
      delay(amount);                        // 失败: 退避一段时间
      amount *= 2;                          // 指数增长
    }
  }
  

• 直观解释（”它是什么？”）：这就是以太网的 CSMA/CD 退避策略搬到锁上：撞车了就别马上再撞，随机/递增地等一会儿。大家的尝试频率一降，互连上的无效事务自然就少了。

• 讲义提出的关键问题与答案：“无竞争时延迟与 TAS 相同，但在竞争下延迟可能更高。为什么？”——因为退避的线程在锁被释放的那一刻可能正睡着：锁变空闲了它也不知道，必须等自己的 delay 走完才去看，于是”锁空闲但没人来拿”的空窗期被拉长；等待者越多、退避越久，这个空窗越大。
• 性质：流量比 TAS 小、可扩展性改善、存储仍是 1 个 int；但指数退避会造成严重的公平性问题（severe unfairness）——新来的请求者退避间隔更短（amount 从 1 开始），因此有可能后到先得，老等待者理论上可以被无限期插队（饥饿 starvation）。
• 性能特征：退避把”流量随等待时长线性增长”改成了”流量随退避次数对数增长”，但它不解决公平性，也不消除惊群；工程上常与 TTAS 组合（TTAS + back-off），并用固定上限避免退避过久。

2.8 Ticket 锁：把”抢锁”变成”排队取号”，一次释放只产生 O(P) 流量

• 定义与目的：TAS 系锁的根本毛病是”释放瞬间所有等待者一起用 TAS 去抢“。ticket 锁（slide 20）改用 原子取号 + 只读等待：

  struct lock { volatile int next_ticket; volatile int now_serving; };
  
  void Lock(lock* l) {
    int my_ticket = atomic_increment(&l->next_ticket);  // 取一个号
    while (my_ticket != l->now_serving);                // 等叫号 (纯读!)
  }
  void unlock(lock* l) { l->now_serving++; }            // 叫下一个号
  

• 直观解释（”它是什么？”）：银行取号机。进门先按一下取号机（一次原子加），然后坐下盯着叫号屏（只读），被叫到才起身（进临界区）。取号机只在”进门”那一瞬间被使用一次，因此抢锁的”惊群”消失了。
• 性能特征：
  • Acquire 不需要原子操作（讲义原文：No atomic operation needed to acquire the lock (only a read)）；
  • 每次释放只产生 1 次失效（O(P) 互连流量）：now_serving++ 使所有正在读该行的等待者失效，它们各自重新读一次；
  • 天然 FIFO 公平（先到先得，理论无饥饿）——这是它相对 TAS/TTAS/退避的免费礼物；
  • 代价：取号必须原子（一次 BusRdX）；等待者在共享行上自旋，每次释放后 P-1 个读者要重新取数（残余 O(P) 流量，见 §4 算例）。
  • 工程细节（笔记补充）：next_ticket 与 now_serving 若落在同一 cache line，则每次”取号”都会让所有等待者的只读副本失效——把两者分开填充（padding）是常见优化。

2.9 数组锁（array-based lock）：让每个等待者在不同地址上自旋

• 定义与目的：既然 ticket 锁的残余流量来自”所有等待者共享同一行”，那就给每个等待者一个独立的、填过填充的槽位（slide 21）：

  struct lock {
    volatile padded_int status[P];   // 每个槽位填充(padded), 保证不共用 cache line
    volatile int head;
  };
  int my_element;                     // 每个线程私有
  
  void Lock(lock* l) {
    my_element = atomic_circ_increment(&l->head);   // 环形递增, 分配槽位
    while (l->status[my_element] == 1);             // 只在自己的槽位上自旋
  }
  void unlock(lock* l) {
    l->status[my_element] = 1;                      // 标记自己的槽位可用
    l->status[circ_next(my_element)] = 0;           // 放行下一个槽位
  }
  

• 直观解释（”它是什么？”）：医院分诊叫号 + 每人一个专属指示灯。你不再盯着公共叫号屏，而是盯自己头顶那盏灯——别人释放锁时只点亮你这一盏（写一个地址），其余人的灯纹丝不动。于是”一次释放”在互连上只需改动极少量数据。
• 性能特征：每次释放 O(1) 互连流量（写到下一个等待者的槽位；若每个槽位独占一行，则约 2 次行事务）；但锁的空间开销随 P 线性增长（status[P] 且带填充 → P × 64 B）；此外 atomic_circ_increment（带环形回绕的原子加）是更复杂的原子操作，开销更高（讲义原文）。
• 与 MCS 的对比：数组锁用空间换”每个等待者一个独立地址”；MCS 用每线程一个私有节点换同样的效果，但空间是每线程私有的（不随锁数量放大），且没有”环形递增”的复杂度。

2.10 x86 cmpxchg：实现 CAS 系原语的硬件指令

• 定义与目的：lock cmpxchg dst, src（slide 22）是 x86 上实现 CAS、ticket、MCS 等一切”比较并交换”语义的指令：

  lock cmpxchg dst, src
      if dst == accumulator:        ; accumulator 通常是 eax
          ZF = 1                    ; 标志寄存器置位 = 成功
          dst = src                 ; 写入新值
      else
          ZF = 0                    ; 失败
          accumulator = dst         ; 把当前值返回给调用者
  

  语义三步 (讲义 slide 22 的原文):
    1. Does the dst have the value we think it has?    (目标里是我们以为的值吗?)
    2. Then make the update                             (是 → 更新)
    3. If not return the current value                  (不是 → 返回当前值, 让软件重试)
  

• 直观解释（”它是什么？”）：CAS 是“验货后付款”：我先说”如果箱子里还是我上次看到的那件货，就把它换成我的货”，硬件保证”看”与”换”之间不被打断；如果箱子被换过了，把新货色告诉我，我自己决定要不要重试。lock 前缀的作用是让这条指令在多核之间真正原子（在缓存一致性协议上表现为”取独占所有权”）。
• 性能特征：lock cmpxchg 在成功路径上等价于一次 BusRdX（拿独占 + 让所有人失效，~65–75 周期）；在失败路径上（值已被改）通常无需总线事务（本地就能判断），这是 CAS 循环优于 TAS 循环的原因之一。CAS 循环的经典隐患是 ABA 问题（值从 A 变 B 又变回 A，CAS 无法察觉），这也是下一讲（lock-free）的核心议题。

2.11 队列锁（MCS lock）：O(1) 流量 + FIFO 公平 + 精确唤醒

• 定义与目的：MCS 锁（Mellor-Crummey & Scott，讲义 slide 23 给出伪代码；注释指出要用到 slides 22 的 cmpxchg 语义）让每个等待者在自己的私有节点上自旋，锁本身只保存队尾指针：

  AcquireQLock(*glock, *mlock)              ReleaseQLock(*glock, *mlock)
  {                                          {
     mlock->next = NULL;                        do {
     mlock->state = UNLOCKED;                     if (mlock->next == NULL) {
     ATOMIC();                                       x = CMPXCHG(glock, mlock, NULL);
       prev = glock;    // 原子交换                       if (x == mlock) return;
       *glock = mlock;                                  }
     END_ATOMIC();                                  else {
     if (prev == NULL) return;   // 队空, 直接获得          mlock->next->state = UNLOCKED;
     mlock->state = LOCKED;                               return;
     prev->next = mlock;                                }
     while (mlock->state == LOCKED) ;  // SPIN        } while (1);
  }                                          }
  

• 直观解释（”它是什么？”）：排队传话。每个人拿着自己的小纸条（本地节点）站在队伍里，纸条上写着”轮到我了吗”。上一个人离开时，只需要走到你面前拍你一下（写你的 state），不需要向全楼广播。所以：流量 O(1)、顺序严格 FIFO、被唤醒的人恰好一个（不会惊群）。
• 图解（图 5）：MCS 队列锁的数据结构与唤醒路径

   glock (全局锁: 只是一个指向队尾的指针)
     |
     v
  +---------+    next    +---------+    next    +---------+    next    +---------+
  | mlock   |----------->| mlock   |----------->| mlock   |----------->| mlock   |
  |  P3     |            |  P7     |            |  P1     |            |  P4     |
  | LOCKED  |            | LOCKED  |            | LOCKED  |            | LOCKED  |
  +---------+            +---------+            +---------+            +---------+
   队首=持有者               |                     |                      ^ 新来者
     |                       |                     |                      | 挂到队尾
     |  每个节点都是【线程私有】的变量 (通常在线程栈/线程本地存储里)
     |  => 每人在自己的 cache line 上自旋, 互不干扰, 零互连流量
     |
     +--- unlock: 若 mlock->next != NULL, 只写 mlock->next->state = UNLOCKED
                  => 精确唤醒 1 个等待者, 互连上只搬 1 条 cache line (O(1))
         若 mlock->next == NULL: 用 CMPXCHG(glock, mlock, NULL) 尝试"我是最后一个
                 且无人排队" -> 成功则锁变空闲; 失败说明有人正在挂入, 等它把 next 写出来

  释放路径 (所有锁算法对比的关键):
     TAS / TTAS / ticket : 释放 -> 通知【所有】P-1 个等待者 (O(P) 流量)
     MCS                 : 释放 -> 通知【下一个】等待者 (O(1) 流量), 且顺序 = 请求顺序

• 性能特征：每次释放 O(1) 互连流量；FIFO 公平（无饥饿）；存储开销是”每线程一个节点”（不是每锁 P 份，因此锁多了也不炸）；代价是：需要 cmpxchg 处理”释放时发现无人排队”的竞态（释放路径更复杂），且节点必须常驻（不能放在会被回收/搬移的栈帧里，否则队列断裂——工程上用线程本地存储或节点池）。
• 与讲义 slide 24 的提示一致：算法的正确性依赖 cmpxchg 的确切语义（成功/失败时返回值不同），伪代码中的 x = CMPXCHG(glock, mlock, NULL) 就是”如果 glock 仍是 mlock 就把它设为 NULL”。

2.12 屏障（barrier）：从”朴素共享计数器”到”合并树”

屏障是事件通知类原语的代表：它不保护数据，而是让 P 个线程在同一个逻辑时刻会合。讲义用四步把屏障的实现讲透。

(a) 朴素集中式屏障：为什么错的版本”看起来对”

struct Barrier_t { LOCK lock; int counter; /* init 0 */ int flag; };
// 讲义 slide 25: 朴素版本
void Barrier(Barrier_t* b, int p) {
  lock(b->lock);
  if (b->counter == 0) { b->flag = 0; }      // 第一个到达者清 flag
  int num_arrived = ++(b->counter);
  unlock(b->lock);
  if (num_arrived == p) { b->counter = 0; b->flag = 1; }  // 最后一个到达者置 flag
  else { while (b->flag == 0); }             // 其余人等 flag
}

• 它对不对？ 讲义的问题问得很准（slide 25）——请考虑连续两个屏障的用法：

  do stuff ... ; Barrier(b, P); do more stuff ... ; Barrier(b, P);
  

  朴素版本在”循环反复使用同一个屏障”时会失败：快线程走完屏障 1 后冲到屏障 2，作为屏障 2 的”第一个到达者”把 flag 清成 0；而慢线程可能还没观察到屏障 1 的 flag == 1，它看到的却是被清掉的 0，于是永远自旋下去（死锁）。根因是复用同一个 flag 而没有”代际（generation）”概念——这就是为什么要引入 sense reversal 或 leave_counter。

(b) 两计数器正确版本：等所有人离开上一代，再清 flag

struct Barrier_t { LOCK lock;
                   int arrive_counter;  // init 0
                   int leave_counter;   // init P
                   int flag; };
void Barrier(Barrier_t* b, int p) {
  lock(b->lock);
  if (b->arrive_counter == 0) {            // 我是第一个到达者
    if (b->leave_counter == P) {           // 确认没有别人"还留在屏障里"
       b->flag = 0;                        // 可以安全地清 flag
    } else {
       unlock(lock);
       while (b->leave_counter != P);      // 等所有人离开上一个屏障
       lock(lock);
       b->flag = 0;
    }
  }
  int num_arrived = ++(b->arrive_counter);
  unlock(b->lock);
  if (num_arrived == p) {                   // 最后一个到达者
    b->arrive_counter = 0;
    b->leave_counter = 1;
    b->flag = 1;
  } else {
    while (b->flag == 0);                   // 等 flag
    lock(b->lock); b->leave_counter++; unlock(b->lock);   // 记录"我离开了"
  }
}

• 核心思想（讲义原文）：“等所有处理器先离开上一个屏障，清清白白之后，才为下一个屏障清 flag”——用 leave_counter 给 flag 加了”代际隔离”。代价是：等待者要自旋两次（一次等 flag，一次等别人离开 / 加锁更新 leave_counter）。

(c) Sense reversal（感知翻转）：一次自旋解决问题

struct Barrier_t { LOCK lock; int counter; /* init 0 */ int flag; /* init 0 */ };
int local_sense = 0;   // 每个处理器私有的 sense
void Barrier(Barrier_t* b, int p) {
  local_sense = (local_sense == 0) ? 1 : 0;    // 翻转自己的 sense
  lock(b->lock);
  int num_arrived = ++(b->counter);
  if (num_arrived == p) {                       // 最后一个到达者
    unlock(b->lock);
    b->counter = 0;
    b->flag = local_sense;                      // 把 flag 置为"新一代的值"
  } else {
    unlock(b->lock);
    while (b.flag != local_sense);              // 等 flag 变成我这一代的值
  }
}

• 直观解释（”它是什么？”）：用”翻转”代替”清零”。大家约定：第 1、3、5… 次屏障等 flag == 1，第 2、4、6… 次等 flag == 0。这样永远不需要”把 flag 清回初值”这个危险动作——flag 的每一次变化本身就是”新一代开始”的信号。类比：交通灯用红绿交替而不是”先熄灭再亮”，就不会出现”灯灭了但有人还在过马路”的窗口。
• 性能特征（讲义原文）：Sense reversal 优化把两次自旋变成一次（不需要再等 leave_counter）；local_sense 必须是每处理器私有的；flag 字段建议单独占一条 cache line（讲义在 slide 25 反问”Why?”——因为 flag 被 P-1 个等待者同时读，若与频繁写的 counter/lock 同行，每次计数更新都会让所有等待者的只读副本失效，制造伪共享级别的流量）。

(d) 集中式屏障的流量与 span，以及合并树屏障

• 流量（slide 28）：每次屏障 O(P) 互连流量：
  • 所有线程：2P 次写事务用于抢屏障锁与更新计数器（在”锁获取是 O(1)”的假设下算作 O(P) 流量）；
  • 最后一个线程：2 次写事务（写 flag、清计数器），但因为 flag 有大量共享者，代价仍是 O(P)；
  • P-1 次读事务去读更新后的 flag。
• 但真正的伤害是串行化（slide 28 原文）：“still serialization on a single shared lock ⇒ span（整个操作的延迟）是 O(P)”。这一点与流量无关：所有线程在同一个原子变量上排队，屏障延迟随 P 线性增长。
• 能做得更好吗？能——合并树屏障（slide 29）：
  • 合并树（combining tree）更好地利用了互连拓扑中的并行性，达到 lg(P) 的 span；
  • Acquire（到达）：处理器到达屏障时，对父节点的计数器做一次递增，递归向上直到根；
  • Release（释放）：从根开始，逐层向下通知子节点释放；
  • 重要限制（讲义原文）：这套策略在总线上意义不大，因为总线上的所有流量本来就被串行化；合并树的价值体现在点对点互连（如树、环、Mesh）上。
  • 对比：集中式屏障 = 高竞争（high contention），单把屏障锁 + 单个计数器成为瓶颈。
• 图解（图 6）：集中式屏障 vs 合并树屏障的执行模型

 (a) 集中式屏障: 树高 1, 扇入 P —— 所有线程争同一个变量, span = O(P), 竞争 O(P^2)
       T0  T1  T2  T3  T4  T5  T6  T7        (P = 8)
        \   \   \   |   /   /   /   /
         \   \   \  |  /   /   /   /
        +-v---v---v--v--v---v---v---v-+
        |  单一 lock + counter + flag  |  <-- 串行化点: 每次只能有 1 个线程进来
        +-----------------------------+
        到达: lock -> ++counter -> unlock -> 自旋等 flag     (P 次串行加锁)
        离开: 最后一个到达者置 flag -> P-1 个读者重新取数      (O(P) 流量)

 (b) 合并树屏障: 扇入 2, 树高 log2(P) —— 到达自底向上合并, 释放自顶向下广播
                        +-------------------+
                        |   root (0)        |  flag/sense
                        +---------+---------+
                    +-------------+-------------+
              +-----v-----+               +-----v-----+
              |  node 1   |               |  node 2   |
              +-----+-----+               +-----+-----+
                 +--+--+                     +--+--+
                 |     |                     |     |
              node 3  node 4              node 5  node 6
                 |     |                     |     |
                T0    T1                    T2    T3      (P = 4 的示意)
        到达 (acquire): 每个叶子 ++自己的父节点计数; 当父节点收齐 2 个, 由"最后一个
                          到达者"代表父节点继续向上 ++祖父节点 ... 递归到根 (深度 lg P)
        释放 (release): 根置 flag -> 逐层向下把释放信号广播到子节点 (深度 lg P)
        span = 2 * lg(P) 次节点操作;  总流量仍是 O(P) (但分布到 P-1 个节点上, 不集中在 1 个)
        注意: 树形结构在【总线】上无收益(总线本来就是串行的), 在点对点网络(树/环/Mesh)上才赢

2.13 地基：一致性、一致性模型与 fence —— 同步原语为什么必须谈内存序

这一节把配套 CS149 讲义的要点与本讲衔接起来：锁与屏障能工作，前提是”临界区内的读写不会被重排到临界区之外”。

• Cache coherence（缓存一致性）：只约束同一个地址的读写——”所有处理器必须对地址 X 的读写顺序达成一致”，即存在一条把 X 上所有操作串起来的假设时间线（hypothetical serial order），与各处理器的观察一致。MSI/MESI 通过两条不变量保证它：SWMR（Single-Writer, Multiple-Reader） 与 写序列化（write serialization：BusRd/BusRdX 的数据由 M 态缓存提供，总线串行化所有事务）。

• 表 2：MSI 失效协议（invalidate protocol）状态迁移表（A / B = 观察到动作 A 则执行动作 B；-- 表示无总线动作）

• MSI 的已知低效：对”先读一个地址、再写它”这个最常见的模式，MSI 需要两次互连事务（BusRd 进 S，再 BusRdX 升级到 M）——即使程序完全没有共享。于是有了 MESI：增加 E（Exclusive clean，独占但干净） 状态，把”独占性”与”脏”解耦，E → M 的升级不需要任何总线事务。这就是”实现同步原语时，一次 fetch_add 究竟是 2 个事务还是 1 个事务”的差别。

• Memory consistency（内存一致性）：约束不同地址的读写相对顺序（一个线程的访存何时对别的线程可见）。讲义用”四种顺序”刻画：
  • WX→RY（写后读）、RX→RY（读后读）、RX→WY（读后写）、WX→WY（写后写）。
  • 顺序一致性（SC, Sequential Consistency, Lamport 1976）：所有操作按某种全序执行，如同操作单一份共享内存，且每个线程的操作保持程序序——四种顺序全部维持。
  • 松弛（relaxed） 的动机是性能：写要 100 多个周期，而”写 A 与随后读 B 无关”，没必要等写完成。写缓冲（write buffer） 就是硬件在松弛 WX→RY，于是需要更弱的内存模型。
• 表 3：内存一致性模型对比（讲义 slide 44–50）

• 同步原语与 fence 的关系：每种架构都提供同步原语使内存序变严格。Fence（内存屏障，memory barrier） 阻止重排，但昂贵（”它之后的所有访存都必须等它之前的所有访存完成”）。x86 提供 mm_lfence（load fence）、mm_sfence（store fence）、mm_mfence（mem fence）；ARM 的一致性模型非常松弛（这也是 ARM 上 dmb/isb 语义讨论多的原因）。

• 数据竞争与 DRF 契约（本讲最实用的结论）：

  • 冲突访问（conflicting accesses）：两个访问命中同一地址且至少一个写；
  • 非同步程序（unsynchronized program）：冲突访问之间没有同步操作（fence、带 release/acquire 语义的操作、屏障等）排序 ⇒ 程序含数据竞争 ⇒ 结果依赖于处理器的相对速度（不确定）；
  • 已同步程序（synchronized program）：无数据竞争，则即使硬件是弱模型，程序也表现出 SC 的结果（”SC for DRF“）；
  • 现代语言（C11/C++11）与 Java 5 都保证 DRF 程序的顺序一致性，编译器负责插入必要的同步指令来适配硬件模型；程序一旦有数据竞争，则不作任何保证。这解释了为什么我们不手写”裸的共享变量标志”，而要用锁/屏障/atomic——把复杂性封装在库里，是唯一的工程正解。

3. 代码示例与性能分析

三个示例均可独立编译运行。所有示例都使用 release 优化编译（-O3/-O2）：同步基准若不开优化，循环开销会淹没同步代价，结论会失真。

3.1 示例 1：五种自旋锁的完整实现与吞吐量对比

// ============================================================================
// lockbench.cpp —— 五种自旋锁在同一临界区上的吞吐量/延迟对比
// 编译(release): g++ -O3 -std=c++17 -pthread lockbench.cpp -o lockbench
//   (先确认生成代码: g++ -O3 -S lockbench.cpp 或 objdump -d 查看 lock xchg/lock cmpxchg)
// 运行: ./lockbench 16 200000      # 16 线程, 每线程 20 万次"加锁 -> 临界区 -> 解锁"
// ============================================================================
#include <atomic>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <thread>
#include <vector>

static constexpr int CACHE_LINE = 64;

// ---------------- 1) Test-and-Set 锁: 每次尝试都写, 每次都制造一次总线事务 ----------------
struct TASLock {
    alignas(CACHE_LINE) std::atomic<int> v{0};
    void lock() {
        // exchange 在 x86 上编译为 lock xchg, 目标行必须进入 M 态 -> BusRdX + 失效
        while (v.exchange(1, std::memory_order_acquire) != 0) { /* 失败继续抢 */ }
    }
    void unlock() { v.store(0, std::memory_order_release); }
};

// ---------------- 2) Test-and-Test-and-Set: 先在本地副本上只读自旋 ----------------
struct TTASLock {
    alignas(CACHE_LINE) std::atomic<int> v{0};
    void lock() {
        for (;;) {
            // 只读自旋: 命中本核 L1, 互连上零事务(这就是 TTAS 的关键)
            while (v.load(std::memory_order_relaxed) != 0) { }
            // 观察到锁空闲才做原子抢锁
            if (v.exchange(1, std::memory_order_acquire) == 0) return;
        }
    }
    void unlock() { v.store(0, std::memory_order_release); }
};

// ---------------- 3) 指数退避 TAS: 失败后退避, 减少无谓事务 ----------------
struct BackoffLock {
    alignas(CACHE_LINE) std::atomic<int> v{0};
    void lock() {
        int amount = 1;
        for (;;) {
            if (v.exchange(1, std::memory_order_acquire) == 0) return;
            for (volatile int i = 0; i < amount; ++i) { }   // delay(amount)
            if (amount < 4096) amount <<= 1;                // 上限, 避免无限退避
        }
    }
    void unlock() { v.store(0, std::memory_order_release); }
};

// ---------------- 4) Ticket 锁: 取号 + 只读等号, FIFO 公平 ----------------
struct TicketLock {
    alignas(CACHE_LINE) std::atomic<uint32_t> next_ticket{0};
    // 与 next_ticket 分处不同 cache line: 否则每次"取号"都会让所有等待者的只读副本失效
    alignas(CACHE_LINE) std::atomic<uint32_t> now_serving{0};
    void lock() {
        uint32_t my = next_ticket.fetch_add(1, std::memory_order_relaxed);
        while (now_serving.load(std::memory_order_acquire) != my) { }
    }
    void unlock() { now_serving.fetch_add(1, std::memory_order_release); }
};

// ---------------- 5) MCS 队列锁: 每人在自己的节点上自旋, O(1) 流量 + FIFO ----------------
struct MCSLock {
    struct Node {
        alignas(CACHE_LINE) std::atomic<Node*> next{nullptr};
        alignas(CACHE_LINE) std::atomic<bool>  locked{false};   // 独占一行: 唤醒只碰它
    };
    alignas(CACHE_LINE) std::atomic<Node*> tail{nullptr};       // 全局锁 = 队尾指针

    void lock(Node* me) {
        me->next.store(nullptr, std::memory_order_relaxed);
        me->locked.store(true, std::memory_order_relaxed);
        Node* prev = tail.exchange(me, std::memory_order_acq_rel);   // 挂到队尾
        if (prev == nullptr) return;                                  // 队空 -> 直接持有
        prev->next.store(me, std::memory_order_release);              // 让前驱能找到我
        while (me->locked.load(std::memory_order_acquire)) { }        // 自旋在【自己的】节点
    }
    void unlock(Node* me) {
        if (me->next.load(std::memory_order_acquire) == nullptr) {
            // 无人排队: 尝试把 tail 从"我"改成 NULL (cmpxchg 语义, 见讲义 slide 22)
            Node* expected = me;
            if (tail.compare_exchange_strong(expected, nullptr,
                                             std::memory_order_acq_rel)) return;
            // 失败: 有人正在挂入, 等它把 next 指针写出来
            while (me->next.load(std::memory_order_acquire) == nullptr) { }
        }
        // 精确唤醒下一个: 只写它的 locked 字段 (O(1) 互连流量)
        me->next.load(std::memory_order_acquire)->locked.store(false, std::memory_order_release);
    }
};

// MCS 需要每线程一个常驻 node; 用 thread_local 放在线程本地存储里(天然不共享)
struct MCSAdapter {
    MCSLock impl;
    static thread_local MCSLock::Node node;
    void lock()   { impl.lock(&node); }
    void unlock() { impl.unlock(&node); }
};
thread_local MCSLock::Node MCSAdapter::node;

// ---------------- 基准骨架 ----------------
// 临界区: 对一条共享且【已填充】的计数器做一次读-改-写
template <typename Lock>
static void worker(Lock* lk, long long* cs, long long iters, long long* sink) {
    long long acc = 0;
    for (long long i = 0; i < iters; ++i) {
        lk->lock();
        *cs += 1;            // 临界区: 一次共享写 (L1 命中 + 独占写)
        lk->unlock();
        acc += i;            // 临界区外的工作: 只为了让循环不被优化掉
    }
    *sink += acc;
}

template <typename Lock>
static void bench(const char* name, int P, long long iters) {
    static Lock lk;                                        // 每种锁一个实例, 反复复用
    alignas(CACHE_LINE) static long long cells[8 * 64];    // 每个线程 64 B 独占一行
    std::vector<std::thread> th;
    std::vector<long long>   sink(P, 0);
    const long long total = iters * (long long)P;

    auto t0 = std::chrono::steady_clock::now();
    for (int t = 0; t < P; ++t)
        th.emplace_back(worker<Lock>, &lk, &cells[t * 8], iters, &sink[t]);
    for (auto& x : th) x.join();
    auto t1 = std::chrono::steady_clock::now();

    double us = std::chrono::duration<double, std::micro>(t1 - t0).count();
    long long sum = 0;
    for (int t = 0; t < P; ++t) sum += cells[t * 8];
    printf("%-18s P=%2d  交接次数=%10lld  用时=%10.1f us  ns/次交接=%6.1f  M交接/s=%8.2f  (校验 %lld)\n",
           name, P, total, us, us * 1000.0 / (double)total,
           (double)total / us, sum);
}

int main(int argc, char** argv) {
    const int      P     = (argc > 1) ? atoi(argv[1]) : 8;
    const long long iters = (argc > 2) ? atoll(argv[2]) : 200000;
    printf("== 自旋锁对比: %d 线程, 每线程 %lld 次临界区进入 (临界区仅一次共享写) ==\n", P, iters);
    bench<TASLock>    ("TAS",         P, iters);
    bench<TTASLock>   ("TTAS",        P, iters);
    bench<BackoffLock>("Backoff-TAS", P, iters);
    bench<TicketLock> ("Ticket",      P, iters);
    bench<MCSAdapter> ("MCS",         P, iters);
    return 0;
}

【代码做什么？】

1. TASLock：每次循环都执行一次 exchange。无论锁是否空闲，这条指令都要让目标行进入本核独占态——在 x86 上是 lock xchg。这就是讲义里”每个等待者每次测试都产生一次失效”的直接映射。
2. TTASLock：外层无限循环 + 内层只读自旋。内层 load 命中本地缓存副本（S 态），不产生互连事务；一旦看到 0，才 exchange 抢锁；抢失败（说明被别人先抢了）则回到只读自旋。
3. BackoffLock：TAS + 指数退避；for (volatile int i...) 是”廉价 delay”，amount 倍增并设上限，避免退避到永远。
4. TicketLock：fetch_add 取号（一次原子 RMW），然后只读等 now_serving 追上自己的号；unlock 就是 now_serving++——一次写。字段分置不同 cache line，避免”取号时顺带踢掉所有等待者的只读副本”。
5. MCSAdapter：thread_local 节点 + 队列；lock 用 exchange 把自己挂到队尾；若队空直接持有；否则让前驱指向自己并在自己的 node 上自旋。unlock 若发现无人排队则用 compare_exchange_strong 尝试把 tail 置空（对应讲义伪代码里的 CMPXCHG(glock, mlock, NULL)），否则只写下一个等待者的 locked 字段。
6. bench<>()：P 个线程各自进入 iters 次临界区，临界区是”对一条独占 cache line 的计数器加一”，因此临界区本身几乎零成本，测出来的基本就是同步开销（与讲义”把临界区时间扣掉再看曲线”的做法一致）。最后把每个线程的计数器求和打印，用于验证互斥没有坏（结果必须恰好等于 iters × P）。

【并行机制与性能解说】

• 线程与共享数据：P 个 OS 线程，通常被调度到不同核上（-pthread）。共享的是锁对象与一条被填充过的计数器；MCSAdapter::node 是 thread_local，不在线程间共享（这正是 MCS 的要点）。
• Work / Span / 并行度（本讲的第一个硬结论）：设总进入次数 N = iters × P，一次原子操作的成本为 ℓ，一次临界区成本为 c，一次竞争下的锁交接延迟为 h（含互连往返与排队）。
  • Work（总工作量） = N × (ℓ + c)；
  • Span（关键路径） = N × (h + c)：所有 N 次临界区都被互斥强制串行；
  • 并行度 = Work / Span = (ℓ + c) / (h + c)。 取 ℓ = 20 周期（无竞争）、h = 150 周期（P 个线程抢）、c = 30 周期：并行度 = (20+30)/(150+30) ≈ 0.28。并行度 < 1 意味着这不是”加速多少”的问题，而是”比单线程更慢”的问题——加线程只会让交接更贵（h 随 P 增长：TAS 的 h ∝ P，TTAS/Ticket 的 h 也有 O(P) 流量项，MCS 的 h ≈ 常数）。这正是讲义那句”简单 TAS 锁：低竞争低延迟、高流量、扩展性差”的定量表达。
  • 由 Work/Span 得到的可扩展性上限：临界区吞吐量 ≈ 1/(h + c)，与 P 无关。想提高它，只能 (a) 缩短临界区 c（细粒度锁）、(b) 降低交接延迟 h（换 MCS/数组锁）、或 (c) 消除互斥（无锁算法，下一讲）。
• 瓶颈定位：
  • TAS：瓶颈是 互连带宽 + 总线仲裁（失败尝试制造的事务与等待时长成正比）；
  • TTAS：瓶颈是每次释放的惊群（P-1 个 BusRdX + P-1 次重新取数）；
  • Backoff：瓶颈是空窗延迟（锁空闲却没人来拿）与不公平；
  • Ticket：瓶颈是P-1 个读者在每次释放后重新读 now_serving（O(P) 流量），但顺序公平；
  • MCS：流量 O(1)、无惊群，瓶颈转移到内存延迟本身（一次交接 ≈ 一次 cache line 的核间传递 ≈ 65–75 周期 + 端点处理），这也是理论下限。

3.2 示例 2：两种屏障 —— 集中式 sense reversal vs 传播式（dissemination）屏障

// ============================================================================
// barriers.cpp —— 集中式屏障(讲义 slide 27 的 sense reversal) vs O(log P) 屏障
// 编译(release): g++ -O3 -std=c++17 -pthread barriers.cpp -o barriers
// 运行: ./barriers 8 200000     # 8 线程, 每线程 20 万轮 "计算 + 屏障"
// ============================================================================
#include <atomic>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <thread>
#include <vector>

static constexpr int CACHE_LINE = 64;

// ---------------- (a) 集中式屏障 + sense reversal ----------------
// 对应讲义 slide 27: "Sense reversal optimization results in one spin instead of two"
class SenseBarrier {
public:
    explicit SenseBarrier(int P) : P_(P) {}
    void wait(bool& local_sense) {
        local_sense = !local_sense;                                   // 翻转本线程的 sense
        if (cnt_.fetch_add(1, std::memory_order_acq_rel) == P_ - 1) { // 我是最后一个到达者
            cnt_.store(0, std::memory_order_relaxed);                 // 复位计数器(为下一代)
            sense_.store(local_sense, std::memory_order_release);     // 用"翻转"代替"清零"
        } else {
            while (sense_.load(std::memory_order_acquire) != local_sense) { }  // 只自旋一次
        }
    }
private:
    const int P_;
    alignas(CACHE_LINE) std::atomic<int>  cnt_{0};      // 计数器单独一行(被 P 个线程写)
    alignas(CACHE_LINE) std::atomic<bool> sense_{false}; // flag 单独一行(被 P-1 个线程读)
};

// ---------------- (b) 传播式屏障 (dissemination barrier): 无锁, span = O(log P) ----------------
// 讲义 slide 29 讲的是 combining tree(合并树); 这里实现一个同样具有 lg(P) span 的
// 无锁屏障, 用来定量对比"O(P) span vs O(log P) span"。要求 P 为 2 的幂。
class DissemBarrier {
public:
    explicit DissemBarrier(int P) : P_(P), logP_(0) {
        while ((1 << logP_) < P_) ++logP_;              // P 向上取整到 2 的幂
        flags_.resize(P_);
        for (auto& row : flags_) {
            row = std::vector<std::atomic<unsigned>>(logP_);
            for (auto& f : row) f.store(0, std::memory_order_relaxed);
        }
    }
    // 必须由同一个线程反复调用; rnd 是该线程私有的"屏障轮次"(从 0 开始, 每轮 +1)
    void wait(int t, unsigned& rnd) {
        ++rnd;                                           // 单调递增的轮次号, 避免 ABA
        for (int r = 0; r < logP_; ++r) {
            const int partner = (t + (1 << r)) % P_;      // 我通知"后面第 2^r 个"
            flags_[partner][r].store(rnd, std::memory_order_release);
            // 我等"前面第 2^r 个"通知我: 它写的正是 flags_[t][r]
            while (flags_[t][r].load(std::memory_order_acquire) != rnd) { }
        }
    }
private:
    int P_, logP_;
    std::vector<std::vector<std::atomic<unsigned>>> flags_;   // flags_[目标线程][轮次]
};

// 两个屏障统一成 wait(tid) 接口(thread_local 保存每线程私有状态)
struct SenseAdapter {
    SenseBarrier impl;
    static thread_local bool sense;
    explicit SenseAdapter(int P) : impl(P) {}
    void wait(int) { impl.wait(sense); }
};
thread_local bool SenseAdapter::sense = false;   // 初值 false -> 第 1 次屏障等的值是 1

struct DissemAdapter {
    DissemBarrier impl;
    static thread_local unsigned rnd;
    explicit DissemAdapter(int P) : impl(P) {}
    void wait(int tid) { impl.wait(tid, rnd); }
};
thread_local unsigned DissemAdapter::rnd = 0;

// ---------------- 基准: K 个 "计算阶段 + 屏障" ----------------
template <typename Barrier>
static void bench_barrier(const char* name, int P, long long phases) {
    Barrier bar(P);
    std::vector<std::thread> th;
    std::vector<long long>   acc(P, 0);

    auto t0 = std::chrono::steady_clock::now();
    for (int t = 0; t < P; ++t) {
        th.emplace_back([&bar, t, phases, &acc] {
            long long a = 0;
            for (long long k = 0; k < phases; ++k) {
                for (int i = 0; i < 200; ++i) a += (i ^ t);   // 模拟该阶段的并行计算
                bar.wait(t);                                  // 阶段边界: 屏障
            }
            acc[t] = a;
        });
    }
    for (auto& x : th) x.join();
    auto t1 = std::chrono::steady_clock::now();

    double us = std::chrono::duration<double, std::micro>(t1 - t0).count();
    long long chk = 0; for (auto v : acc) chk += v;
    printf("%-22s P=%2d  阶段数=%8lld  总用时=%10.1f us  ns/屏障=%8.1f  (校验 %lld)\n",
           name, P, phases, us, us * 1000.0 / (double)phases, chk);
}

int main(int argc, char** argv) {
    const int       P      = (argc > 1) ? atoi(argv[1]) : 8;
    const long long phases = (argc > 2) ? atoll(argv[2]) : 200000;
    printf("== 屏障对比: %d 线程 (必须为 2 的幂), 每线程 %lld 个阶段 ==\n", P, phases);
    bench_barrier<SenseAdapter> ("SenseReversal", P, phases);
    bench_barrier<DissemAdapter>("Dissemination", P, phases);
    return 0;
}

【代码做什么？】

1. SenseBarrier::wait：先把每线程私有的 local_sense 翻转；再用一次原子 fetch_add 判断自己是不是最后一个到达者。是 → 复位计数器并把 sense_ 置为本代的值（“翻转”而不是”清零”，因此不需要等价于 leave_counter 的第二轮自旋）；不是 → 自旋等待 sense_ 变成自己这一代的值。
2. DissemBarrier::wait：共 log2(P) 轮。第 r 轮中，线程 t 通知 (t + 2^r) mod P，并等待 (t - 2^r) mod P 的通知（表现上就是”等 flags_[t][r] 变成本轮轮次号”）。因为每轮让线程知道的”已到达者集合”翻倍，log2(P) 轮后每个线程都知道全体已到达。用单调递增的轮次号 rnd 而非 0/1，天然规避”快线程领先一代导致误读”的 ABA 问题。
3. bench_barrier：每轮先做一小段纯计算（200 次异或累加，代表阶段内的并行工作 T_c），然后调用屏障；统计总时间与”每次屏障的纳秒数”。两个适配器用 thread_local 持有每线程私有状态（sense / 轮次号），这正是讲义强调的”local_sense 必须是每处理器私有的“。

【并行机制与性能解说】

• 线程与数据布局：P 个线程；SenseBarrier 的 cnt_ 与 sense_ 各自独占 cache line（防止”每次计数更新都踢掉所有等待者的 flag 只读副本”，即讲义 slide 25 的那个反问）；DissemBarrier 的每个 flag 位置只被”一个写者 + 一个读者”访问，天生无伪共享。
• Work / Span / 并行度：设每阶段并行计算量为 T_c，屏障的临界路径长度为 T_b，阶段数 K：
  • Work = K × (T_c + W_b)，其中 W_b 是屏障的总工作量：集中式 W_b = Θ(P)（每个线程一次原子加 + 若干读），传播式 W_b = Θ(P log P)（P 个线程 × log P 次写 + log P 次读）。
  • Span = K × (T_c/P + S_b)，其中 S_b（屏障的关键路径）：集中式 = Θ(P)（所有线程在同一个原子变量上排队，P 次原子 RMW 串行 + flag 广播的 O(P) 流量）；传播式 = Θ(log P)（log P 轮，每轮一次 release 存 + 一次 acquire 读，互不依赖、可全并行）。
  • 并行度 = Work / Span：集中式 ≈ (T_c + Θ(P)) / (T_c/P + Θ(P)) → 当 P 增大时趋近 O(1)（”屏障期间整机空转”）；传播式 ≈ Θ(P log P) / Θ(log P) = Θ(P)（屏障本身也并行）。
• 瓶颈与可扩展性上限（定量结论）：屏障把速度上限钉死在 T_c / T_b 附近： 设 T_c = 10,000 周期（每阶段并行工作量）、P = 64、每次”竞争下的原子 RMW + 排队”约 200 周期：
  • 集中式：S_b ≈ P × 200 = 12,800 周期 → 单阶段时间 = 10,000/64 + 12,800 ≈ 12,956 周期 → 加速比 = 10,000 / 12,956 ≈ 0.77（比单线程还慢！）
  • 合并树（讲义方案，span = 2·lg P·L_node）：S_b ≈ 2 × 6 × 200 = 2,400 → 单阶段 = 156 + 2,400 = 2,556 → 加速比 ≈ 3.9×
  • 传播式：S_b ≈ log2(64) × (75 + 75) = 900 → 单阶段 = 156 + 900 = 1,056 → 加速比 ≈ 9.5×
  • 理论上限（无屏障）：64× → 结论：屏障开销把可扩展性上限压到 T_c/T_b（大 P 时加速比 ≈ T_c/T_b），因此减少屏障次数、让每次屏障之间”干活足够多”比任何微优化都重要。这与讲义”集中式屏障 span 是 O(P)，合并树是 lg(P)”的定性结论完全一致；同时注意讲义的限制条件：在总线上树形结构帮助有限（总线本身把 O(P) 流量串行化了，树只是把竞争点从 1 个变量分散到 P-1 个变量，总线上仍要排队），只有在点对点互连上才能把 lg(P) 的 span 变成真实收益。

3.3 示例 3：伪共享（false sharing）—— 一致性协议写给软件的最贵账单

// ============================================================================
// falsesharing.cpp —— 伪共享的实测: 未填充 vs 已填充 (结构取自 CS149 讲义 slide 17)
// 编译(release): g++ -O2 -std=c++17 -pthread falsesharing.cpp -o falsesharing
// 运行: ./falsesharing 8 40000000     # 8 线程, 每线程 4000 万次自增
// 说明: CS149 讲义在 4 核机器上、8 线程、同一份测试下实测 14.2 s vs 4.7 s
// ============================================================================
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <pthread.h>

static constexpr int CACHE_LINE_SIZE = 64;
static constexpr int MAX_THREADS     = 64;
static long MANY_ITERATIONS = 40000000;   // 由命令行覆盖

// 每个线程一个计数器, 并把它填满到独占一条 cache line
struct padded_t {
    int  counter;
    char padding[CACHE_LINE_SIZE - sizeof(int)];
};

// 工作线程: 反复自增【只属于自己】的计数器
static void* worker(void* arg) {
    volatile int* counter = (int*)arg;      // volatile: 强制每次都真的读写内存
    for (long i = 0; i < MANY_ITERATIONS; i++)
        (*counter)++;
    return NULL;
}

// ---- 版本 1: 未填充。相邻计数器落在同一条 cache line ⇒ 伪共享 ----
static double test1(int num_threads) {
    pthread_t threads[MAX_THREADS];
    int       counter[MAX_THREADS];
    for (int i = 0; i < num_threads; i++) counter[i] = 0;

    auto t0 = std::chrono::steady_clock::now();
    for (int i = 0; i < num_threads; i++)
        pthread_create(&threads[i], NULL, &worker, &counter[i]);
    for (int i = 0; i < num_threads; i++)
        pthread_join(threads[i], NULL);
    auto t1 = std::chrono::steady_clock::now();

    long long sum = 0; for (int i = 0; i < num_threads; i++) sum += counter[i];
    double s = std::chrono::duration<double>(t1 - t0).count();
    printf("未填充(sizeof(int)=%zu B, 8 个计数器共用 1 条 64 B 行): %8.3f s  (总和=%lld)\n",
           sizeof(int), s, sum);
    return s;
}

// ---- 版本 2: 已填充。每个计数器独占一条 cache line ⇒ 无伪共享 ----
static double test2(int num_threads) {
    pthread_t threads[MAX_THREADS];
    padded_t  counter[MAX_THREADS];
    for (int i = 0; i < num_threads; i++) counter[i].counter = 0;

    auto t0 = std::chrono::steady_clock::now();
    for (int i = 0; i < num_threads; i++)
        pthread_create(&threads[i], NULL, &worker, &(counter[i].counter));
    for (int i = 0; i < num_threads; i++)
        pthread_join(threads[i], NULL);
    auto t1 = std::chrono::steady_clock::now();

    long long sum = 0; for (int i = 0; i < num_threads; i++) sum += counter[i].counter;
    double s = std::chrono::duration<double>(t1 - t0).count();
    printf("已填充(每个计数器独占 1 条 64 B 行):                  %8.3f s  (总和=%lld)\n",
           s, sum);
    return s;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 8;
    if (argc > 2) MANY_ITERATIONS = atol(argv[2]);
    printf("== 伪共享实测: %d 线程, 每线程 %ld 次 volatile 自增 ==\n", n, MANY_ITERATIONS);
    double s1 = test1(n);
    double s2 = test2(n);
    printf("--> 未填充/已填充 = %.2fx\n", s1 / s2);
    return 0;
}

【代码做什么？】 两个版本工作线程完全相同：每个线程对自己的 int 做 MANY_ITERATIONS 次 volatile 自增。唯一差别是布局：版本 1 里 8 个 int 紧挨着（8 个计数器共享一条 64 B cache line）；版本 2 里每个计数器用 char padding[60] 撑满一条 cache line。打印总和用于验证结果正确（两者都应等于 线程数 × MANY_ITERATIONS）。

【并行机制与性能解说】

• 为什么”没有共享却跑了通信”：一致性协议的粒度是 cache line，不是变量。版本 1 中 P1 写 counter[1] 与 P2 写 counter[2] 落在同一条行上：P1 要写，必须先 BusRdX 把行独占并让 P2 的副本失效；P2 要写，又得把行抢回去。行在两个核之间来回弹跳（ping-pong），每次弹跳 ≈ 75 周期（”L3 命中、行在另一个核里是 modified”），而这完全不是算法需要的数据通信——讲义称之为 artifactual communication（人为通信），根因是 cache line（64 B）远大于被访问的数据（4 B）。
• Work / Span / 并行度：
  • Work = P × N 次自增（N = MANY_ITERATIONS），这是真并行的工作量；
  • 理想 Span（各线程完全独立）= N 次自增（一条 chain）→ 并行度 = P；
  • 伪共享下的实际 Span：每次 cache line 所有权转移会串行化互连上的写。若最坏情况下每次转移只允许一个自增发生（对手立刻把行抢走），则 Span ≈ P × N × (T_transfer)，并行度退化为 ≈ 1——与”加了一把锁”没有区别。这就是伪共享最危险的地方：程序里没有任何锁，性能却像全程串行。
  • 定量核对（用 AMAT 模型反推）：AMAT = Σ(访问频率 × 访问延迟)。
    • 已填充版本：全部命中本地 L1（~4–5 周期），AMAT ≈ 5 周期；
    • 未填充版本：设”跨越互连取行”的比例为 f，AMAT ≈ (1-f)×5 + f×75。
    • 讲义实测比值为 14.2 / 4.7 = 3.02×。令 AMAT 之比等于 3.02：[(1-f)·5 + 75f] / 5 = 3.02 ⇒ 5 + 70f = 15.1 ⇒ f ≈ 0.144。
    • 即：约 14% 的访问变成了跨核行转移，就足以让程序慢 3 倍。若按”每次自增都跨核”的极端模型（f = 1），比值会达到 75/5 = 15×——实测只有 3×，说明同一线程连续自增会在一段时间内独占该行（自增之间的循环开销、store buffer 合并、以及 SMT 使 8 个线程实际分布在 4 个物理核的 4 个 L1 上，都降低了真实转移频率）。这个”模型高估、实测更小”的差距本身很有教学价值：伪共享的伤害取决于”行在核间转移的频率”，而不是”有多少线程共享了这条行”。
• 瓶颈：互连带宽 + 行转移延迟；不均衡：8 线程抢 4 个 L1，某些核承担双倍流量；修复手段：填充（padding，本示例）、每个线程写入真私有的局部变量（回归时才合并，即 reduction 模式）、调整数据布局（SoA 中的分块、每个线程一块 block_size ≥ cache line 的区间）。

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

4.1 三个必须同时写的”预算约束”

同步原语的性能从来不是单一指标。工程上必须同时盯住三条预算：

1. 延迟预算（latency budget）：一次 acquire 在无竞争下的关键路径 = 一次原子 RMW 的互连往返（~65–75 周期，行被他人共享/持有时更贵）；
2. 带宽预算（bandwidth budget）：一次同步事件在互连上搬运多少字节。设互连等效数据带宽 B_bus = 8 B/cycle，则一条 64 B cache line = 8 个互连周期的占用；若某算法每次交接要搬 m 条行，则每次交接占用 8m 个互连周期；
3. 串行化预算（serialization budget）：所有线程是否在同一地址上排队？如果是，span 就是 O(P)，与流量无关（讲义 slide 28 的核心）。

4.2 表 4：锁算法的定量对比（参数为示意值，趋势比绝对值重要）

共同假设：P = 16 个线程全部争抢同一把锁；B_bus = 8 B/cycle（等效，64 B 行 = 8 周期）；一次失败 TAS 的往返（含排队）R_eff；临界区持锁时长 H = 400 周期；一次”行转移”提供 64 B。

读法：这张表把讲义的定性结论变成了同一把尺子上的数字。三个关键洞察：

1. TAS 的问题不是”每次多花几个周期”，而是”流量与等待时长成正比”（96% 的互连流量是失败的尝试）；这解释了为什么讲义 slide 13 的曲线随 P 陡增；
2. TTAS 把”持续尝试”变成”每次释放尝试一次”，流量降一个数量级，但仍是 O(P)/次释放；
3. 要把 O(P)/次释放 变成 O(1)，必须让等待者不共享同一个地址（数组锁：不同槽位；MCS：不同节点）。这时交接的互连代价降到”一条 cache line”，即 ≈ 8 个互连周期 ≈ 理论下限。

4.3 数值算例 A：16 线程下三种锁的临界区吞吐量上限

设总线数据带宽等效 B = 8 B/cycle、时钟 1.6 GHz、临界区 H = 400 周期（= 250 ns）：

结论：在”临界区 250 ns”这个尺度上，TAS 把有效吞吐砍到理想值的 49%，TTAS 61%，Ticket 74%，MCS 84%。注意 P 增大时 TAS 会继续恶化（流量 O(P²)），而 MCS 的 h 基本不随 P 变——这就是”可扩展性”的具体含义：不是”现在快多少”，而是”P 翻倍后还剩下多少”。

4.4 数值算例 B：屏障开销如何给加速比设上限（Amdahl 视角）

设程序分为 K 个阶段，每阶段并行工作量 T_c 周期，阶段间必须同步，屏障的关键路径 T_b：

T(P, K) = K · ( T_c / P + T_b )
Speedup(P) = (K · T_c) / (K · (T_c/P + T_b)) = 1 / (1/P + T_b/T_c)
                ─────────────────────────────────────────────
P → ∞ 时:  Speedup_max = T_c / T_b        <-- 屏障给加速比设的硬上限

取 T_c = 10,000 周期、P = 64、单次”竞争下原子操作 + 排队” 200 周期：

结论：T_c = 10,000 周期在 1.6 GHz 下只有 6.25 µs。这意味着只要阶段之间的计算少于约 6 µs，集中式屏障就会让 64 核机器比单核更慢。提高方式只有两条：(a) 增大 T_c（把更多工作塞进两个屏障之间：批处理、blocking、tiling）；(b) 降低 T_b（换 O(log P) 的屏障，并把屏障放到点对点互连上）。

4.5 数值算例 C：一次 fetch_add 的延迟预算分解

用配套讲义给出的延迟表做预算分解（Core i7 Xeon 5500 量级），一次 ticket 锁的 acquire：

算例：acquire 的原子 RMW 命中”行在别的核被修改”这一栏 → ≈75 周期 ≈ 47 ns @1.6 GHz；release 的写使 15 个等待者失效，每个等待者重新取行 ≈75 周期。因此一次”完美实现的”锁交接的最低下界 ≈ 150 周期 ≈ 94 ns——这就是 MCS 的实测交接延迟与”再多优化也降不下去”的物理原因（注意：这是延迟下界，不是吞吐限制；吞吐还受互连带宽约束）。若临界区只有 50 ns，那么锁交接本身就是临界区的两倍——这正是讲义强调”低延迟”与”低流量”必须同时满足的现实含义。

4.6 用 Roofline / 算术强度看同步

同步代码的算术强度（arithmetic intensity, AI）= 浮点/整数运算数 ÷ 访存字节数极低：一次 fetch_add 是”1 次操作 / 一条 cache line（64 B）”，AI ≈ 0.016 op/B。在 Roofline 模型里这意味着它永远落在带宽斜坡的最左端：性能 = AI × B_bus，与峰值算力无关。这是”同步是纯开销”的定量表述：16 核 × 3.0 GHz × 8 宽 SIMD × 2（FMA）= 768 GFLOPS 的峰值算力，在同步指令上一点也用不到——同步只消耗互连带宽与延迟。同理，一个 256 MB 数组在 20 GB/s 带宽下单次遍历至少要 12.8 ms，而一次锁交接（~100 ns）相比微不足道；但当每次访问一个元素就要同步一次时（如 lock; a[i]++; unlock;），吞吐被同步而非带宽锁死：20 GB/s / 64 B ≈ 312 M 行/s 的带宽预算完全用不上，实际被 1/(h+c) 限制在几 M/s——相差两个数量级。这条对比是”批处理 / 减少同步次数”最有力的论据。

5. 关键要点

1. 把同步事件拆成 acquire / waiting / release 三阶段再看性能。锁的灾难几乎总在某一阶段高度集中：TAS 死在 waiting（持续制造总线事务）、ticket/数组/MCS 分别优化 acquire 的原子操作、waiting 的地址隔离、release 的唤醒粒度。优化前先定位是哪一段在花钱。
2. 同步的性能尺度是”互连流量与串行化”，不是”指令数”。判据只有两条：(i) 每次同步事件在互连上搬几条 cache line（O(1) / O(P) / O(P²)）？(ii) 线程是否在同一个地址上排队（若是，span = O(P)，与流量无关）？MCS 同时打赢这两条：O(1) 流量 + 每个等待者独立地址 + FIFO 公平。
3. 原子 RMW（TAS/CAS/fetch-add）是正确性的必要条件，不是性能的解决方案。load-test-store 必然错；但”用 TAS 实现一切”必然不扩展。正确做法是用最便宜的原子原语 + 最少的共享地址：取号用 fetch_add，升级用 cmpxchg，等待用只读自旋。
4. 屏障（以及一切全局同步）给加速比设了一个硬上限 T_c/T_b。集中式屏障 span = O(P)，合并树/传播式 = O(log P)（但树形只在点对点互连上兑现收益，总线上流量仍被串行化）。工程上第一优先级永远是增大两次同步之间的工作量，其次才是换 O(log P) 的屏障。
5. 伪共享是”没有共享的通信”——它把”每线程独立写”变成互连上的 cache line 弹跳，可以让并行度退化为 1。同步数据结构（锁字、屏障计数器、每线程计数器）必须各自独占 cache line（alignas(64) / padding），并且要在实现里就做对，而不是等 profiling 发现。

6. 常见陷阱与注意事项

• 用 load + store 手写锁或标志位：LOAD-TEST-STORE 不是原子的（讲义 slide 8 的反例），P0/P1 会同时认为自己持有锁。任何”先检查再写入”的互斥逻辑，都必须由单条原子 RMW（TAS/CAS/fetch_add）完成。同理，while (flag == 0); 这样的裸自旋在没有 atomic/volatile+fence 保证时，可能被编译器优化成死循环（或读被提升到循环外）。
• 忽略内存序，以为”原子 = 万事大吉”：默认的 memory_order_seq_cst 最安全但最贵；反过来，把 relaxed 用在发布/订阅模式上（例如 data = x; flag = 1; 全用 relaxed）会让消费者看到 flag 却看不到 data。规则：写方用 release 发布，读方用 acquire 获取；只有在纯计数（如 fetch_add(1, relaxed) 取号）时才可用 relaxed。这就是 §2.13 的 DRF 契约：程序无数据竞争，硬件模型再弱也呈现 SC；一旦有竞争，则毫无保证。
• 伪共享（false sharing）：两个线程写不同变量但落在同一条 64 B cache line（如 int counter[NUM_THREADS]、相邻的锁字、屏障的 counter 与 flag 同行）→ 行的所有权在两个核之间 ping-pong。修复：填充到 cache line、每线程私有局部变量后再合并、按块划分数据（块 ≥ 一行）。实测教训：约 14% 的访问跨核转移就足以让程序慢 3 倍（§3.3）。
• 把”自旋”当万能药：自旋只在”不超售 + 预期等待时间 < 上下文切换开销”时划算；在超售环境（线程数 > 核数、或同机跑多个 CPU 密集程序）里，自旋会抢走持锁线程的 CPU，形成”自旋者越多、持锁者越慢、锁越难释放”的活锁式退化。混合策略（短暂自旋后 sched_yield/futex 阻塞）才是工程解。
• 忽略公平性 ⇒ 饥饿（starvation）：TAS/TTAS 无公平性；指数退避更糟——新来者退避间隔更短，可能反复插队（讲义 slide 19）。需要 FIFO 语义时必须选 ticket / 数组 / MCS 锁。反过来，不要以为 FIFO 一定更快：ticket 锁的 FIFO 是免费的，但它的等待者在同一行上自旋，每次释放仍有 O(P) 流量。
• 屏障的两个经典错误：(1) 用”朴素共享计数器 + flag”实现可复用的屏障——快线程冲到下一次屏障清掉 flag，慢线程永远等不到（讲义 slide 25/26 的核心问题），必须用 sense reversal 或 leave_counter 做代际隔离；(2) 忘记 local_sense/轮次号必须是每线程私有（放在共享结构里就退化成又一个被争用的变量）。此外，所有线程必须执行相同次数的屏障，否则最弱的模型也救不了——这是结构性要求，不是性能问题。
• 只看平均延迟、不看尾延迟（tail latency）：锁交接的延迟分布在竞争下长尾极重（排队 + 互连重试）。用”平均 ns/次”评估锁会系统性低估真实伤害；评估同步原语时应看 p99/p999 与吞吐量两条曲线，而不是单点平均值。
• 在总线上迷信树形/分层算法的收益：合并树把竞争点从 1 个分散到 P-1 个，span 降到 O(log P)，但总流量仍是 O(P)；总线本身串行，收益有限（讲义 slide 29 明确提醒）。算法优化必须匹配互连拓扑。

7. 思考题（带答案）

思考题 1（TAS vs TTAS 的流量核算）

8 个线程争抢同一把 TAS 锁，锁的行被所有等待者缓存。一次失败 TAS 的往返（含排队）为 60 周期，临界区持锁时长 H = 300 周期，总线等效带宽 B = 8 B/cycle（64 B 行 = 8 周期）。

(a) 一次锁交接，等待者一共发起多少次失败的 TAS？互连上搬了多少字节？等效占用多少总线周期？ (b) 换成 TTAS 后，一次交接的流量量级变成多少？给出估算并说明与 (a) 的差距从何而来。 (c) 如果 P 从 8 增到 32，两种锁的流量各自怎么变？

【答案】 (a) TAS：7 个等待者，每个等待者大约每 60 周期发一次 TAS，因此在 H = 300 周期的持锁窗口内，每个等待者做 300/60 = 5 次失败尝试 → 失败次数 = 7 × 5 = 35 次。每次失败的 TAS 需要一次 BusRdX（拿到独占行并发失效），即一次 64 B 的行传输：35 × 64 = 2240 B；再加上 1 次成功的 TAS（64 B）和持有者 unlock 时重新抢回行写 0（64 B，因为行已被等待者抢走），合计约 2368 B ≈ 37 条行事务 ≈ 296 个总线周期。注意这个数大于临界区本身的一半——纯粹浪费。 (b) TTAS：等待者在本地只读副本上自旋（零互连事务），只在观察到释放后才尝试。所以每次交接的失败 TAS 从 35 次降到”每个等待者 1 次”：7 次抢锁尝试（7 × 64 = 448 B）+ 6 个失败者重新取回行继续自旋（6 × 64 = 384 B）+ 释放时 7 次失效消息（每条约 8 B，56 B）≈ 888 B ≈ 14 条行事务 ≈ 112 个总线周期。差距来自根本机制的改变：TAS 的尝试频率与”等待时长”成正比（持续尝试），TTAS 的尝试频率与”释放次数”成正比（每次释放一次）——等待越久，TAS 越亏。 (c) P = 32（31 个等待者，其余不变）：

• TAS：每个等待者仍做 5 次 → 31 × 5 = 155 次失败 → 155 × 64 ≈ 9920 B。流量与 P 近似线性增长（O(P) 每次交接），而每次交接的等待时长随流量继续增长，形成正反馈 → 整体约 O(P²)。这正是讲义幻灯片上随 P 陡升的曲线。
• TTAS：失败尝试仍为”每个等待者 1 次”→ 31 × 64 = 1984 B 抢锁 + 30 × 64 = 1920 B 重取 ≈ 3.9 KB。仍是 O(P)，但系数只有 TAS 的约 1/2.5，且不随等待时长放大。结论：TTAS 并没有消除 O(P)，它只是把”P 越大越糟”从”P × 等待时长”降为”P × 1 次释放”——真正的 O(1) 需要 MCS/数组锁。

思考题 2（屏障的 span 与加速比上限）

某程序有 K = 1,000 个阶段，每阶段并行计算量 T_c = 20,000 周期，阶段之间用屏障同步。机器有 P = 64 核，1.6 GHz；集中式屏障的每次到达/离开在竞争下约 200 周期。 (a) 用 Speedup = 1/(1/P + T_b/T_c) 估算集中式屏障下的加速比；此时机器有多少时间在空转？ (b) 换成 span 为 2·lg(P) 的合并树屏障（每节点操作仍是 200 周期），加速比变多少？ (c) 若把每阶段的计算量降到 T_c = 2,000 周期（屏障次数不变），结论如何变化？给出一条工程建议。

【答案】 (a) T_b(集中式) ≈ P × 200 = 64 × 200 = 12,800 周期。Speedup = 1/(1/64 + 12,800/20,000) = 1/(0.015625 + 0.64) = 1/0.6556 ≈ 1.53×。单阶段时间 = 20,000/64 + 12,800 = 312 + 12,800 = 13,112 周期，其中屏障占 97.6%，即 64 核中有约 62.5 核的算力在屏障期间闲置。加速比上限 T_c/T_b = 20,000/12,800 ≈ 1.56×，与上面的结果吻合。 (b) T_b(树) = 2 × lg(64) × 200 = 2 × 6 × 200 = 2,400 周期 → Speedup = 1/(0.015625 + 2,400/20,000) = 1/(0.015625 + 0.12) = 1/0.1356 ≈ 7.4×。用 O(log P) 的屏障把加速比从 1.5× 提到 7.4×（约 4.8 倍），但距 64× 仍差得远——瓶颈已经从”屏障”转移到”并行计算只占 312 周期，而屏障仍要 2,400 周期”。 (c) T_c = 2,000 时：集中式 Speedup = 1/(0.015625 + 12,800/2,000) = 1/(0.015625 + 6.4) ≈ 0.156×（比单线程慢 6 倍以上）；合并树 = 1/(0.015625 + 1.2) ≈ 0.82×（仍然负加速）。结论：当单阶段计算量低于屏障开销时，无论屏障实现多好，加核都会变慢。工程建议：先做”粗化（coarsening）”——把多个小阶段合并成一个大阶段、对循环分块、把每个线程的私有结果累积起来再同步，把 T_c/T_b 抬到 10 以上（例如 T_c ≥ 24,000 周期，约 15 µs），再考虑屏障算法本身的优化。此外还应减少屏障次数（K 从 1000 降到 100），因为墙钟时间 = K × (T_c/P + T_b)。

思考题 3（伪共享的诊断与修复）

一个 OpenMP 归约程序在 8 核上跑得比单线程还慢。profile 显示 L1 命中率很高，但互连流量异常大，且 perf 报出大量 “HITM”（命中他人修改过的行）事件。代码片段如下：

double sum[NUM_THREADS];                  // 全局数组, 每线程写 sum[tid]
#pragma omp parallel for
for (int i = 0; i < N; i++) {
    int tid = omp_get_thread_num();
    sum[tid] += a[i];
}

(a) 这是什么问题？为什么”每个线程只写自己的元素”仍然会有通信？ (b) 给出两种修复方案，并说明哪一种更好。 (c) 为什么 double 数组比 int 数组在这种场景下”稍微好一点”，但并没有解决问题？

【答案】 (a) 伪共享（false sharing）。sum[NUM_THREADS] 是 double，8 个元素共 64 B，恰好整条 cache line。虽然每个线程只写自己的元素（没有真共享 true sharing），但一致性协议的粒度为 cache line：线程 0 写 sum[0] 必须独占整行并让其他核的副本失效，线程 1 立刻再抢回该行……整行在两个/多个核之间 ping-pong。perf 的 HITM 事件正是”我请求的行在别的核里是 modified 状态，必须由它提供数据”的证据——这是纯粹的人为通信（artifactual communication）。L1 命中率高并不矛盾：命中的是别的行，而这一行的每次访问都在跨核迁移。 (b) 两种修复：

1. 填充（padding）：让每个线程的累加器独占一条 cache line：

   struct Padded { double v; char pad[64 - sizeof(double)]; } sum[NUM_THREADS];
   // 或 C11/C++17: struct alignas(64) Padded { double v; };
   

2. 私有累加 + 阶段合并（reduction）：每个线程在自己的局部变量（寄存器/栈）里累加一整块数据，只在最后合并一次：

   #pragma omp parallel
   { double local = 0;
     #pragma omp for
     for (int i = 0; i < N; i++) local += a[i];
     #pragma omp critical
     sum_global += local;      // 或 #pragma omp atomic
   }
   

   方案 2 更好：它把跨核通信从”每次迭代一次”降到”每线程一次”，总流量从 O(N) 降到 O(P)；而且它天然规避了伪共享（局部变量在寄存器/私有栈上）。方案 1 只是把问题”挡住”（每行独立，但仍是每线程每迭代一次 cache line 的读写，只是不再迁移）——它比原来快得多，但没有消除”每迭代一次共享内存写”这个根本成本。二者应结合：先做私有累加，跨线程汇总处再用填充/critical。 (c) 因为 cache line 是 64 B：double（8 B）时 8 个元素刚好占满一条线，8 个线程争 1 条线；int（4 B）时一条线里有 16 个元素，争用者更多、每线程的”有效产量/行”更低，同样的行迁移次数分摊到更少的有效数据上，相对损失更大。但”稍微好一点”不等于解决问题：只要多个线程写同一条 cache line 的不同字节，就会发生伪共享——判据是”是否落在同一行”，与数据类型或元素个数无关（CS149 讲义的定义：两个处理器写不同地址，但地址映射到同一 cache line）。