无锁结构 · 拾光集

环境：Windows 11 x64，GCC 13.1.0（MinGW-w64），g++ -std=c++17 -O2 -Wall -Wextra -static -lpsapi。ABA 那一节是确定性构造（手工排出交错顺序），不是”跑很多次也许会遇到”；对拍那一节用固定随机种子（mt19937(20261015)）生成操作序列，无锁版和有锁版跑的是同一份序列。

一、CAS 循环：无锁代码的语法与它的第一个骗局

最典型的无锁原语就是 CAS 重试循环。一个 Treiber 栈（无锁栈）：

void push(Node* n) {
    n->next = head.load(std::memory_order_relaxed);
    while (!head.compare_exchange_weak(n->next, n,
                                       std::memory_order_release, std::memory_order_relaxed)) {}
}
Node* pop() {
    Node* old = head.load(std::memory_order_acquire);
    while (old && !head.compare_exchange_weak(old, old->next ? old->next : nullptr,
                                              std::memory_order_acquire, std::memory_order_relaxed)) {}
    return old;
}

读这段代码要注意三件事，每一件都是坑：

compare_exchange_weak(期望, 目标) 的副作用：失败时它会把当前实际值写回第一个参数，循环因此自动拿到新的 old，不需要自己重读。写成 while (head.load() == old && !CAS(...)) 反而多一次读。
weak 会虚假失败（在 x86 上 weak 和 strong 生成一样的 lock cmpxchg，没有虚假失败；在 LL/SC 架构上才有）。虚假失败在循环里无害，所以循环里用 weak，一次性判断用 strong。
pop 里那句 old->next 就是在读”别人的现在”：old 是从 head 快照来的，old->next 可能在 CAS 成功之前已经被改掉。下一节就是它出事的过程。

二、ABA：地址没变，但含义变了

确定性的 ABA 演示（不用线程，手工把交错排出来）。节点是 4 个静态对象 a{1} b{2} c{3} d{4}，初始栈 c → b → a。

  A 读到 head=3，打算 CAS 成它下面的 2
  B 弹出 3、2 后把 3 原样压回 ⇒ 真实栈变成 c -> a
  A 的 CAS(期望 head=3, 装入 2) 返回 成功
  CAS 之后栈顶=2，它的 next=1（B 的 2 早被弹走了）⇒ 链表被接回了废弃节点
  从栈顶往下走能遇到的在册节点数=4（正确实现里应该等于当前实际元素数）

发生了什么，逐步对照：

步	A 的视角	真实状态
1	`head == &c`，`c->next == &b`	`c → b → a`
2	（被抢占）	B 弹出 c、b，把 c 压回，再 pop 一次 ⇒ `c → a`
3	CAS：期望 `head == &c` 成立 → 装入 `&b`	`head = &b`
4	我的 pop 成功了，返回 c	栈顶现在是 b，一个已经被 B 弹走的节点

A 的 CAS 返回”成功”，因为 head 这个字确实还等于 &c——CAS 只能保证”值没变”，不能保证”没人动过”。结果是把 b 接回了链表：从新栈顶往下走能遇到 4 个在册节点，而当时的真实元素只有 2 个。链表结构被写坏，而且没有任何断言会响。

三种解法，本机能量化的只有前两种

解法	原理	代价（本机）
版本号 / tag	CAS 同时比较 `(指针, 计数)`，任何改动都会让计数变了	需要 16 字节原子——第八节实测：MinGW 上 `atomic<16 字节>` 不加 `-latomic` 链不过，加了之后 `is_lock_free=0`，是带锁模拟，等于把无锁的意义抹掉了
节点池 + 索引	用 `数组下标` 代替指针，把 tag 塞进同一个 64 位字（如高 32 位 tag + 低 32 位索引）	只支持固定节点数；下标化让跨进程共享更容易（共享内存队列都这么做）
指针回收保护（RCU/hazard pointer/epoch）	不解决 ABA 本身，而是保证”被读到的节点不会被释放”	见第四节

x86-64 上还有一个”免费午餐”没被 GCC 用上：lock cmpxchg16b 能做真 16 字节 CAS，但第八节测到 libatomic 在这个构建里走的是锁模拟。要真用带 tag 的指针，得自己写 __sync_... 或内联 lock cmpxchg16b，并保证 16 字节对齐（alignof 实测 16 ✓）。

三、结构对不对，靠对拍；快不快，看竞争强度

固定随机种子生成 4 条线程各 15 万步的操作计划（55% push / 45% pop），同一份计划分别喂给无锁栈和有锁栈，并用一个 atomic<int> 的”取走标记数组”检查同一个节点是否被两个线程各取走一次：

  无锁栈：329839 次 push、270161 次成功 pop、重复取走 0 个、结束记账剩余 59678 个、链表实走 59678 个，58.5 ms
  判定：重复取走必须为 0，且 记账剩余==链表实走 → 通过
  有锁栈参照：270161 次成功 pop、重复取走 0 个、剩余 59678 个，28.3 ms（0.48x 于无锁）

三个结论按重要性排：

正确性是靠”三个不变量”确认的，不是靠”跑起来没崩”：
- 成功 pop 的次数两边相同（270161）；
- 重复取走必须为 0（一个节点被两个线程拿到 = 结构坏了）；
- 结束时”push+1/pop−1 的记账值” == 从栈顶实际走一遍链表的长度（59678 == 59678）——这一条能抓到 ABA、能抓到丢节点、也能抓到接回废节点。
无锁在 4 线程竞争下比有锁慢 2.07 倍（58.5ms vs 28.3ms）。原因不是”原子比锁快”这句话错了，而是竞争形态不同：锁会让后来者睡着（第三节量过：唤醒 11.4µs，但睡着期间不抢总线），而 CAS 失败者醒着重试，几十个线程反复夺同一条缓存行 → 第八节的 lock cmpxchg 每次都要求该行独占。
但单线程无竞争时它确实更快：

  单线程 200 万次操作（100 万 push + 100 万 pop）：无锁 12.59 ns/次 | 有锁 18.25 ns/次
  节点池 15 MB（16 字节/节点），push 期间私有提交 15.96 → 15.96 MB

无锁快 1.45 倍（省下 mutex 的函数调用与内部状态维护），而且内存零增长——节点是静态池，push/pop 只搬指针，这也是”无锁结构通常要配套节点池”的原因（本篇第三节）。

所以”要不要无锁”的判断依据是竞争强度，不是”无锁听起来高级”：低竞争 → 无锁略优；高竞争单点（一个 head） → 无锁明显劣；高竞争但能分片 → 用分片（第六节）；高竞争且必须共享一个结构 → 先把锁的临界区缩短（第二节实测缩到 0.05µs）。

四、无锁的真正难题：什么时候能释放内存

上面那个栈之所以”敢”让 B 把节点复用了还给 A 的 CAS 成功，前提是节点来自静态池、永不释放。一旦节点要归还系统，无锁就多出两个问题：

A 还握着 old 指针时，B 不能 free(old) —— A 接下来要读 old->next（本篇第一小节的三点注意之一）。这就是”回收难题”：读侧没有加锁，写侧就不知道什么时候没人读了。
ABA 的多数实际成因就是回收后复用。地址能重新出现，通常是因为内存被 free 又 malloc 回来了。

可落地的四条路（各自的代价我按本机/可验证程度标注）：

做法	思路	代价
永不释放 / 池化	节点用数组下标 + 空闲链表，逻辑释放只是挂回空闲链	峰值内存不降；本篇第三小节实测节点池 15MB 常驻
引用计数（`shared_ptr` 快照）	读侧复制一份 `shared_ptr`，最后一个读者负责释放	第七节实测：读一次 25.8–28.9 ns（含原子引用计数），且它的计数本身就是个争用点——多读者时比 mutex（18.4ns）还贵
hazard pointer	每个线程公开”我此刻在指哪个节点”，释放方先查所有 hazard 槽	每次读要发布 hazard 指针（一次 relaxed 存 + 内存栅栏），释放要 O(线程数) 扫描
epoch / RCU 宽限期	全局 epoch，读侧进入/离开时记录；回收要等所有线程都跨过一个 epoch 边界	回收有延迟（对象堆积），需要”危险列表”长度阈值触发

值得强调的是**“用 shared_ptr 就安全了”是个危险的错觉**：第七节实测的 COW 快照是”一个指针变量的原子替换”，那是对的；但如果多个字段各自是 shared_ptr，读者会拿到跨版本混读。把版本号和根指针打包进同一次原子交换，才是快照语义。

五、什么时候该写无锁（本机数据支撑的判据）

有实测的锁瓶颈。先量：本节的表给了参照——无竞争 12.59 vs 18.25ns（省 5.7ns），竞争 4 线程时亏 30.2ms。如果每秒调用不到 10 万次，无锁的收益是 0.5ms/秒量级，不值得那份复杂度。
单点原子量的东西尽量退化成”每线程私有 + 事后合并”（第六节的分片、第八节的 alignas(64) 计数器）。这条永远比写无锁队列划算。
只写”能证明”的无锁结构：第三节那三条不变量（成功次数相同、重复取走为 0、记账==实走长度）要能进 CI，用固定种子跑几十万次步。不能对拍的无锁代码等于没测过的无锁代码。
优先用现成的：boost::lockfree::queue、moodycamel::ConcurrentQueue、或者干脆用 IoRing/IOCP 这类系统队列。本节没有实现无锁队列（Michael-Scott）并测它——无锁单链表的一个 next 字段就要处理”两个线程同时接链”的窗口，实现难度远高于栈，我不给自己留”没测过但看起来对”的代码。

六、小结

CAS 只能保证”值没变”，不能保证”没人动过”。确定性的 ABA 演示：A 的 CAS 返回成功，却把已被弹走的节点接回链表，遍历遇到 4 个在册节点而真实元素只有 2 个，且不会有任何断言报警。
带 tag 的指针要 16 字节原子，而这套工具链上 16 字节原子不是无锁的（不加 -latomic 链不过；加了 is_lock_free=0）。要么把 tag 和索引打包进一个 64 位字，要么自己写 lock cmpxchg16b。
无锁栈的对拍三条不变量都通过（成功 pop 两边 270161、重复取走 0、记账剩余==链表实走=59678），但4 线程竞争下它比有锁栈慢 2.07 倍（58.5ms vs 28.3ms）——CAS 失败者醒着夺缓存行，锁的等待者睡着。单线程无竞争时它快 1.45 倍（12.59 vs 18.25 ns）。
回收才是无锁的真难点：池化（实测 15MB 常驻不增）、shared_ptr 快照（读一次 26–29ns，且计数本身是争用点）、hazard pointer、epoch/RCU 各有权衡；shared_ptr 只保护”单个根指针”，不保护”跨字段一致性”。
决策顺序应该是：缩短临界区 → 分片 → 无竞争设计 → 最后才轮到无锁结构。前三步的收益在本专栏前几节都有数字，第四步在这台机器上甚至可能是负收益。