算法与数据结构 / 并发数据结构 · 从 CAS 到无锁队列与内存回收 待审核 6 页

并发数据结构 · 从 CAS 到无锁队列与内存回收

单线程的数据结构有唯一正确答案：给定一串操作，结果是确定的。多线程一进来这个前提就没了——两个线程同时 push，谁先谁后不由代码决定。于是正确性判据要换：linearizability 要求每个操作看起来在它的调用与返回之间的某个瞬间原子生效，且这些瞬间排成的顺序既能被顺序规格解释、又与实际的重叠区间相容。

效率判据也要换。渐近复杂度对并发结构几乎不起作用——一把大锁护住的栈与 Treiber 栈都是 O(1) push，差别在进展保证：wait-free 保证每个线程在有界步数内完成，lock-free 只保证总有一个线程在推进，而上锁的版本什么都不保证，持锁者一停全场停摆。这三档与吞吐无关，lock-free 不等于更快。

本系列的实现约定是一条硬约束：JavaScript 单线程，所以不假装做真并发。每个「线程」是一串带标号的原子步骤，调度器决定下一步走谁，任意交错都可复现、可枚举、可测试。于是「小规模下穷举全部交错」成了这里最有力的手法：Treiber 栈两线程三操作共 168843 条交错全部可线性化，而普通 store 链接的坏队列在 20 条交错里有 18 条丢元素。

判据与原语：怎么算对，怎么算有进展

先把两把尺子立起来：linearizability 判对错，进展保证的三级判效率。再看唯一的原语 compare-and-swap 与它自带的坑——指针值回到原样但中间发生过变化，CAS 察觉不到。

linearizability · 三级进展保证

正确性判据与进展保证

并发执行没有唯一正确答案，正确性判据换成 linearizability：每个操作看起来在调用与返回之间的某个瞬间原子生效。效率判据换成进展保证的三级，而这三级说的不是吞吐。

 compare-and-swap · ABA · tagged pointer

CAS 与 ABA

无锁结构只靠一条原语：compare-and-swap 把「值仍是我读到的那个」与写入绑成一步。它的盲区是 ABA——指针值回到原样但中间发生过变化，CAS 察觉不到。

交错模拟器的适用边界

模拟器给的是可枚举而非完备。它把每条原子指令当作不可分割的一步，于是覆盖了「线程在指令之间被切换」这一类现象，也就覆盖了绝大多数教学用的反例。 它不覆盖的有两类。其一是编译器与 CPU 的重排序——那要另一套模型，见 内存序。其二是真实的时间：模拟器里「一个线程停住」是布尔的，现实中是概率的，所以它能证明某条交错存在，不能告诉这条交错多久出现一次。 交错数随步数是多项式系数级增长的（两个线程各 kk 步是 (2kk)\binom{2k}{k}），所以穷举只在很小的规模下可行。本系列最大的一次穷举是 794968 条，再往上就只能抽样。

判据与原语 · 延伸阅读

两个经典结构与它们共同的难题

Michael-Scott 队列用 head / tail 两个指针各自 CAS 推进，靠「任何线程都可以替落后的 tail 推一把」保住 lock-free。Treiber 栈比它简单得多，却把真正的难题暴露得更彻底：一个线程正要读的节点可能已被另一个线程释放。

MPMC 无锁队列 · 帮助机制

Michael-Scott 队列

链表队列的 head 与 tail 各用 CAS 推进，中间必然出现「节点已链上、tail 还没跟上」的状态。任何线程都可以替落后的 tail 推一把，这条帮助机制是 lock-free 成立的前提。

 hazard pointer · epoch · RCU

Treiber 栈与内存回收

Treiber 栈只有一个 top 指针，却把无锁编程最难的一关暴露得最彻底：一个线程正要读的节点可能已被另一个线程释放。引用计数、hazard pointer 与 epoch-based reclamation 是三条出路，代价各不相同。

带 GC 的语言藏起了最难的一半

JavaScript、Java、Go 里写无锁结构，写完 CAS 循环基本就完了：没人要操心「刚读到的节点被别人 free 掉」，GC 会等到没人引用才回收。C++ 与 Rust 没有这层地板。 于是同一份伪代码在两类语言里的工程量差一个数量级。Michael 的 hazard pointer 论文全篇解决的就是这一件事，Fraser 的 epoch-based reclamation 也是；Treiber 栈与内存回收 一页把三种方案的延迟回收量与扫描代价都量了出来。 值得记住的一个数：本系列的 ABA 实验里，3945 条交错有 2577 条至少读过一次已释放的节点。tagged pointer 能让不可线性化的交错从 18 条降到 0，却对这 2577 条完全无效——它防的是 CAS 认错，不是防访问已释放的内存。

无锁队列、栈与内存回收 · 延伸阅读

规模：把争用摊开，以及重排序

线程一多，正确的结构也会因为大家挤在同一个 cell 上而废掉。分片把一把大锁换成 N 把小锁、再换成 per-bucket 的 CAS。最后一页回到最底层：relaxed 与 acquire-release 的差别，以及为什么 SPSC 环形队列只需要后者。

LongAdder · 分段锁 · false sharing

分片与争用

结构正确不等于可用。线程一多，大家挤在同一个 cell 上，CAS 的失败率就把吞吐吃掉。分片把争用域切开，per-bucket CAS 切到最细，而 padding 处理的是切开之后仍然共享的那一层。

争用、分片与内存模型 · 延伸阅读

relaxed · acquire-release · seq_cst

内存序

原子操作除了不可分割，还要回答另一个问题：它与周围那些普通读写的先后关系对别的线程是否可见。relaxed 什么都不保证，acquire-release 建一条同步边，seq_cst 要求一个全局总序。