无锁栈：Treiber 栈、ABA、指数退避与消除退避

并发栈只需要一个共享指针 top 和一条 CAS（Compare-And-Swap）：push 把新节点挂到 top 前面，pop 把 top 换成 top->next。核心代码不到十行，但三个生产实现都在上面加了限制：Linux 的 llist 规定 llist_del_first 同一时刻只能有一个调用者；Boost.Lockfree 的 stack 把弹出的节点放进自己的 freelist，析构之前从不还给操作系统；Windows 的 SList 把表头做成 16 字节，里面有一个 48 位的序号。

这三处限制分别对应三个经常被混在一起的问题：

• ABA：CAS 只比较值，top 从 A 变走又变回 A 时，它看不出中间发生过什么。
• 内存回收：pop 在 CAS 之前要读 top->next，这个节点可能已经被别的线程弹出并释放。给指针加版本号能解决 ABA，解决不了这个。
• 争用：所有线程都在同一个 cache line 上做 CAS，线程越多失败越多。指数退避和消除数组都是为它设计的，但它们提升吞吐的机制并不相同。

本文逐个拆开。所有实测数字都来自同目录的 reproduce/：aba_demo.c 确定性地复现 ABA；lfstack.c 实现五种栈，用”每个压入的元素恰好弹出一次”的守恒检查验证正确性，并用 ThreadSanitizer 和 AddressSanitizer 各跑一遍；性能实验只用了 4 个逻辑 CPU，环境和口径见第五节。

一、Treiber 栈：一个指针、一次 CAS

从 System/370 的空闲链到 Treiber

用 CAS 维护 LIFO 链表的做法比”Treiber 栈”这个名字早。IBM System/370 的《Principles of Operation》（GA22-7000-6，1980 年版）附录 A 在 COMPARE AND SWAP 的示例里有一节 “Free-Pool Manipulation”，用 COMPARE DOUBLE AND SWAP（CDS）同时交换空闲链的表头指针和紧挨着它的一个计数字；IBM 1984 年的美国专利 US 4,482,956 转述这段示例时写明，这个计数值”对队列的完整性必不可少”。计数器存在的理由，就是本文第二节要讲的 ABA。

今天的文献通常把无锁栈归于 R. Kent Treiber 1986 年的 IBM Almaden 研究报告 Systems Programming: Coping with Parallelism（RJ 5118）。这份报告目前没有公开的在线副本；Hendler、Shavit 和 Yerushalmi（SPAA 2004）把它列为 Treiber 栈的出处，并说自己的节点池”类似 [Treiber] 引入的池”。后来的理论框架来自两篇论文：Herlihy 和 Wing 的线性一致性（linearizability，TOPLAS 1990）给出了”并发栈正确”的定义；Herlihy 的 Wait-Free Synchronization（TOPLAS 1991）区分了无锁（lock-free）与无等待（wait-free）两种进度保证。

push 与 pop

reproduce/lfstack.c 里 ABA 敏感的朴素版本（naive_push / naive_pop，删掉了统计代码）：

typedef struct node {
    _Atomic(struct node *) next;
    uint64_t val;
} node_t;

static _Atomic(node_t *) top;

void push(node_t *n) {
    node_t *old = atomic_load_explicit(&top, memory_order_relaxed);
    do {
        atomic_store_explicit(&n->next, old, memory_order_relaxed);
    } while (!atomic_compare_exchange_weak_explicit(&top, &old, n,
                 memory_order_release, memory_order_relaxed));
}

node_t *pop(void) {
    node_t *old = atomic_load_explicit(&top, memory_order_acquire);
    for (;;) {
        if (!old) return NULL;
        node_t *nx = atomic_load_explicit(&old->next, memory_order_relaxed);
        if (atomic_compare_exchange_weak_explicit(&top, &old, nx,
                memory_order_acquire, memory_order_acquire))
            return old;
    }
}

push 的第二步只写新节点 N 自己的 next，此时 N 还没有发布，其他线程看不到它。pop 的第二步不一样：它读的是共享节点 A 的 next，而在读完到 CAS 之间，A 可能已经被别的线程弹出、重用甚至释放。图中标红的那一步就是后面两节的全部麻烦所在。

compare_exchange_weak 失败时会把看到的当前值写回 old，所以循环里不需要重新 load。weak 允许伪失败（spurious failure）；在 LL/SC 架构上它可以直接编译成一次 LL/SC 尝试，放在重试循环里正好。

线性化点与进度保证

线性化点（linearization point）是操作”看起来瞬间生效”的时刻：成功的 push 和非空的 pop 都在 CAS 成功时生效；返回空的 pop 在读到 top == NULL 的那次 load 生效。

进度保证可以直接从代码读出来。top 只会被成功的 CAS 修改，所以一个线程的 CAS 失败，意味着在它读 top 之后有另一个操作完成了。于是任意时刻，只要有线程在执行，系统整体就在前进，这就是无锁的定义。它不是无等待的：没有任何机制阻止某个线程每次都输掉 CAS。第五节的实测会看到，退避会放大这种不公平。

内存序

push 先用 relaxed 写 n->next（以及 n->val），再用 release CAS 发布；pop 用 acquire 读 top，之后才读节点字段。pop 的 CAS 失败序也是 acquire，因为失败后刷新的 old 马上会被解引用。

这里有一个容易漏的细节：pop 读到的 top 往往不是 push 直接写的，而是中间若干次 push/pop 的 CAS 写的。C11 的释放序列（release sequence）规则保证：一次 release 写之后，同一原子对象上的读-改-写（read-modify-write）操作都延续它的释放序列。top 在初始化之后只被 CAS 修改，所以任何 acquire 读都能与之前每一次 release CAS 同步，pop 看得到节点被发布时写入的内容。在 x86-64 上带 lock 前缀的 cmpxchg 本身就是全屏障，这些内存序参数主要约束编译器；在 ARM、POWER 这样的弱内存模型上，它们决定生成哪些屏障。

二、ABA：CAS 只比较值

一次确定性的 ABA

ABA 的描述通常是”线程 1 读到 A，被换出；线程 2 把 A 弹出、再压回；线程 1 的 CAS 误以为什么都没变”。reproduce/aba_demo.c 用两个信号量把这个交错固定下来：线程 T1 在 pop 里读完 old = A、nx = A->next = B 之后停下，T2 执行 pop、pop、push(A)，然后放 T1 继续执行 CAS。

程序的真实输出（results/aba_demo.txt）：

naive (64-bit CAS on ptr):
  initial:                     top -> A B C
  T2 popped A, popped B (still holds it), pushed A back
  after T2:                    top -> A C
  T1 pop returned A after 1 CAS attempt(s)
  final:                       top -> B C
tagged (128-bit CAS on {ptr, tag}):
  initial tag = 3
  initial:                     top -> A B C
  T2 popped A, popped B (still holds it), pushed A back
  after T2:                    top -> A C
  T1 pop returned A after 2 CAS attempt(s)
  final:                       top -> C
  final tag = 7

朴素版本里，T1 的 CAS 看到 top 仍是 A，于是把 top 设成它几步之前读到的 B。可 B 已经被 T2 弹出并持有，现在它同时在 T2 手里和栈顶上，下一次 pop 会把它再发一次。带版本号的版本里，top 的版本在 T2 的三次操作后从 3 变成 6，T1 的 CAS 失败，刷新后重读 A->next = C，第二次 CAS 成功，栈里只剩 C。这个交错不依赖时序，连续运行 1000 次输出逐字节相同。

ABA 的前提是地址被重用。只要节点从不重用（例如只 malloc 不 free，或者由垃圾回收保证仍被引用的地址不会被复用），pop 看到”还是 A”就意味着确实没变。所以 ABA 和内存回收总是一起出现：一旦允许节点复用或释放，就必须同时回答”CAS 会不会误判”和”读 A->next 时 A 还在不在”。

压力下的守恒检查

确定性演示说明问题存在，还需要知道它在真实调度下多常见。lfstack.c 的每个 push 都携带唯一值（线程号左移 40 位再加序号），弹出的值记在线程私有数组里；运行结束后把栈里剩下的元素弹空，检查器逐个核对：每个压入过的值必须恰好出现一次，不能丢（lost）、不能重复（dup）、不能出现没压入过的值（bogus），弹空时元素数也不能超过压入总数（超出说明链表成了环）。节点通过线程私有的空闲链回收，从不释放，因此这里只测 ABA，不涉及释放后使用。

4 线程、每线程 20 万次操作、push 和 pop 各占一半，换 20 个随机种子：

另外四种实现（mutex、tagged、backoff、elim）在本文所有运行里都通过了守恒检查，包括下面的 sanitizer 构建，以及第五、六节合计 150 次性能运行（results/*.txt 每一行末尾的 check= 字段）。

朴素版本每次都坏：80 万次操作里有十几万个元素再也没被弹出，而且每次弹空时链表都已成环（重复计数里有很大一部分是弹空阶段在环上反复读到的节点，检查器在弹出数超过压入总数时停止）。线程私有空闲链是 LIFO 的，刚弹出的节点很快就被同一线程重新压入，正好制造”同一地址回到栈顶”的条件。

这个”每次都坏”依赖机器。同一个 run.sh 在一台只有 2 个 vCPU 的 KVM 虚拟机（AMD EPYC 9754，Linux 6.8，GCC 13.3）上，4 个线程挤在 2 个 CPU 上，20 个种子全部通过守恒检查，丢失和重复都是 0（results/naive_stress_2vcpu.txt）；下一小节的 TSan 构建在这台机器上对 naive 也没有报告（results/sanitize_2vcpu.txt）。ABA 要求一个线程恰好停在读 old->next 与 CAS 之间的几条指令上，而另一个线程在此期间完成至少三次操作。CPU 少于线程数时，线程主要在时间片边界被换出，落在这个窗口里的概率很低；4 个线程真正并行时，窗口每时每刻都开着。所以上面的确定性演示才是 ABA 存在的证据，压力测试通过不能说明没有 ABA。

ThreadSanitizer 抓到的是什么

同一组程序用 GCC 和 clang 的 -fsanitize=thread 各跑一遍（results/sanitize.txt）：mutex、tagged、backoff、elim 四种实现都是 0 条报告且守恒检查通过；naive 有 3 到 4 条报告。这些报告不在 CAS 上，而在 n->val 的写入和空闲链指针 fnext 的写入上，是两个线程对同一节点的普通写-写竞争。

原因是 top 和 next 都是原子变量，ABA 本身不构成数据竞争（data race），TSan 没有理由报它。它报出来的是 ABA 的后果：同一个节点被两个线程同时”拥有”，于是对非原子字段的写入发生了竞争。TSan 只检测数据竞争，如果节点里的数据也全用原子访问，它就没有可报的东西了。守恒检查这类语义测试不能省。

Linux llist：用接口限制绕开 ABA

Linux 内核的 llist（Huang Ying，2010 到 2011 年）就是一个 Treiber 栈。v6.12 的 include/linux/llist.h 头部注释用一张表说明哪些操作可以不加锁并发：

 *           |   add    | del_first |  del_all
 * add       |    -     |     -     |     -
 * del_first |          |     L     |     L
 * del_all   |          |           |     -

L 表示需要锁。注释给出的原因正是 ABA：llist_del_first 依赖 list->first->next 不变，如果它在中途被抢占，另一个消费者做了 llist_del_first, llist_add, llist_add，first 可能恢复成原值而 next 已经变了。lib/llist.c 里的实现和第一节的 pop 几乎一样（v6.12，原样摘录）：

struct llist_node *llist_del_first(struct llist_head *head)
{
    struct llist_node *entry, *next;

    entry = smp_load_acquire(&head->first);
    do {
        if (entry == NULL)
            return NULL;
        next = READ_ONCE(entry->next);
    } while (!try_cmpxchg(&head->first, &entry, next));

    return entry;
}

内核没有加版本号，而是限制用法：多生产者用 llist_add，消费者要么只有一个，要么用 llist_del_all。后者就是 xchg(&head->first, NULL)，一次性摘走整条链，不读任何节点的 next，所以既没有 ABA，也不会碰到已释放的节点。代价是 llist 不提供通用的多消费者 pop：要逐个弹出，就只能有一个消费者，或者由调用者自己加锁。

三、版本号与双字 CAS

把计数器和指针一起比较

System/370 的 CDS 与 HSY 2004 第 2.3 节给出的是同一个办法：在 top 旁边放一个计数器，CAS 同时比较并替换两者，每次更新让计数器加一。HSY 写这篇论文时指针是 32 位的，他们指出当时的 x86 和 SPARC 都支持对对齐的 64 位块做 CAS，足够放下”指针加标签”。到了 64 位指针，同样的做法需要 128 位 CAS，x86-64 上就是 lock cmpxchg16b。lfstack.c 的 pop 一次尝试如下（tagged_try_pop，原样摘录）：

static inline u128 pack(node_t *p, uint64_t tag) {
    return (u128)(uintptr_t)p | ((u128)tag << 64);
}

/* 1 = popped into *out, 0 = empty, -1 = CAS failed (retry) */
static inline int tagged_try_pop(u128 *old, node_t **out) {
    node_t *p = ptr_of(*old);
    if (!p) return 0;
    node_t *nx = atomic_load_explicit(&p->next, memory_order_relaxed);
    if (__atomic_compare_exchange_n(&S.ttop, old, pack(nx, tag_of(*old) + 1),
                                    true, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE)) {
        *out = p;
        return 1;
    }
    return -1;
}

这里的 nx 可能是过期的：p 在读 next 之前可能已被别人弹出、重用。但只要版本号没变，就说明从读 old 到 CAS 这段时间里 top 没有被任何人改过，p 仍在栈顶，p->next 也还是它被压入时写的值。版本号一变，CAS 失败，过期的 nx 被丢掉。

计数器不必在每次更新时都加一。要让 top 回到同一个地址 A 却带着不同的 next，A 必须先被弹出、再被压入，所以只在 pop 时加一就足以识别 ABA。Michael 在 PODC 2002 的论文里也提到，Treiber 已经观察到 push 的 CAS 不受 ABA 影响。Boost.Lockfree 1.86 正是这样实现的：stack.hpp 的 link_nodes_atomic（push）用 old_tos.get_tag() 保留原标签，pop 和 consume_one 用 get_next_tag() 加一。本文的实现在 push 时也加一，只是为了让演示里的版本号变化更直观。

cmpxchg16b 的三个细节

Intel SDM 对 CMPXCHG8B/CMPXCHG16B 的描述里有三条和本文直接相关：

1. 必须 16 字节对齐。操作数不在 16 字节边界上时触发 #GP(0)（64 位模式异常表）。本机上用内联汇编对偏移 8 字节的地址执行 lock cmpxchg16b（reproduce/misaligned_cas.c），进程收到的是 SIGSEGV。lfstack.c 用 _Alignas(64) 让 top 独占一个 cache line，也顺带满足了对齐。
2. 失败也写。“To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison”：比较失败时处理器把原值写回，永远不会只产生加锁读而不产生加锁写。CMPXCHG 的描述里有同样的句子。一次失败的 CAS 和成功的 CAS 一样，要把 cache line 拿到独占状态，这是第五节退避有效的硬件原因。
3. 不是基础指令。它有自己的 CPUID 位（CPUID.01H:ECX 第 13 位），位为 0 时执行也是 #GP(0)。编译器的默认 x86-64 目标不假设它存在：不加 -mcx16 时，clang 22 会警告 16 字节原子操作”超过最大无锁宽度 8 字节”并改为调用库函数。

编译器对 16 字节原子操作的处理也不一样。同一段 __atomic_compare_exchange_n(unsigned __int128 *) 代码加 -O2 -mcx16：GCC 16.1.1 生成对 libatomic __atomic_compare_exchange_16 的调用，__atomic_is_lock_free(16, p) 返回 0；clang 22.1.6 直接内联 lock cmpxchg16b，返回 1。libatomic 在运行时按 CPUID 选择实现，本机上最终执行的仍是 cmpxchg16b；它的 16 字节 load 另有一条使用 vmovdqa 的路径，而 clang 把 16 字节 load 也内联成了 lock cmpxchg16b。单线程、每次 400 万次操作、CPU 2、5 次中位数（results/single_thread.txt）：

没有争用时，128 位版本比 64 位版本慢 38% 到 45%；clang 的内联版本反而比 GCC 的函数调用版本慢，与它把 load 也变成加锁 RMW 的反汇编结果一致，但本文没有做进一步的隔离实验。

标签放在哪里、有多宽

• 本文：{ptr, tag} 各 64 位，要 128 位 CAS。
• Boost.Lockfree 1.86：detail/prefix.hpp 在 x86-64 以及非 Android 的 ARMv8 上定义 BOOST_LOCKFREE_PTR_COMPRESSION，改用 tagged_ptr_ptrcompression.hpp：tag_t 是 uint16_t，放在 64 位字的最高 16 位，指针用 ptr_mask = 0xffffffffffff 取低 48 位，于是普通的 64 位 CAS 就够了。其他平台用 tagged_ptr_dcas.hpp 的双字 CAS。
• Windows x64：Windows 11 23H2 内核符号里的 _SLIST_HEADER 是 16 字节，HeaderX64 分为 Depth:16、Sequence:48（低 8 字节）和 Reserved:4、NextEntry:60（高 8 字节）。微软的驱动文档要求 64 位系统上 SLIST_ENTRY 16 字节对齐，所以地址的低 4 位不用存。

标签宽度决定了回绕风险。一个 \(k\) 位计数器只有在”读到 old 到执行 CAS”之间恰好前进了 \(2^k\) 的整数倍，并且 top 恰好又是同一个地址时才会误判。对 16 位标签，这要求某个线程停住的时间里栈上恰好发生 65536 的整数倍次 pop。按本机单线程约 66 Mops/s 估算，65536 次操作只要 1 毫秒左右，一个被抢占的线程完全可能停这么久，只是还需要计数和地址同时凑巧重合。48 位和 64 位计数器在任何现实的停顿时间内都不会回绕。

指针压缩还有一个前提：用户态地址不超过 48 位。Linux v6.12 的 Documentation/arch/x86/x86_64/5level-paging.rst 说明，5 级页表让用户态虚拟地址扩展到 56 位，但内核默认不在 47 位以上分配地址，除非 mmap 显式给出更高的提示地址。所以在默认配置下 Boost 的 48 位掩码仍然成立；一个自己用高地址提示 mmap 的分配器就会打破它。

LL/SC 架构（ARM 的 LDXR/STXR、POWER 的 lwarx/stwcx.）按定义在预留地址被写过之后让 SC 失败，写回相同的值也算，所以理论上不需要标签就能发现 ABA。但前提是 LL 在读 top->next 之前执行、SC 就是那次 CAS。C11 和 C++11 只暴露 CAS 接口，compare_exchange 编译出的 LL/SC 循环从 CAS 开始时才执行 LL，读 next 早在这之前就完成了，所以用标准原子操作写的 Treiber 栈在这些架构上照样需要标签或安全回收。

四、版本号不管内存回收

版本号只保证 CAS 不误判，管不了 pop 在 CAS 之前那次 p->next 读取。lfstack.c -i tagged -r free 把回收方式从”放进线程私有空闲链”改成 pop 成功后立刻 free()，其余代码不变。用 -fsanitize=address,undefined 构建、4 线程各 20 万次操作、5 个随机种子，5 次全部报告 heap-use-after-free，位置都是 tagged_try_pop 里读 p->next 的那一行（lfstack.c:129，results/sanitize.txt）。

交错很简单：线程 X 读到 old = {p, t}，还没读 p->next；线程 Y 弹出 p 并释放它；X 接着读 p->next，读的是已释放的内存。X 随后的 CAS 会因为版本号变化而失败，结果不会被采用，但读本身已经是未定义行为。在真实的分配器上，如果那一页已经还给操作系统，这次读就是段错误。

要安全地释放，有三类做法：

• 类型稳定的节点池：节点只在同类对象之间复用，数据结构存活期间从不还给系统。读到过期节点只会读到过期数据，由版本号兜底。HSY 2004 第 2.3 节用的是一个”只能由执行 pop 的线程归还”的节点池；Boost.Lockfree 的 stack 在类注释里写明节点被放回 freelist，“not returned to the OS before the stack is destroyed”；本文的 reproduce/ 也用这种方式。代价是内存峰值只升不降。
• 危险指针（hazard pointers）：Michael（IEEE TPDS 2004）让每个线程先公布自己将要解引用的指针，回收者扫描所有公布值后才释放。摘要里写明它只用单字读写、允许把内存还给操作系统，并且顺带给出只用单字指令的 ABA 解法：被保护的节点不会被释放，也就不会以同一地址重新出现。
• 基于纪元的回收（epoch-based reclamation）：线程进入和离开临界区时登记纪元，只有所有线程都越过某个纪元之后，才释放在那个纪元被摘下的节点。读路径开销更低，但一个停住的线程会让所有回收停下来。

后两种的机制和代价分别在本系列的 Hazard Pointers 和 Epoch-Based Reclamation 两篇展开，这里只记住一个结论：ABA 和回收是两个问题。版本号解决前者，节点池、危险指针、纪元回收解决后者；危险指针恰好能同时解决两者，所以用了它的栈可以退回到单字 CAS。

五、指数退避：失败之后先等一会儿

来源

退避不是为无锁栈发明的。Anderson 的 “The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors”（IEEE TPDS 1990）在共享内存多处理器上比较了自旋锁的几种等待方式，其中之一是获取失败后按指数增长的时间退避；Agarwal 和 Cherian 同年代的 “Adaptive Backoff Synchronization Techniques”（ISCA 1989）讨论了自适应退避。HSY 2004 实验里的 “Treiber with backoff” 就是在 Treiber 栈上加了 Anderson 那种指数退避，并称它是当时已知方法中最好的。

退避对 CAS 循环有效的原因在第三节已经出现：失败的 cmpxchg 也要把 cache line 拿到独占状态。一个失败的线程如果立即重试，就会把 line 从刚刚成功的线程那里抢走，而对方下一次操作又得抢回来。让失败者等一段随机时间，line 就能在成功者那里多停留几次操作。

实现

lfstack.c 的退避只有几行：窗口从 g_bo_min 开始，每失败一次在 \([0, \text{limit})\) 里均匀取一个值，执行这么多次 pause，然后窗口翻倍，直到 g_bo_max。每次操作开始时窗口复位。

static void backoff(tstat_t *ts, unsigned *limit) {
    unsigned d = (unsigned)(xorshift(&ts->rng) % *limit);
    for (unsigned i = 0; i < d; i++) cpu_relax();   /* __builtin_ia32_pause() */
    if (*limit < g_bo_max) *limit *= 2;
}

随机数用线程私有的 xorshift，不用 rand()：共享的随机数状态本身就会成为新的争用点。

实验环境与口径

这台机器上同时有其他任务在跑，吞吐数字只看相对趋势；CAS 失败次数和公平性比值不受时钟精度影响，但同样受调度干扰。

结果

吞吐中位数（Mops/s，括号里是每次操作的 CAS 失败次数和公平性比值，数据来自 results/bench.txt）：

三点观察：

1. 不退避的 Treiber 栈从 2 线程开始就不比锁好。单线程时四种实现都在 67 Mops/s 左右，一加第二个线程，tagged 掉到 24.4，4 线程时每次操作平均要失败 1.2 次 CAS，吞吐 14.7，略低于 mutex 的 17.7。“无锁”在这里只带来进度保证，没有带来吞吐。
2. 退避把 4 线程吞吐拉回到接近单线程的水平，靠的是让一个线程连续占用 cache line。backoff 的失败率降到每千次操作 3 次，吞吐 56.3。但公平性比值从 1 降到 0.58：最先完成的线程只用了最后完成者 58% 的时间。线程总数固定、每个线程的工作量相同，完成时间差这么多，说明某些线程长时间抢不到 top。
3. mutex 在 2 线程时最差（18.8），3 线程反而回升到 22.1，这个非单调现象在 5 次运行里都出现（2 线程范围 17.9 到 19.8，3 线程 21.6 到 22.3）。本文没有分析它的原因，只把它当作”锁的吞吐同样对线程放置敏感”的一个例子。

退避窗口上限的影响（4 线程，results/backoff_sweep.txt）：

上限越大，失败越少、吞吐越高，公平性越差；上限 4096 时最快的线程只用了最慢线程 28% 的时间。吞吐和公平性在这里是同一个旋钮的两端。这个取舍在不同机器上的位置不同：pause 的时延随微架构变化，cache line 在核间传递的代价随拓扑变化，所以窗口参数没有可移植的”最优值”。HSY 2004 为此让每个线程根据自己的成功率局部调整参数；后来的 TS 栈论文（POPL 2015）在两台机器上分别调优 EB 栈的配置和自己的延迟参数，延迟取值随机器不同而不同（该文第 6 节与 Table 1）。

六、消除退避栈

从消除树到”把消除当退避”

消除（elimination）的观察来自 Shavit 和 Touitou 的 “Elimination Trees and the Construction of Pools and Stacks”（SPAA 1995；Theory of Computing Systems 1997）：一次 push 紧跟一次 pop，栈的状态不变。如果一对 push 和 pop 能在栈之外碰面、直接交换数据，它们就不必碰 top。消除树把多层消除数组组织成树，但按 HSY 2004 的说法，它非阻塞却不满足线性一致性，另一条路线组合漏斗（combining funnels）线性一致却是阻塞的，两者都只在极高负载下才有优势。

Hendler、Shavit 和 Yerushalmi 的 “A Scalable Lock-free Stack Algorithm”（SPAA 2004；期刊版 JPDC 70(1)，2010）只用一个消除数组，而且只把它当退避：先在中央 Treiber 栈上尝试 CAS，失败了才去数组里随机挑一个位置等待配对，配对失败再回到栈上。低负载时几乎所有操作第一次就成功，数组不参与，延迟和普通 Treiber 栈一样；高负载时失败的操作越多，配对的机会也越多。论文证明了这个结构是无锁且线性一致的：在栈上完成的操作线性化在 CAS 处，一对被消除的 push 和 pop 线性化在碰面时刻，push 排在 pop 紧前面。

交换器

HSY 原文用两个按线程号索引的数组（location[] 和 collision[]）实现碰面。reproduce/lfstack.c 采用的是 Herlihy 和 Shavit 在 The Art of Multiprocessor Programming 里给出的简化形式：数组的每个槽位是一个交换器（exchanger），状态在 EMPTY、WAITING、BUSY 之间转换。

stateDiagram-v2
    [*] --> EMPTY
    EMPTY --> WAITING: first thread CAS, offers its item
    WAITING --> BUSY: second thread CAS, takes item, offers its own
    WAITING --> EMPTY: first thread times out, CAS withdraws offer
    BUSY --> EMPTY: first thread reads partner item, resets slot

push 提供节点指针，pop 提供 0。push 换回 0 说明遇到了 pop，操作完成；pop 换回非零值说明遇到了 push，拿到的就是那个节点。push 遇到 push、pop 遇到 pop 时交换照常发生，但双方都判定为失败，各自带着原来的东西回到栈上重试。槽位的高 64 位里除了 2 位状态还有一个序号，每次状态转换加一，用来防止槽位自身的 ABA。核心代码（exchange，删掉了注释）：

for (int i = 0; i < g_elim_spins; i++) {
    u128 cur = __atomic_load_n(slot, __ATOMIC_ACQUIRE);
    uint64_t seq = ex_seq(cur);
    switch (ex_state(cur)) {
    case EX_EMPTY:
        if (__atomic_compare_exchange_n(slot, &cur, mk(mine, seq + 1, EX_WAITING),
                false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)) {
            seq++;
            for (int j = 0; j < g_elim_spins; j++) {
                cur = __atomic_load_n(slot, __ATOMIC_ACQUIRE);
                if (ex_state(cur) == EX_BUSY) goto collided;
                cpu_relax();
            }
            u128 exp = mk(mine, seq, EX_WAITING);
            if (__atomic_compare_exchange_n(slot, &exp, mk(0, seq + 1, EX_EMPTY),
                    false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE))
                return false;
            cur = exp;
        collided:
            *theirs = ex_item(cur);
            __atomic_store_n(slot, mk(0, seq + 1, EX_EMPTY), __ATOMIC_RELEASE);
            return true;
        }
        break;
    case EX_WAITING:
        if (__atomic_compare_exchange_n(slot, &cur, mk(mine, seq, EX_BUSY),
                false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE)) {
            *theirs = ex_item(cur);
            return true;
        }
        break;
    default:
        break;
    }
    cpu_relax();
}
return false;

超时撤回的 CAS 失败只有一种可能：在 WAITING 状态下，只有配对方能把槽位改成 BUSY，所以 exp 里读回的一定是 BUSY 和对方的物品。BUSY 状态只由最先到达的线程复位，因此复位用普通的原子 store 就够了。被 pop 取走的节点所有权随之转移，push 一方不再碰它，这与 HSY 第 2.3 节”节点只由执行 pop 的线程归还”的约束一致。

论文里的数字与本机的数字

HSY 2004 的实验机器是 14 个 400 MHz UltraSPARC 处理器的 Sun Enterprise E6500（Solaris 9），负载是每线程 50 万次操作、push 和 pop 各半、栈预先填充到不会变空。论文报告：消除退避栈与 “Treiber with backoff” 的差距随线程数增大，32 线程时快了将近 3 倍（论文 Figure 7）；被成功消除的操作比例从 2 线程的 11% 升到 32 线程的 43%（论文 Table 2）。32 线程已经超过了 14 个处理器，也就是说最高负载点是超订的。

本机的结果（第五节的表，elim 一列）方向不同。默认配置是 2 个槽位、每次等待 64 轮 pause：

• 2 线程和 3 线程时，elim 的吞吐是 59.2 和 54.3，接近 backoff；但真正通过配对完成的操作只占 0% 和 0.32%。它快，是因为 CAS 失败后在槽位上等待的那段时间起到了时间退避的作用。
• 4 线程时，配对比例升到 9.2%，吞吐却降到 22.1，远低于 backoff 的 56.3。按 WSL2 报告的拓扑，4 线程里有两个线程在同一个核的两个超线程上。

换几组参数（4 线程，results/elim_sweep.txt）能把这两种效果分开：

配对比例最高的配置（1 个槽位）吞吐最低；吞吐最高的配置（4 个槽位、等 256 轮）几乎不配对，只剩等待。在只有 4 个线程的时候，一个线程在槽位里等到的多半不是互补操作，而等待本身的收益与第五节的退避相同。本文的实现也没有 HSY 的自适应宽度和等待时间。所以这组数据不能用来否定论文的结论，它说明的是：消除要在失败的操作足够多时才有配对可言，4 个逻辑 CPU 离论文的 32 线程很远。

后续工作：把消除放到哪里

Dodds、Haas 和 Kirsch 的 TS 栈（“A Scalable, Correct Time-Stamped Stack”，POPL 2015）在 x86 上与 Treiber 栈和 EB 栈做了比较，机器是 4 路 10 核 Xeon 和 4 路 16 核 Opteron。他们实现 EB 栈时有一处与 HSY 相反：先访问消除数组，再访问栈，并称这样扩展性更好。TS 栈本身走得更远：每个线程把元素压进自己的单生产者池并打上时间戳，并发压入的元素之间不排序，pop 时再找最年轻的元素；论文报告它在 x86 上比 EB 栈快约 2 倍。

另一条路线是合并（combining）。Hendler、Incze、Shavit 和 Tzafrir 的 “Flat Combining and the Synchronization-Parallelism Tradeoff”（SPAA 2010）让一个持锁线程替其他线程批量执行请求，摘要称在一个”不可忽略的并发度”以内，这种粗粒度同步比最好的细粒度实现更快，并据此构造了栈、队列和优先队列。消除减少的是对 top 的访问次数，合并减少的是争用同一 cache line 的线程个数，两者针对的是同一个瓶颈。

七、三个生产实现的取舍

Windows 的文档对历史有一段直白的说明：SList 在 32 位代码里容易实现，在 64 位代码里难，因为原生的 interlocked 交换宽度不是地址宽度的两倍；从 Windows 8 开始，64 位代码才有了 InterlockedCompare64Exchange128 这样的原生原语。这正是第三节”标签要么压进指针，要么用双字 CAS”的两难。

三者的共同点是都没有尝试在库内部解决”何时可以释放节点”。Linux 把它交给调用者和接口约束，Windows 交给调用者，Boost 用类型稳定的池回避它。通用的安全回收（危险指针、纪元回收）会给每次 pop 增加开销，这三个实现都把这笔开销留给真正需要它的调用者。

八、争论与开放问题

退避究竟该不该做，做在哪一层

Dice、Hendler 和 Mirsky 的 “Lightweight Contention Management for Efficient Compare-and-Swap Operations”（Euro-Par 2013；期刊扩展版 Concurrency and Computation: Practice and Experience 2014）问的是：软件层面的争用管理能否改进硬件 CAS 的效率？摘要给出的结论是，在中高争用下轻量的争用管理能大幅提升性能，低争用时开销通常很小。Morrison 和 Afek 的 “Fast Concurrent Queues for x86 Processors”（PPoPP 2013）走的是另一个方向：他们认为 CAS 重试循环本身就是问题，在 FIFO 队列里用总会成功的 fetch-and-add 分散线程，得到的 LCRQ 在 4 路 Xeon E7-4870 上比基于合并的队列快 1.5 到 2.5 倍。

这两篇针对的不是同一个数据结构，但立场可以对照：一方在 CAS 之上加管理，另一方换掉 CAS。本文的判断是，对栈来说后一条路更难走：LIFO 的”最新元素”没有像队列下标那样可以用 fetch-and-add 预先分配的位置；TS 栈用时间戳绕开全序，是目前这条路上有代表性的尝试。

吞吐与公平

第五节的数据里，退避把 4 线程吞吐从 14.7 提到 56.3，同时最快的线程只用了最慢线程 58% 的时间；窗口上限放到 4096 时这个比例降到 28%，相差 3.5 倍以上。无锁只保证系统整体前进，不保证每个线程前进；想要每个线程的操作步数有界，需要无等待（wait-free）算法。退避参数实际上是在吞吐和公平性之间选一个点，这个点随机器和负载漂移；在本文查到的文献里，还没有一个无需调参、在不同拓扑上都稳定的方案。HSY 的局部自适应和 Dice 等人的争用管理都是朝这个方向的尝试。

严格 LIFO 值不值

消除、合并和时间戳三条路线都在同一个问题上做文章：线性一致的栈要求所有操作在 top 上排成全序，这是串行瓶颈。TS 栈说明全序可以推迟到 pop 时再部分建立，但 pop 需要扫描所有线程的池；flat combining 说明在一定并发度以内，干脆让一个线程串行执行反而更快。如果应用只需要”大致后进先出”，放松语义可以换来更好的扩展性，但放松到什么程度仍然可以证明正确、又对应用有用，是仍在讨论的问题。

九、参考资料

规范与文档

• IBM, IBM System/370 Principles of Operation, GA22-7000-6, 1980, Appendix A, “Free-Pool Manipulation”, p. A-37.
• Intel, Intel 64 and IA-32 Architectures Software Developer’s Manual, Vol. 2A, “CMPXCHG—Compare and Exchange” 与 “CMPXCHG8B/CMPXCHG16B—Compare and Exchange Bytes”（在线转录：felixcloutier.com/x86/cmpxchg、felixcloutier.com/x86/cmpxchg8b:cmpxchg16b）。
• ISO/IEC 9899:2018（C17），7.17 “Atomics” 与 5.1.2.4 “Multi-threaded executions and data races”（release sequence 的定义）。
• Microsoft Learn, Interlocked Singly Linked Lists；InterlockedPopEntrySList；Singly and Doubly Linked Lists。
• Linux v6.12, Documentation/arch/x86/x86_64/5level-paging.rst。

源码

• Linux v6.12：include/linux/llist.h、lib/llist.c。
• Boost.Lockfree，tag boost-1.86.0：include/boost/lockfree/stack.hpp、detail/prefix.hpp、detail/tagged_ptr_dcas.hpp、detail/tagged_ptr_ptrcompression.hpp（github.com/boostorg/lockfree）。
• Vergilius Project, _SLIST_HEADER（Windows 11 23H2 x64，由公开符号整理的结构布局，非官方文档）。

核心论文

• R. K. Treiber, “Systems Programming: Coping with Parallelism”, IBM Almaden Research Center, Technical Report RJ 5118, April 1986（未见公开电子版，内容经 HSY 2004 等文献转述）。
• T. E. Anderson, “The performance of spin lock alternatives for shared-memory multiprocessors”, IEEE Transactions on Parallel and Distributed Systems 1(1), 1990, 6–16.
• D. Hendler, N. Shavit, L. Yerushalmi, “A scalable lock-free stack algorithm”, SPAA 2004, 206–215, doi:10.1145/1007912.1007944；期刊版 Journal of Parallel and Distributed Computing 70(1), 2010, 1–12.
• N. Shavit, D. Touitou, “Elimination trees and the construction of pools and stacks”, SPAA 1995, 54–63；期刊版 Theory of Computing Systems 30(6), 1997, 645–670.
• M. M. Michael, “Hazard pointers: safe memory reclamation for lock-free objects”, IEEE TPDS 15(6), 2004, 491–504.

其他论文

• A. Agarwal, M. Cherian, “Adaptive backoff synchronization techniques”, ISCA 1989, 396–406.
• M. P. Herlihy, J. M. Wing, “Linearizability: a correctness condition for concurrent objects”, ACM TOPLAS 12(3), 1990, 463–492.
• M. Herlihy, “Wait-free synchronization”, ACM TOPLAS 13(1), 1991, 124–149.
• M. M. Michael, M. L. Scott, “Simple, fast, and practical non-blocking and blocking concurrent queue algorithms”, PODC 1996, 267–275.
• M. M. Michael, “Safe memory reclamation for dynamic lock-free objects using atomic reads and writes”, PODC 2002, 21–30.
• D. Hendler, I. Incze, N. Shavit, M. Tzafrir, “Flat combining and the synchronization-parallelism tradeoff”, SPAA 2010, 355–364.
• A. Morrison, Y. Afek, “Fast concurrent queues for x86 processors”, PPoPP 2013, 103–112.
• D. Dice, D. Hendler, I. Mirsky, “Lightweight contention management for efficient compare-and-swap operations”, Euro-Par 2013, LNCS, 595–606；扩展版 Concurrency and Computation: Practice and Experience 26(14), 2014.
• M. Dodds, A. Haas, C. M. Kirsch, “A scalable, correct time-stamped stack”, POPL 2015, 233–246.

工程资料

• M. Herlihy, N. Shavit, V. Luchangco, M. Spear, The Art of Multiprocessor Programming, 2nd ed., Morgan Kaufmann, 2021, “Stacks and elimination” 一章。
• IBM, US Patent 4,482,956, 1984（申请 1982 年；背景部分转述了 PoO 的 Free-Pool Manipulation 示例）。

实验

• reproduce/lfstack.c：mutex、naive、tagged、backoff、elim 五种栈，守恒检查与吞吐测试。
• reproduce/aba_demo.c：用信号量排定交错，稳定复现 ABA，并对照带版本号的版本。
• reproduce/misaligned_cas.c：对未 16 字节对齐的地址执行 lock cmpxchg16b，观察到 SIGSEGV。
• reproduce/run.sh：构建（含 TSan、ASan+UBSan）并运行全部实验，默认 CPUS=2,11-13，单线程实验用列表里的第一个 CPU；结果写入 reproduce/results/。没有 clang 时跳过 clang 构建。TSan 若启动即报 unexpected memory mapping（地址随机化位数较大的内核），用 setarch -R ./run.sh 运行。
• reproduce/results/naive_stress_2vcpu.txt、sanitize_2vcpu.txt：同一脚本在 2 vCPU 虚拟机上的守恒与 sanitizer 结果，文件头记录环境。
• reproduce/plot_bench.py、reproduce/draw_figures.py：生成本文的吞吐图和示意图。

系列导航： - 上一篇：无锁队列：Michael-Scott 算法与 ABA 问题 - 下一篇：并发跳表：标记删除、乐观加锁与 ConcurrentSkipListMap

相关阅读： - Hazard Pointers：安全内存回收的优雅方案 - Epoch-Based Reclamation：Crossbeam 的实现之道 - RCU：宽限期的保证、读侧的三种实现与代价的去向