无锁编程与内存序

非阻塞算法的进展保证（卷 I 4.9）

按保证由弱到强：

「无锁编程」常被宽泛地指任何不阻塞的算法，严格的统称是非阻塞算法 (non-blocking algorithm)，这仍是开放的研究领域。

数据竞争的三个来源（卷 I 4.9.1）

1. 一个关键操作被同一对象的另一个关键操作打断（抢占或多核）；
2. 编译器的指令重排优化与 CPU 的乱序执行（只保证单线程可观察行为不变，见 并发与并行基础）；
3. 内存控制器的激进优化使读写效果相对延迟，书中称为内存序 bug (memory ordering bug)。

要保证原子性，三者都必须排除。

实现原子性（卷 I 4.9.2）

• 关中断（x86 cli）只影响执行它的那个核，只在单核抢占式系统有效，实用性有限。
• 原子读写：多数 CPU 上 4 字节对齐的 32 位整数读写是原子的；有的 CPU 对按自身大小对齐的字节或 64 位整数也是。原因是不超过寄存器宽度（有时是缓存行宽度）的对齐访问在一个内存周期内完成，而时钟驱动的内存周期不可打断，连其他核也打断不了。未对齐访问通常由两次对齐访问拼成，不能假定原子（对齐见 C++ 内存布局与对齐）。依赖前务必查 ISA 文档。
• 原子读-改-写 (RMW)：实现互斥锁必需。x86 的 lock 前缀能让几乎任何指令原子执行。

原书问题（4.9.2.6）：(1) 书中称 Windows SDK 的 InterlockedExchange 等无下划线函数「涉及内核调用、贵得多」。据 Microsoft Learn 的 InterlockedExchange 等页面，这些函数在可能时就是用编译器内建函数实现的（winnt.h 中直接映射到 _InterlockedExchange 等），在用户态执行一条带 lock 语义的指令，并不进入内核；二者开销基本相同。(2) 示例 _InterlockedExchange8(old, pLock); 参数顺序和用法不对：原型是 char _InterlockedExchange8(char volatile* Target, char Value)，返回旧值，应写成 old = _InterlockedExchange8((char volatile*)pLock, 1);。另外书中 TAS/XCHG/CAS 自旋锁示例本身都声明为「缺少内存栅栏、仅作示意」，完整版本见 4.9.7。

• CAS 实现自旋锁的示例把锁值设为 -1（0xFFFFFFFF），while (!_cas(pValue, 0, kLockValue)) PAUSE();；原子自增则是「读旧值 → +1 → CAS，失败重试」。
• ABA 问题：CAS 读到 A，提交前另一线程先写 B 再写回 A，CAS 无法察觉发生过竞争。
• LL/SC 相对 CAS 的优点：不受 ABA 影响；更适合流水线——CAS 需要两个访存阶段（读比较、写），LL 与 SC 各只需一个。
• 强/弱 compare-exchange：C++11 的 compare-exchange 在不同硬件上可能由 CAS 或 LL/SC 实现；strong 版本对程序员隐藏 SC 的虚假失败，weak 版本不隐藏（理由见 Lawrence Crowl 的论文）。
• 相对强度：在多线程共识 (consensus) 问题上，TAS 只操作布尔值，只能解决两个线程的无等待共识；CAS 操作 32 位值，能解决任意多线程的共识。这主要与容错系统相关。

屏障：防止指令重排（卷 I 4.9.3）

• 例：生产者 g_data = 42; g_ready = 1;，消费者 while (!g_ready) PAUSE(); ASSERT(g_data == 42);。即便 32 位读写都是原子的，编译器或 CPU 也可能把 g_ready = 1 提到 g_data = 42 之前；理论上编译器还可能把消费者对 g_data == 42 的检查提到 while 循环之前。重排发生在汇编层面，例如 A = B + 1; B = 0; 可被重排为先写 B 再写 A（例子来自 Jeff Preshing 的博客）。
• C/C++ 的 volatile 没用：它为内存映射 I/O 和信号处理设计，只保证变量不被缓存在寄存器、每次从内存重读；不阻止重排是标准行为（部分编译器在特定平台或选项下才保证）；也挡不住 CPU 乱序和缓存一致性问题。Java 和 C# 的 volatile 则保证原子性（见下文）。
• 编译器屏障：GCC 用 asm volatile("" ::: "memory")，MSVC 用 _ReadWriteBarrier()。多数函数调用是隐式编译器屏障，因为编译器看不到副作用；但仅当编译器看不到函数定义时成立（例如定义在另一个翻译单元），链接时优化 (LTO) 会消除这类隐式屏障从而引入并发 bug；内联函数也可能例外。编译器屏障挡不住 CPU 运行时乱序，有的 ISA 有专门指令（PowerPC isync）。

内存序语义（卷 I 4.9.4）

• 只在多核 + 多级缓存的机器上出现：单核总按执行顺序看到自己的读写，多核之间可能对读写的表观顺序产生分歧，而且不同 CPU 行为不同。每种 CPU 都有自己的内存序语义规则，掌握最弱语义下的技巧就能在更强的 CPU 上通用。
• 缓存回顾：写操作更新 L1 中的副本，写回主存通常推迟（直写缓存可忽略）。
• MESI 协议：每个缓存行处于 Modified（本地已改）、Exclusive（仅本核有）、Shared（多核有相同副本）、Invalid（失效） 之一；各核 L1 通过互连总线 (ICB) 相连，L1、更高级缓存与主存构成缓存一致性域。MOESI 多一个 Owned 状态，允许不先写回主存就共享已修改数据。示例：核 1 读 g_ready（E）→核 2 读，核 1 回应（双方 S）→核 1 写 1（本核 M，发 Invalidate，核 2 变 I）→核 2 再读时从核 1 取得新行（双方 S，并触发写回主存）。缓存结构见 计算机硬件与内存层次。

stateDiagram-v2
  [*] --> E: 核1首次读
  E --> S: 核2读同一行
  S --> M: 核1写（核2副本变为I）
  M --> S: 核2再读，从核1取得并写回主存

上图是书中例子里核 1 那一份缓存行的状态变化。

• MESI 怎么出错：为降低延迟，协议的某些操作被推迟执行。例如核 1 已有 g_ready 所在的缓存行、还没有 g_data 的，g_ready = 1 就可能先于 g_data = 42 对其他核可见。结论：缓存一致性协议的优化会让两条读写指令在其他核看来以与实际执行相反的顺序发生。
• 内存栅栏 (memory fence / memory barrier)：一条指令「越过 (pass)」另一条有四种情况：读越读、读越写、写越写、写越读。理论上每种都可以有双向、正向、反向栅栏，共 12 种；实际 ISA 只提供几种组合。最强的是全栅栏 (full fence)，双向阻止读写越过，但硬件代价高。所有栅栏都有两个副作用：充当编译器屏障，并阻止 CPU 乱序跨越栅栏。所以原子指令 + 内存栅栏就足以实现可靠的互斥锁、自旋锁和其他无锁算法。
• 三种语义（内存序语义其实是读写指令的属性，栅栏只是赋予它们语义的手段）：
  • 释放 (release)：程序顺序中在它之前的读写不能越过这次共享写（write-release），只管正向。
  • 获取 (acquire)：程序顺序中在它之后的读写不能越过这次共享读（read-acquire），只管反向。
  • 全栅栏：双向。
• 何时用：生产者连续两次写（先 g_data 后 g_ready），把第二次写变成 write-release，在它之前放 release 栅栏（核等待之前的写全部提交到一致性域）；消费者先读标志再读数据，把第一次读变成 read-acquire，在它之后放 acquire 栅栏（核等待其他核的写全部刷入一致性域）。即 g_data = 42; RELEASE_FENCE(); g_ready = 1; 与 while (!g_ready) PAUSE(); ACQUIRE_FENCE(); ASSERT(g_data == 42);。

sequenceDiagram
  participant P as 生产者（核1）
  participant C as 消费者（核2）
  P->>P: g_data = 42
  P->>P: release 栅栏
  P->>C: g_ready = 1（write-release）
  C->>C: 读到 g_ready（read-acquire）
  C->>C: acquire 栅栏
  C->>C: 读 g_data，保证为 42

上图说明 release 与 acquire 成对使用时，消费者看到标志后一定能看到数据。

• CPU 内存模型：DEC Alpha 默认语义极弱，几乎处处要加栅栏；Intel x86 默认很强。

原书问题（4.9.4.9）：书中称 x86 的 sfence 提供 release 语义、lfence 提供 acquire 语义。按 Intel SDM 第 3 卷「Memory Ordering」一节，x86（WB 内存）本身已保证普通读具有 acquire 语义、普通写具有 release 语义，唯一允许的重排是「后面的读越过前面写到不同地址的写」（StoreLoad），只有 mfence 或带 lock 前缀的指令能阻止它。sfence 主要用于给非临时 (non-temporal) 存储和写合并内存排序，lfence 是读顺序/指令派发序列化屏障（常用于 Spectre 缓解）；在普通代码中实现 acquire/release 不需要它们，编译器对 memory_order_acquire/release 也只生成普通 mov。

原子变量与 C++ 内存序（卷 I 4.9.5–4.9.6）

• C++11 的 std::atomic<T> 几乎能把任何类型变成原子变量（std::atomic_flag 是原子布尔），默认提供全栅栏语义，从而同时排除三种数据竞争来源。把生产者-消费者例子的变量换成 std::atomic 即可变成无竞争程序。
• 实现按大小特化：32/64 位类型可直接用原子指令无锁实现，更大的类型内部用互斥锁；可调用 is_lock_free() 检查。
• std::memory_order 选项（作者的解释）：

• 原书问题（consume）：按 C++ 标准，memory_order_consume 是「依赖序 (dependency-ordered)」的 acquire：只保证数据依赖于该读结果的后续操作能看到对方 release 之前的写，并不是「只防指令重排、不管一致性」；实际上所有主流编译器都把它直接提升为 acquire，P0371R1 起标准不鼓励使用，C++26 经 P3475R2 已将其弃用。
• 原书问题（示例代码）：4.9.5 示例 std::atomic_flag g_ready = false; 及之后的 g_ready = true、while (!g_ready) 无法编译——atomic_flag 没有从 bool 的构造/赋值和到 bool 的转换，只能用 test_and_set()/clear()（C++20 起还有 test()），初始化在 C++20 前需用 ATOMIC_FLAG_INIT；应改用 std::atomic<bool>（书中 4.9.5.1 的第二个示例正是这么做的）。同理，4.9.7.1 SpinLock 构造函数里的 m_atomic(false) 也不合法，C++20 起默认构造即为 clear 状态，之前应写 m_atomic = ATOMIC_FLAG_INIT。
• 注意（一般知识，非本书内容）：C++ 标准中 std::atomic 操作的默认内存序是 memory_order_seq_cst（顺序一致），memory_order_acq_rel 是另一个独立选项；书中把「acquire/release」说成默认值，与标准的表述不同，这里两说并列，以 C++ 标准文本为准。
• 指定的内存序只是下限，某些硬件上会更强：例如 x86 上 relaxed 读实际具有 acquire 语义。使用时要从重载运算符改为显式 store()/load()，如 g_ready.store(true, std::memory_order_release) 与 g_ready.load(std::memory_order_acquire)。
• 作者建议遵循 80/20 规则：宽松内存序很容易用错，只在性能分析证明确有必要、且改动确实带来预期收益时才使用非默认内存序。
• 解释型语言：Java（JVM）和 C#（CLR）在虚拟机中运行，VM 像软件模拟的 CPU 和内核，自己管理线程调度，因此能提供不受硬件约束的同步设施。例如它们的 volatile 保证原子性，读写实际上直达主存。
  • 原书问题：这种说法不准确。按 Java 语言规范（JLS §17.4、§17.7）与 C# 规范，volatile 保证的是对该变量单次读或写的原子性（Java 中包括 long/double）以及可见性和顺序（Java 中 volatile 读写是顺序一致的同步动作；C# 中是 acquire/release），但 v++ 这类读-改-写不是原子的，需要 AtomicInteger/Interlocked。读写也并不绕过 CPU 缓存——可见性靠的是缓存一致性加 JIT 插入的栅栏。

自旋锁及其变体（卷 I 4.9.7）

• 基本自旋锁：用 std::atomic_flag，TryAcquire() 调 test_and_set(std::memory_order_acquire)，Acquire() 循环 TryAcquire() 并 PAUSE()（不支持 pause 的平台、预期争用高时可改用 std::this_thread::yield()），Release() 调 clear(std::memory_order_release)。获取用 acquire 是为了防止在别的线程尚未完全离开临界段时就观察到锁已释放；释放用 release 是为了保证解锁前的所有写不会被看成发生在解锁之后。
• 作用域锁 (Scoped Lock)：构造时加锁、析构时解锁，适用于任何提供 Acquire()/Release() 的锁，函数有多个返回点时尤其有用（即 错误处理与断言 中提到的 janitor/RAII 思路）。
• 可重入锁：普通自旋锁中，同一线程重复获取会死锁（例如持锁的 B() 调用同样加锁的 A()）。做法是在原子变量里存持有者线程 ID 的哈希，并加引用计数保证 Acquire/Release 成对：已持有就直接加计数；否则用 compare_exchange_weak(0 → tid) 自旋；计数归零时存 0 解锁。CAS 用 relaxed，另用 std::atomic_thread_fence 在获取后加 acquire 栅栏、释放前加 release 栅栏。
• 读写锁 (readers-writer lock)（又称 shared-exclusive lock、push lock）：允许多个读者并发，写者等所有读者结束后以独占模式获取。实现上在原子变量里存读者引用计数，保留一个值表示写者持有，例如 0–0x7FFFFFFF 表示读者数，0x80000000 表示写者。缺点是饥饿：写者持锁太久会饿死读者，读者太多会饿死写者。替代方案有顺序锁 (sequential lock)，以及 Linux 内核中支持多读多写的 RCU（read-copy-update）。书的网站上有完整实现。
• 「无需加锁」断言 (lock-not-needed assertion)：游戏循环通常分阶段执行，若某共享数据在帧前段只被一个线程访问、后段又只被一个线程访问，按结构这两者不会重叠，理论上不需要锁。与其「以防万一加锁」或「干脆不管」，作者更倾向断言不需要锁：开销极低、发布前可剥离，还能在假设不成立或日后重构破坏假设时自动报警。检测不必 100% 可靠，90% 命中率就够，因为团队每天大量运行游戏总会有人触发。因此不用原子布尔（那和无争用自旋锁一样贵），而用 volatile bool：Acquire() 中 assert(!m_locked); m_locked = true;，Release() 中 assert(m_locked); m_locked = false;，再用 BEGIN/END_ASSERT_LOCK_NOT_NECESSARY 宏或 janitor 包装，在 ASSERTIONS_ENABLED 关闭时编译为空。作者说 Naughty Dog 实现了它，确实抓到了多处程序员以为不会重叠的关键操作重叠。

无锁事务与无锁链表（卷 I 4.9.8–4.9.9）

• 从自旋锁本身的实现看，写自旋锁就是无锁编程的一个例子。无锁编程的目标是既不让线程睡眠，也不让它困在自旋锁的忙等循环里。
• 事务思路：大部分工作在只有本线程可见的本地数据上完成，准备好后用一条原子指令（CAS 或 LL/SC）提交，成功就「发布」到共享数据结构；失败说明别的线程同时提交成功了，于是重试。因为一个线程失败必然意味着另一个成功，系统总有线程在前进，这正是无锁的定义。
• 无锁单链表 push_front()（例子来自 Herb Sutter 在 CppCon 2014 的演讲）：新建节点、填数据，pNode->m_pNext = m_head.load(relaxed)；然后循环 m_head.compare_exchange_weak(pNode->m_pNext, pNode, std::memory_order_release, std::memory_order_relaxed)，成功用 release，失败用 relaxed。失败时 compare_exchange_weak 会自动把 m_pNext 更新为当前头节点，所以代码里看不到显式重新初始化。

flowchart TD
  A["本地创建节点并填数据"] --> B["next 指向当前头节点"]
  B --> C{"CAS: 头指针仍等于 next?"}
  C -- "是" --> D["头指针换成新节点，提交成功"]
  C -- "否，next 被更新为新头" --> C

上图是这个两阶段过程：准备事务，然后用 CAS 原子提交，失败就重试。

延伸阅读（卷 I 4.9.10）

书中推荐：Herb Sutter 的 CppCon 2014 演讲、CMU Geoff Langdale 的讲座、Samy Al Bahra 的并发综述演讲、Mike Acton 关于并发思维的演讲、Jeff Preshing 的博客，以及 Linux 内存屏障资料。

PBRT 的视角：CAS、原子浮点与 MESI（PBRT 4e B.6.1–B.6.3）

• compare-and-swap：书中示例用 compare_exchange_weak() 循环求多线程最大值；失败时 currentMax 会被更新为最新值再重试。无锁建树：线程在局部完整构造子节点，再用 CAS 把空指针替换为它；失败说明别的线程已抢先，删除自己的节点、改用对方的即可。
• 原子浮点：pbrt 的 AtomicFloat 把浮点数位模式存在 std::atomic 整数中，用 CAS 循环实现加法（详见 数值表示与浮点数 中关于 C++20 的观点对照）。
• MESI 与伪共享：写一个在别的缓存中处于 shared/modified/exclusive 状态的缓存行，需要发出 RFO (read for ownership) 使其他副本失效，可能停顿几十到上百个周期。pbrt 对渲染时会被修改的类使用 alignas(PBRT_L1_CACHE_LINE_SIZE)，让它独占缓存行，避免伪共享 (false sharing)。
• 内存屏障：编译器和硬件都可能重排写操作，单线程察觉不到，多线程则需要屏障；C++ 原子操作和同步原语通常已包含它们（Boehm 2005 指出线程无法仅以库的形式可靠实现，C++11/C11 解决了这一点）。