夜市的烧烤摊前永远排着长队，因为只有一位阿姨掌勺。排队的人不能自己动手，必须等阿姨叫号——这就是“锁”。有人挑菜慢，整条队都堵住；熟客来了还能插队；最糟的是阿姨中途离岗，所有人干等到天荒地老。后来老板把打菜窗口改成自助餐台：菜摆在那里，谁想拿就去拿，不用排队，但人人都得守规矩——夹菜前先看清盘子里是什么，确认没看错才动手，错了就放回去重新看；还要提防“菜被换过”的骗局，更要防止服务员把你正要用餐的盘子收走。无锁数据结构，就是计算机内存里的这座自助餐台：多个线程同时读写同一个队列或栈，不靠锁，靠原子操作与 CAS 指令保证正确性，靠版本号识破陷阱，靠 hazard pointer 与 epoch 决定“盘子什么时候能收”。这篇文章就从排队打饭讲到自助餐台，带你吃透无锁世界的规则、陷阱与代价。

岗位关联

掌握无锁数据结构，你就能跳出“并发=加锁”的惯性思维，看懂数据库、操作系统内核与高吞吐中间件里每秒处理百万请求的底层秘密，这是迈向资深并发工程师的必修课。

目录
  1. 可视化演示
  2. 锁的代价
  3. 原子操作
  4. CAS原语
  5. 无锁队列
  6. ABA问题
  7. 内存回收
  8. 权衡取舍
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

通过CAS原子操作流程、ABA问题成因与版本号解决、以及锁与无锁性能对比，展示无锁编程如何利用原子操作避免阻塞实现高并发吞吐。

本节配有交互动效（进入视口后自动加载，约 3KB）。

CAS原子操作流程 比较内存值与期望值相等则写入新值否则操作失败重试 CAS是无锁编程的基础原语保证原子性无需加锁 CAS(addr,old,new)→bool 原子操作是无锁数据结构的基石

锁的代价

回想烧烤摊的排队场景：阿姨一次只能接待一个人，其他人走不了，只能干等。更气人的是，后厨偶尔还夹塞——明明你在前面排着，熟客却先拿到了菜；如果阿姨突然被叫去后厨，整个队伍瞬间停摆。这就是互斥锁的日常：线程拿不到锁就被挂起睡眠，等锁释放再被唤醒，一来一回损失惨重。

在并发编程里，“排队”就是线程对共享数据的互斥访问。操作系统为了公平，会让没抢到锁的线程进入睡眠队列，这叫阻塞；等锁释放后再把它唤醒。每一次阻塞与唤醒，都伴随着一次上下文切换——CPU 要保存当前线程的全部状态，再加载另一个线程的状态，这些开销悄悄吞噬了并发本该带来的吞吐。

更隐蔽的是优先级反转：低优先级线程持有锁，高优先级线程却要等它，仿佛餐厅里被熟客插队；而如果两个线程互相持有对方需要的锁，又谁也等不到谁，这就是死锁。用公式看，一批并发任务在锁方案下的总耗时是：

排队制度本身没有错，错在“等人”的成本太高。无锁结构的目标不是消灭排队，而是取消那个唯一的“阿姨通行证”——让每个线程都能自己动手，不必等别人放行。

T总=∑i=1N(T临界区+T阻塞+T切换)T_{\text{总}} = \sum_{i=1}^{N} \left( T_{\text{临界区}} + T_{\text{阻塞}} + T_{\text{切换}} \right)
  1. 总耗时 T_总所有线程依次排队干活的总时间，锁竞争越激烈，这个值越大。
    T总T_{\text{总}}
  2. 线程数 N竞争同一把锁的线程个数，求和符号表示每个线程都要把三个分项走一遍。
    ∑i=1N\sum_{i=1}^{N}
  3. 临界区时间 T_临界区线程真正修改共享数据、非做不可的“正事”，这段无法省略。
    T临界区T_{\text{临界区}}
  4. 阻塞等待 T_阻塞拿不到锁被挂起睡眠的时间，锁被占得越久，等待越久。
    T阻塞T_{\text{阻塞}}
  5. 切换开销 T_切换阻塞时保存现场、唤醒时恢复现场两次上下文切换的代价。
    T切换T_{\text{切换}}

原子操作

自助餐台要运转，第一步是“售货机式”的铁板一块动作。想象一台自动售货机：投币、选货、出货是一气呵成的，绝不会出现“吞了币却没出货”或“出了货却没吞币”的半截状态——因为售货机的机械结构从物理上保证了这一步不可分割。

计算机内存也需要这样的“售货机”。当两个线程同时对一个内存单元做“读取—修改—写回”时，如果操作被拆开，就可能互相覆盖。硬件为此提供了一批原子读改写（RMW）指令，例如带 LOCK 前缀的加法、交换指令，它们让整个操作变成不可分割的整体，任何其他线程都无法在中间插一脚。

原子操作还有一种关键配套——内存屏障。现代 CPU 为了性能会乱序执行指令，还会把数据暂存在自己的高速缓存里。内存屏障相当于一个负责“全局广播”的传令兵，保证一个线程的写入能被其他线程及时看见。原子读改写可以用公式描述：

自动售货机不会半途卡壳，原子操作也一样。它们是无锁数据结构的“砖石”——有了这些不可分割的积木，我们才能搭建出更复杂的无锁算法。

RMW(P,f):v←∗P,∗P←f(v),return v\text{RMW}(P, f):\quad v \leftarrow *P,\qquad *P \leftarrow f(v),\qquad \text{return } v
  1. 内存地址 P指向共享内存单元的“货道编号”，所有线程都盯着这里。
    PP
  2. 读旧值先把当前值取出来，赋给局部变量 v。
    v←∗Pv \leftarrow *P
  3. 算新值基于旧值 v 计算出新结果，并写回同一地址。
    ∗P←f(v)*P \leftarrow f(v)
  4. 返回旧值把读到的旧值返回给调用者，整个操作一步完成。
    return v\text{return } v
  5. 不可分割硬件保证任意时刻都不会有线程看到“读到一半”的中间状态。
    RMW: 不可分割的单一操作\text{RMW: 不可分割的单一操作}

CAS原语

自助餐台真正的灵魂是一条规矩：“先看标签，再动手。”你以为盘子里是红烧肉，伸手去夹之前必须再确认一眼——还是红烧肉才夹走；如果发现是别的菜，就把手收回来，重新找目标。简单，但有效。

计算机把这套“看—比—换”做成了单条指令，叫比较并交换，也就是 CAS。线程先记下自己期望的值 E，然后执行 CAS：如果共享内存里当前的值恰好等于 E，就把新值 N 写进去；如果不等于，说明别人抢先改过了，这次不写，返回失败。CAS 的完整定义是：

CAS 失败后，线程通常不会傻等，而是立刻重读最新值再试一次，这叫自旋重试；如果竞争太激烈，还可以退避——稍微歇一歇再重试，避免一群人挤在一起互相干扰。在 RISC 架构上，硬件没有 CAS，但提供 LL/SC 两条指令配合：先“链接读”拿到值，再在“条件写”时核对这段地址没被动过，效果与 CAS 等价。

你看，自助餐的规矩只有一条，但所有人都遵守它，整个餐台就不需要管理员。CAS 就是那条规矩——无锁队列、无锁栈，千变万化的算法，根基都是这一条指令。

CAS(P,E,N)={∗P←N, trueif ∗P=Efalseotherwise\text{CAS}(P, E, N) = \begin{cases} *P \leftarrow N,\ \text{true} & \text{if } *P = E \\ \text{false} & \text{otherwise} \end{cases}
  1. 共享位置 P要修改的内存地址，相当于餐台上那个盘子。
    PP
  2. 期望值 E线程记忆里“盘子里应该是什么”，是与事实核对的标准。
    EE
  3. 新值 N确认无误后想写入的“我的菜”。
    NN
  4. 比较判断先检查 *P 是否等于 E，这是整个操作的灵魂。
    if ∗P=E\text{if } *P = E
  5. 写入并返回相等才写 N 并返回 true；不等则返回 false，线程进入自旋重试。
    ∗P←N, trueorfalse*P \leftarrow N,\ \text{true} \quad \text{or} \quad \text{false}

无锁队列

有了 CAS 这条规矩，老板把餐台升级成了传送带：厨师在传送带的一头放新菜（入队），顾客在另一头端走菜（出队）。两头各忙各的，互不排队。偶尔两个人同时伸手，撞在一起，按“先看标签”的规矩重来一次就行。

这就是无锁队列的基本图景。最经典的是 Michael-Scott 队列：它用两个指针，head 指向队首、tail 指向队尾。入队时，线程先创建一个新节点，把它链到当前 tail 指向的节点后面，再用 CAS 把 tail 推进到新节点；出队时，线程用 CAS 把 head 推进到下一个节点，拿走旧队首的数据。

一个精巧的细节是“哨兵节点”：队列永远保留一个不装数据的 dummy 节点，head 始终指向它。这样空队列也有一个确定的状态，避免了 head 和 tail 都指向 NULL 时，两个方向的 CAS 无从比较的尴尬。队列的不变量是：

更妙的是，如果某个线程入队刚把节点链上、还没来得及推进 tail 就被打断，其他线程看到 tail 落后，会主动“帮忙”把 tail 推进到正确位置——就像传送带上卡住的一盘菜，后面的人顺手把它往前推一把。正是这种互助，让队列在没有锁的情况下依然保持正确。

Q: head→dummy→n1→n2→⋯→tail,dummy 节点永不为空Q:\ \text{head} \to \text{dummy} \to n_1 \to n_2 \to \cdots \to \text{tail},\quad \text{dummy 节点永不为空}
  1. 队首指针 head指向哨兵节点，出队时推进它。
    head→dummy\text{head} \to \text{dummy}
  2. 哨兵节点 dummy不装数据的占位节点，让空队列也有确定形态。
    dummy 节点永不为空\text{dummy 节点永不为空}
  3. 中间节点链从 n1 到 tail 之间是真正排队等待被取走的元素。
    →n1→n2→⋯→tail\to n_1 \to n_2 \to \cdots \to \text{tail}
  4. 入队锚点新元素永远从 tail 一侧追加，再用 CAS 推进 tail。
    tail→CASnew_node\text{tail} \xrightarrow{\text{CAS}} \text{new\_node}
  5. 出队锚点取出 dummy 的下一个节点，用 CAS 推进 head。
    head→CAShead.next\text{head} \xrightarrow{\text{CAS}} \text{head.next}

ABA问题

传送带再顺畅，也藏着一个“红烧肉骗局”。你看见盘子里是红烧肉（A），放心地回头拿筷子；就在这一瞬间，服务员把这道菜端走、倒掉，又盛了完全一样的红烧肉放回原位。你转回身一看——还是红烧肉，于是放心夹走。但你不知道，这盘菜已经被动过手脚了。

计算机里，这种现象叫 ABA 问题。在线程 T1 读到一个指针 A 之后、执行 CAS 之前，线程 T2 把 A 弹出栈、又压入一个“新”的 A。由于新 A 与旧 A 的内存地址相同（内存分配器把刚释放的地址又还了回来），T1 的 CAS 发现“值还是 A”，就判定没人动过，于是成功写入——但此时栈的结构已经被 T2 改变，T1 的更新可能让其他节点凭空丢失。

破解红烧肉骗局的办法，是给每盘菜贴一张“版本标签”：每次有人动过这盘菜，标签数字就加一。CAS 比较时，不仅要比值，还要比版本号——值相同但版本号不同，说明中间被动过，这次操作作废。带版本号的 CAS 长这样：

硬件上，版本号方案往往体现为“双宽 CAS”：把指针和版本号打包成 128 位一次性比较交换；软件上，还有 hazard pointer 等方案从内存生命周期上消除 ABA 的根源。认清标签，红烧肉骗局就再也骗不了你。

CAS(P, (E,v), (N, v+1))\text{CAS}\big(P,\ (E, v),\ (N,\ v+1)\big)
  1. 值 E 与版本 v两个条件合成一把“复合钥匙”，缺一不可。
    (E,v)(E, v)
  2. 期望版本号 v线程读取瞬间记下的标签，代表“我要改的正是我看到的那一瞬间的版本”。
    vv
  3. 版本号递增每次成功写入，版本号从 v 变为 v+1，记录“被动过一次”。
    v+1v+1
  4. 双双匹配才写入值等于 E 且版本等于 v，才把新值 N 写进去。
    if ∗P=E and version=v\text{if } *P = E \ \text{and} \ \text{version} = v
  5. 失败即重试版本对不上，说明发生过 A→B→A 的复归，放弃这次操作重来。
    ABA 被识破，重试\text{ABA 被识破，重试}

内存回收

自助餐台还有最后一个难题：服务员什么时候能收走盘子？你正在夹菜，服务员却把盘子端走了，你会扑个空。所以餐台立了规矩：如果哪个顾客说“这盘菜我还要用”，服务员就在心里记下，绝不收走；等顾客用完说“不要了”，才允许收。

无锁结构里，这个“收盘子”问题叫内存回收。在锁方案里，节点弹出后立刻 free 是安全的，因为锁保证了没人在用；但在无锁世界里，一个线程可能在 CAS 之前刚刚读到了这个节点，另一个线程却已经把它弹出并释放了。前者再去访问，就是访问已释放的内存——程序崩溃或数据错乱。因此无锁结构必须“延迟回收”，确保没有任何线程还在引用时才能释放。

第一个成熟方案是 Hazard Pointer（危险指针）：每个线程把自己的引用登记到专属的“槽位”里，向全世界宣告“这个节点我在用，别收”。写入者要释放旧节点前，先扫描所有线程的槽位，确认没人指向它才动手。协议的核心是一个“先登记、再确认”的两步走：

另一个思路是“周期清台”，即 epoch（纪元）方案：把时间分成一个个周期，节点退役后先放进“冷藏柜”，等到两个周期过去，基本可以断定所有线程都已离开危险区，再统一释放。Linux 内核的 RCU 也是类似哲学——读端不登记，靠宽限期判断所有人都读完了。收盘子的规矩立好了，自助餐台才算真正完整。

HPi←P,CAS(P,P,N),retire(P)⇒扫描 HP 后释放\text{HP}_i \leftarrow P,\qquad \text{CAS}(P, P, N),\qquad \text{retire}(P) \Rightarrow \text{扫描 HP 后释放}
  1. 登记危险指针读取共享指针 P 之前，先把 P 写入线程私有的槽位 HP_i。
    HPi←P\text{HP}_i \leftarrow P
  2. 二次验证登记后重新读一次 P，发现被换过就立即停止，防止读到已回收节点。
    HPi≠P⇒放弃\text{HP}_i \neq P \Rightarrow \text{放弃}
  3. CAS 推进确认引用真实可靠后，执行 CAS 更新共享指针。
    CAS(P,P,N)\text{CAS}(P, P, N)
  4. 退役旧节点被替换下来的旧节点 P 进入“待回收”列表。
    retire(P)\text{retire}(P)
  5. 扫描后释放回收前遍历所有危险指针槽位，确认无人引用才真正 free。
    ∀i: HPi≠P⇒free(P)\forall i:\ \text{HP}_i \neq P \Rightarrow \text{free}(P)

权衡取舍

自助餐台这么高级，为什么还有烧烤摊在排队？因为不是所有场景都适合自助。夜宵摊就三四个人，阿姨动手比你快得多，搞自助反而要自己端盘找位；只有人山人海、排队成本高得离谱时，自助餐台才显示出价值。

无锁结构同理。它的前提是“排队成本”远高于“自助成本”：任务临界区短、竞争激烈、线程数多、锁切换开销巨大。此时用无锁，线程不再阻塞、不再有优先级反转与死锁，吞吐量能大幅提升。但如果竞争很弱，无锁的 CAS 重试、内存回收这些额外开销，反而可能比一把轻量锁还慢。

收益可以用一个比值来衡量：

无锁最大的隐性成本是“人”——代码难写、难调、难验证，ABA 与内存回收的坑一个接一个，常用的并发调试工具（如 TSan）对无锁的帮助也很有限。所以成熟的工程决策是：先测量，再决定。人多到排队排不起，才上自助餐台；否则，老老实实排队也是一种智慧。

收益=T锁=T临界区+T阻塞+T切换T无锁=T临界区+TCAS 重试+T回收\text{收益} = \frac{T_{\text{锁}} = T_{\text{临界区}} + T_{\text{阻塞}} + T_{\text{切换}}}{T_{\text{无锁}} = T_{\text{临界区}} + T_{\text{CAS 重试}} + T_{\text{回收}}}
  1. 分子 T_锁锁方案的总耗时，包含临界区、阻塞等待与两次切换。
    T锁=T临界区+T阻塞+T切换T_{\text{锁}} = T_{\text{临界区}} + T_{\text{阻塞}} + T_{\text{切换}}
  2. 分母 T_无锁无锁方案的总耗时，包含临界区、CAS 失败重试与内存回收。
    T无锁=T临界区+TCAS 重试+T回收T_{\text{无锁}} = T_{\text{临界区}} + T_{\text{CAS 重试}} + T_{\text{回收}}
  3. T_临界区两种方案都要付出的“正事”时间，它越短，无锁越占优。
    T临界区T_{\text{临界区}}
  4. 适用判据收益大于 1 说明无锁更划算，小于 1 说明锁更合适。
    收益>1⇒无锁更优\text{收益} > 1 \Rightarrow \text{无锁更优}

AI 应用场景

金融交易撮合系统里的无锁队列

阶段：高并发数据的多生产者多消费者调度（中间件设计）

解决的问题：证券交易撮合每秒要处理几十万笔订单，任何一次因锁阻塞产生的抖动都可能造成延迟尖峰。传统互斥队列在竞争激烈时，线程频繁睡眠唤醒，优先级反转还会让关键订单被低优先级任务卡住。无锁 MPMC 队列配合 CAS，让生产者与消费者各自推进，靠自旋重试替代阻塞，把延迟从毫秒级压到微秒级。

具体案例：某券商的核心撮合引擎用 Disruptor 式无锁环形队列替代锁队列后，单线程吞吐提升约 6 倍，99.9 分位延迟从 2ms 降到 30μs，不再出现因锁竞争导致的周期性延迟尖峰。

数据库索引与内存管理中的无锁结构

阶段：数据索引的并发维护与缓冲池管理

解决的问题：数据库的缓冲池、索引结构在多线程下要高并发读写，锁会让热点页成为瓶颈。Linux 内核与 PostgreSQL 大量使用 RCU 与无锁哈希表：读端无锁，写端通过版本号与宽限期回收旧副本，在“读多写少”场景下接近零竞争。

具体案例：PostgreSQL 的共享缓冲区分区锁与时钟扫描替换，在 64 核机器上显著摊薄竞争；JVM 的并发垃圾回收也借鉴 hazard pointer 思想，保证 GC 线程与应用线程并发而不互相踩踏。

高并发 AI 推理服务中的请求批处理队列

阶段：推理请求的异步攒批（dynamic batching）调度

解决的问题：GPU 推理服务要把多个请求攒成一个 batch 再喂给模型，多个前端线程同时往 batch 队列里放请求。用锁队列，高并发下线程频繁阻塞，GPU 因喂不满而闲置；换成无锁 MPSC 队列，各线程用 CAS 追加请求，攒批线程无锁消费，GPU 利用率明显提升。

具体案例：某 LLM 推理框架的 dynamic batching 模块把请求队列从 mutex 队列换成无锁 MPSC 队列后，吞吐提升约 40%，尾延迟更稳定，彻底消除了锁竞争导致的 GPU 空转。

Python 演示

python86 行
"""无锁数据结构演示:ABA 问题与版本号 CAS 方案"""  class Node:    """链表节点,address 模拟 C 语言里的内存地址"""    def __init__(self, value, address):        self.value = value        self.address = address        self.next = None  class AtomicRef:    """模拟共享内存单元,带版本号"""    def __init__(self, node):        self.node = node        self.version = 0  def cas_plain(ref, expected_addr, new_node):    """无版本 CAS:只比对地址是否相同"""    if ref.node.address == expected_addr:        ref.node = new_node        return True    return False  def cas_version(ref, expected_addr, expected_ver, new_node):    """带版本 CAS:地址与版本都匹配才写入"""    if ref.node.address == expected_addr and ref.version == expected_ver:        ref.node = new_node        ref.version += 1        return True    return False  def to_list(top):    """把栈打印成值列表,便于观察"""    items = []    while top is not None:        items.append(top.value)        top = top.next    return items  def demo():    addr_a, addr_b = 0x100, 0x200    a = Node("A", addr_a)    b = Node("B", addr_b)    a.next = b    top = AtomicRef(a)    observed_addr = top.node.address    observed_ver = top.version    print("初始栈:", to_list(top.node), "版本:", top.version)     # 线程 T2:先弹 A 再弹 B,然后压入一个"新"的 A    top.node = b    top.version += 1    top.node = None    top.version += 1    new_a = Node("A", addr_a)  # 模拟 malloc 复用了 0x100 地址    top.node = new_a    top.version += 1    print("T2 折腾后栈:", to_list(top.node), "版本:", top.version)     # 无版本 CAS:地址相同就被骗    ok = cas_plain(top, observed_addr, b)    print("无版本 CAS:", ok, "-> 栈:", to_list(top.node), "(B 早已被弹出,栈损坏!)")     # 重置场景,改用带版本 CAS    a.next = b    top.node = a    top.version = 0    observed_addr = top.node.address    observed_ver = top.version    top.node = b    top.version += 1    top.node = None    top.version += 1    top.node = new_a    top.version += 1    ok = cas_version(top, observed_addr, observed_ver, b)    print("带版本 CAS:", ok, "-> 栈:", to_list(top.node), "(版本 0 != 3,被识破)")  if __name__ == "__main__":    demo()
目的：用 Python 模拟 Treiber 无锁栈上的 ABA 问题，对比“只看地址的 CAS”与“携带版本号的 CAS”两种行为，直观展示为什么版本号能识破值复归的骗局。
  1. class AtomicRef:模拟一个带版本号的共享内存单元，相当于自助餐盘上的“版本标签”。
  2. def cas_plain(ref, expected_addr, new_node):只认内存地址是否相同，不关心这期间被改过几次，这正是 ABA 陷阱的根源。
  3. new_a = Node("A", addr_a)关键一行：模拟 malloc 把刚释放的 0x100 地址又还了回来，让新的 A 与旧的 A 地址相同。
  4. ok = cas_plain(top, observed_addr, b)地址相同就判定成功，把早已弹出的 B 写回栈顶，栈结构被破坏。
  5. def cas_version(ref, expected_addr, expected_ver, new_node):地址加上版本号双重校验，版本对不上就返回 False。
  6. ok = cas_version(top, observed_addr, observed_ver, b)期望版本 0 与实际版本 3 不符，CAS 失败，ABA 被识破。

常见误区

误区无锁数据结构听起来很高大上，是不是意味着任何线程任何时候都不用等，想操作就操作，丝滑无比？

正解不是。无锁意味着没有“阻塞式等待”——线程不会被挂起睡觉，但 CAS 失败时依然要自旋重试，也就是“忙等”。忙等不触发上下文切换、不会死锁或优先级反转，但会消耗 CPU 时间片。如果竞争极其激烈，CAS 一直失败，忙等的开销可能比锁的阻塞还大。

为何常见：“无锁”这个词太容易让人望文生义，以为把“锁”字去掉就万事大吉，忽略了自旋重试本质上也是一种等。

误区CAS 既然能原子地“比较并交换”，那把关键操作都换成 CAS，是不是再也不用锁了？

正解CAS 只保证“单步操作”的原子性，解决不了“多步操作”的一致性问题——先读 A 再 CAS 更新 B，两步之间别的线程可能已经把 A 改得面目全非；ABA 问题本身恰恰就发生在 CAS 的“比较”与“交换”之间。无锁算法还要处理 ABA、内存回收、协助推进等一堆衍生问题，难度远高于“把锁换成 CAS”。

为何常见：人容易把工具的能力夸大。CAS 是一块好砖，但盖高楼还需要梁柱和图纸，不能指望一块砖撑起整栋楼。

误区网上都说无锁性能好，那我写队列、写栈、写计数器，全部上无锁，肯定比加锁快吧？

正解无锁的性能优势只在“竞争激烈 + 临界区短”时明显。低竞争场景下，CAS 重试、内存回收、缓存行乒乓这些开销会让无锁实现输给一把轻量锁甚至原子变量。工程上应当先压测：临界区多长、竞争多高、延迟要求多严，让数据说话，而不是拍脑袋上无锁。

为何常见：性能对比往往只看宣传中的极端场景，忽略了“收益比公式”里的适用条件——就像夜宵摊只有三个人时，自助餐台反而不如阿姨打菜方便。

误区版本号不是能识破 ABA 吗？那旧节点应该可以随便释放了吧？

正解版本号只解决“值复归”的判断，不解决“内存生命周期”。即使带版本号的 CAS 失败了，其他线程可能正握着旧节点的引用准备访问，此刻 free 它，依然会悬空。内存回收必须靠 hazard pointer、epoch 或 RCU 这类专门机制，先保证“没人引用”再释放。两件事是两码事，不能混为一谈。

为何常见：初学者容易把 ABA 与内存回收搅在一起，以为一个版本号包治百病，忽略了它们解决的是不同层面的问题。

面试题

Q1. 无锁数据结构的核心硬件原语是什么？

单选题 · easy

  • A.互斥锁
  • B.比较并交换（CAS）← 正确答案
  • C.信号量
  • D.读写锁

答案：B。无锁结构不靠锁，靠硬件提供的原子指令。CAS 是其中最核心的“先比较后交换”原语，互斥锁、信号量、读写锁本质上都是锁机制的变体，与“无锁”的理念相对。

Q2. ABA 问题中的“复归”指的是什么？

单选题 · easy

  • A.值从 A 变成 B，又变回 A← 正确答案
  • B.两个线程的数值相加溢出
  • C.CPU 缓存行被替换
  • D.线程栈空间不足

答案：A。ABA 的核心是“值复归”：共享值先被改成 B，再被改回 A。CAS 只比较当前值，看到 A 就以为没人动过，实际上中间已经被改过一轮，就像红烧肉被换过盘却看起来一样。

Q3. 相比互斥锁，无锁数据结构避免了哪些问题？

多选题 · mid

  • A.线程阻塞与唤醒← 正确答案
  • B.优先级反转← 正确答案
  • C.死锁← 正确答案
  • D.数据位翻转

答案：ABC。无锁结构里线程拿不到 CAS 结果就自旋重试，不会被挂起，因此没有阻塞唤醒、优先级反转和死锁。但数据位翻转属于硬件层面的存储错误，与用不用锁无关。

Q4. 工程中最常用的 ABA 解决方案是？

单选题 · mid

  • A.加大锁粒度
  • B.带版本号/标签的 CAS← 正确答案
  • C.扩大缓冲队列
  • D.关闭 CPU 缓存

答案：B。给共享值附加一个每次修改都递增的版本号，CAS 时同时比较值与版本，就能识破“值复归”。加大锁粒度是锁方案的思路，扩大缓冲与关闭缓存都解决不了“值复归”本身。

Q5. 以下哪些属于无锁结构的内存回收方案？

多选题 · mid

  • A.Hazard Pointer← 正确答案
  • B.Epoch（纪元回收）← 正确答案
  • C.RCU← 正确答案
  • D.自旋锁

答案：ABC。Hazard Pointer 靠登记危险指针延迟释放，Epoch 靠周期划分宽限期，RCU 靠宽限期判断读端全部离场，三者都是无锁内存回收方案。自旋锁是锁机制，与内存回收无关。

Q6. Michael-Scott 无锁队列为什么需要 dummy 哨兵节点？

单选题 · mid

  • A.减少队列占用的内存总量
  • B.避免空队列时 head 与 tail 指向 NULL 导致的 CAS 歧义← 正确答案
  • C.加速 CPU 缓存预取
  • D.用来存放队列长度信息

答案：B。空队列如果没有 dummy 节点，head 和 tail 都指向 NULL，入队与出队的 CAS 就失去了稳定的比较基准。dummy 节点让空队列也有确定形态，这与减少内存或缓存预取无关。

Q7. Treiber 无锁栈 pop 操作中 ABA 问题的直接来源是？

单选题 · hard

  • A.被弹出的节点地址被 malloc 复用← 正确答案
  • B.栈顶元素的值发生了数值溢出
  • C.CAS 指令的机器码出错
  • D.栈的容量不够

答案：A。pop 先读到栈顶 A，随后 T2 弹出 A 和 B 又压入新节点，内存分配器把刚释放的 A 的地址又分配给新节点。T1 的 CAS 发现地址“还是 A”就成功，但栈结构早已改变。这是内存地址复用导致的“值复归”，与数值溢出、指令错误无关。

Q8. 在无锁队列中，如果入队线程推进 tail 到一半被打断，其他线程应该怎么做？

多选题 · hard

  • A.发现 tail 落后时主动协助推进 tail← 正确答案
  • B.自己的入队操作重试← 正确答案
  • C.必须等待原线程被唤醒后才能继续
  • D.直接修改 head 来补偿

答案：AB。无锁队列允许任何线程发现 tail 落后时帮忙 CAS 推进它（协助机制），同时自己的操作失败后自旋重试。等待原线程唤醒是锁的思路；修改 head 与修复 tail 落后无关，会破坏队列结构。

Q9. 哪种场景下无锁数据结构的收益最明显？

单选题 · extreme

  • A.低竞争、临界区很长
  • B.高竞争、临界区很短← 正确答案
  • C.单线程顺序访问
  • D.读多但从不写

答案：B。高竞争下锁的阻塞与切换成本巨大，短临界区又让“正事”时间占比小，无锁的自旋重试反而能压出高吞吐。低竞争时锁的切换成本小，无锁的额外开销反而吃亏；单线程和无写入场景根本不需要无锁。

Q10. 关于 Hazard Pointer 协议，下列说法正确的是？

多选题 · mid

  • A.读取共享指针之前要先登记到自己的槽位← 正确答案
  • B.登记之后就可以立刻释放旧节点
  • C.登记后需要二次验证，防止读到已回收节点← 正确答案
  • D.它可以完全消除 ABA 问题

答案：AC。Hazard Pointer 的核心是先登记再使用，登记后还要重新验证指针是否被改过，防止读到已回收内存。它解决的是“内存生命周期”问题，而 ABA 需要版本号等机制来消除，所以 D 错误；登记后恰恰不能立刻释放，B 也错误。