无锁编程与内存模型：CAS、ABA 与 happens-before

一句话定义

无锁（lock-free）编程不使用锁、仅凭原子指令（主要是 CAS）与明确定义的内存序（memory order）保证并发正确性；支撑它的是硬件内存模型给出的 happens-before 关系。

为什么重要

锁在高争用下退化成排队，且持有者被换出会拖垮全部等待者——内核热路径（调度器、引用计数、RCU）与高性能存储（无锁队列）因此转向无锁技术。同时它也是最容易写出"看起来对"代码的领域：不懂内存序，CAS 写得再多也只是在错误的地基上盖楼。

前置知识

kp-012（CAS 指令与缓存行争用）；kp-002（多核缓存一致性）。

核心概念

• 原子变量：atomic<T> / C11 _Atomic，读写与 RMW（read-modify-write）操作不可分割。
• 内存序：seq_cst（顺序一致，最直观最慢）、acquire/release（配对建立同步关系）、relaxed（只保原子性）。
• happens-before：若 A release、B acquire 同一变量且 B 读到 A 的写入，则 A 之前的所有写对 B 之后可见。
• ABA 问题：值从 A 变 B 又变回 A，CAS 检查失败——指针相等不代表状态未变。
• RCU（Read-Copy-Update）：读端零开销、写端复制替换后延迟回收的内核利器。
• progress 保证谱系：obstruction-free < lock-free < wait-free。

原理与机制

无锁栈的 push 是标准范例：

push(v):
  node = new Node(v)
  loop:
    old = head.load()
    node->next = old
    if (CAS(&head, old, node)) break    // head 仍是 old 才替换

pop:  同理 CAS 把 head 从 old 换成 old->next

为什么需要内存序：编译器与 CPU 都会乱序重排。线程1 执行 data = 42; ready.store(1, release)，线程2 执行 if (ready.load(acquire)) read(data)——release/acquire 配对禁止"store(1) 重排到 data=42 之前"，保证线程2 读到 42。若都用 relaxed，data 可能读到旧值：原子性保证单变量操作不可分割，内存序才保证跨变量的可见顺序。

ABA 修补：给指针伴随版本号（tagged pointer，把版本戳塞进指针空闲位或用 128 位双字 CAS），比较"指针+版本"整体；内核延迟回收（epoch/RCU）则从根上避免节点被复用。

图示

release/acquire 同步示意:
T1: data=42 ----release-> ready=1        (1 之前的写不许下沉)
T2: ready==1 --acquire-> read(data)=42   (读不许上浮)
           ^^^^^^^^^^^^^ 同步关系: T1 的写对 T2 可见

直观类比

seq_cst 像所有人在同一个公告栏按顺序贴条（全局排队，谁都能看懂）；acquire/release 像两地区各自贴墙、只在"约定暗号"那一刻同步墙上内容；relaxed 只保证"帖子贴上去就不会消失"，不保证别人何时看见。

实例或案例

内核级观察：cat /proc/sys/kernel/threads-max 之外，更直观的是引用计数与 RCU 的无处不在——perf top 里可见 refcount_add、rcu_read_lock 常驻热路径。用户态实验：写一个 CAS 自旋的原子计数器，与 kp-012 的互斥锁版本对比高争用吞吐（8 线程 × 10^7 次），lock-free fetch_add 通常显著领先，但把"计数器"换成"链表 push"后差距缩小——无锁不是免费午餐。

常见误区

• 认为原子操作天然线程安全一切：只保证单变量不可分割，复合逻辑仍需 CAS 循环与正确内存序。
• 用 volatile 替代同步：volatile 只禁止编译器优化该变量访问，不提供原子性与内存序（Java/C++ 语义有差异但均不足）。
• 认为 lock-free 一定更快：复杂的 CAS 循环在低争用场景可能输给一条加锁指令；选型看争用度与实时性需求。

与其他知识点的关系

硬件地基是 kp-002 的缓存一致性与 kp-012 的 lock 前缀；RCU 大量服务内核读路径（kp-005 的 PCB、kp-021 的 dentry 缓存）；内存序是 C/C++ 标准与硬件模型的契约。

延伸阅读

Adve & Gharachorloo 1996 教程；《C++ Concurrency in Action》第 5 章；Linux 内核文档 RCU 章节（Documentation/RCU）。

自测题

1. ABA 问题为什么危险，如何修补？

答：CAS 只比较值相等，指针被回收复用后 A-B-A 序列会让它误判"状态未变"；用版本号/tagged pointer 或延迟回收（epoch/RCU）修补。

1. acquire/release 与 relaxed 的本质差别？

答：acquire/release 在配对时建立 happens-before，保证临界数据跨线程可见；relaxed 只保证单次操作原子，不做任何顺序承诺。

1. RCU 为什么读端几乎零开销？

答：读者不加锁不写共享内存、只原子读指针；写者复制新版本原子切换，等所有旧读者离开（宽限期）后回收旧数据。