无锁编程（Lock-Free）：CAS、无锁结构、ABA、内存序落地

HPC/AI Infra 高频深度题。无锁 ≠ 无同步：它用 原子操作 + 正确内存序 取代「锁」，目标是减少争用、避免阻塞/上下文切换，靠 CAS/指针原子操作推进。

一、从锁到无锁：为什么 & 付出什么

	锁（mutex）	无锁（lock-free）
等待	阻塞睡眠（或自旋）	不阻塞；线程自旋/重试
争用成本	系统调用、上下文切换、缓存颠簸	主要是 CAS 失败重试 + cache line 争用
死锁	可能	天然无死锁
实现正确性	易写对	极难（内存序/ABA/生命周期回收）
适用	临界区长、低争用默认	临界区极短、超高并发计数器/队列

定义：若系统中至少有一个线程总能推进（不会因另一线程被抢占而全体卡死），则是 lock-free。更强的是 wait-free（每个线程有界步数内必然完成）。

二、CAS：compare_exchange（无锁的原子操作基石）

std::atomic<bool> flag{false};
// 想 "若 flag 为 false 则置 true" 
bool expect = false;
if (flag.compare_exchange_strong(expect, true)) {
    // 成功：flag 原来是 false，现在 true
} else {
    // 失败：expect 被更新为当前值 true
}

• compare_exchange_strong(expected, desired)：原子地「若当前==expected 则写 desired 返回 true；否则把 expected 更新为当前值返回 false」。
• compare_exchange_weak：可能虚假失败（硬件层面偶尔），常配 while 循环；strong 在 x86 上一样，Arm 上贵一点但要少写循环。
• compare_exchange 是 RMW（read-modify-write）原子，CPU 给 cache line 加独占锁（硬件一致性），不是全 cache 锁。

三、经典无锁结构实现（手写方向）

1. 无锁原子自增/计数器

std::atomic<long> cnt{0};
cnt.fetch_add(1);            // 就够，无需 CAS

2. 无锁栈（用 linked-list + CAS on head）——面试最常写

class LockFreeStack {
    struct Node { int data; Node* next; };
    std::atomic<Node*> head{nullptr};
public:
    void push(int v) {
        Node* n = new Node{v, head.load(std::memory_order_relaxed)};
        while (!head.compare_exchange_weak(n->next, n,
               std::memory_order_release, std::memory_order_relaxed)) {
            // 失败则 n->next 已被更新为最新 head，重试
        }
    }
    // pop 需解决"内存回收"——见 Hazard/epoch，简化略
};

要点：CAS 更新前先读 head 到本地 → CAS 时把本地当期望值，失败自动刷新 → 典型乐观并发模式。

3. 无锁队列（MPSC/MPMC）

• 实现复杂（head/tail 两个原子 + dummy node 让 head!=tail）。
• 生产级直接用现成库：Folly MPMCQueue / moodycamel::ConcurrentQueue / Boost.Lockfree / Intel TBB concurrent_queue。面试讲「单生产者-消费者可只用环形缓冲区单槽原子」，以及「为什么 MPMC 难：head/tail 双双竞争 + 回收」即可。

四、ABA 问题（必考）

问题：线程 A 读到 head=P；另一线程把 P pop 掉、新 push 了 P'（恰好地址又复用成 P）；A 的 CAS 以为 head 没变、成功把 P 当成当前节点操作 → 但 P 已被删除/复用，状态是陈旧的 → 破坏结构。

解法：

1. 带版本号的原子引用（tag/ABA-counter）：std::atomic 包不了两字用 <cstdint> 打 tag：如 x86 的 cmpxchg16b；或用指针低位当 tag。
2. 延迟回收（不让被删节点地址立即复用）：Hazard Pointer / Epoch-based reclamation（对 AI/无锁是实用话题）、RCU。
3. 讲话术：实际工程里给 CAS 操作带上单调 version，地址等于 + version 相等才算「未变」。

五、无锁与内存序结合（落地原则，勿背废）

在无锁栈 push 用 release（我写的数据对之后 acquire 的读者可见），pop 用 acquire：

Node* n = new Node; n->data = v;
n->next = head.load(relaxed);
while (!head.compare_exchange_weak(n->next, n, release, relaxed));

Node* h = head.load(acquire);   // 读到后，h 上数据可靠

规则速记：用 CAS/release 发布 "我已写好数据"，用 load/acquire 去读他人发布。绝大多数手写可先 seq_cst 写对，再谈优化放宽。

六、工程忠告（面试反向加分）

1. 无锁能不用就不用——先测锁是不是真瓶颈（perf 看 contention），锁不是瓶颈时无锁只添乱。
2. 真需要：优先原子计数 / 单生产者队列 / 现成库；别自己写 MPMC 无锁队列。
3. 校验正确性工具：TSan + -fsanitize=thread、libcds 测试、-fsanitize=undefined；按顺序存储再 validate。
4. HPC 语境常考的其实不是「手搓无锁」，而是「锁竞争多大 + 为什么用原子/权限分离/parititon 降低共享」。

七、快速自测

1. CAS 是原子的吗？在哪个粒度？（cache line 独占，RMW）
2. ABA 怎么破？（tag / hazard pointer / epoch）
3. 为什么 push 要 while CAS 而非 once？—— 竞争时期望值过期，失败需重读重试。
4. lock-free vs wait-free？（全局有人推进 vs 每人有界完成）