第45章无锁编程

课程目录第45章无锁编程

45. 无锁编程：CAS、ABA问题

无锁编程，听起来很酷对吧？说白了就是不用互斥锁、条件变量这些同步原语，直接靠CPU指令来保证线程安全。我刚开始接触这个领域时，觉得这简直是黑魔法——不用锁怎么保证数据不错乱？后来踩过几次坑才明白，无锁编程的核心就是一条指令：CAS（Compare-And-Swap）。

CAS 是什么？

CAS 是一条CPU原子指令。它的逻辑很简单：

bool compare_and_swap(int* ptr, int expected, int desired) {
    if (*ptr == expected) {
        *ptr = desired;
        return true;
    }
    return false;
}

注意，上面只是伪代码。真正的CAS是硬件级别的原子操作，中间不会被线程调度打断。C++11 把它封装在了 <atomic> 头文件里：

#include <atomic>

std::atomic<int> counter{0};

void thread_func() {
    int expected = counter.load();
    int desired = expected + 1;
    // 如果 counter 还是 expected，就更新成 desired
    while (!counter.compare_exchange_weak(expected, desired)) {
        // 失败说明别的线程改了，重新读取
        desired = expected + 1;
    }
}

你看，这里没有锁。多个线程同时执行这段代码，最终 counter 一定会正确累加。这就是无锁编程的基本模式。

核心要点：CAS 是乐观的——它假设冲突很少发生，先尝试更新，失败了就重试。而锁是悲观的——它假设冲突很多，干脆把门锁上不让别人进。

ABA 问题：一个隐蔽的陷阱

CAS 看起来很完美，但有一个经典陷阱——ABA问题。我在项目中遇到过一回，排查了整整两天才找到原因。

什么是ABA？看个例子：

// 假设有一个共享的栈顶指针 top
// 初始状态：top -> A -> B -> C

// 线程1 想 pop A：
// 它读到 top = A, A->next = B
// 然后 CAS(&top, A, B)  // 把 top 从 A 改成 B

// 但就在线程1 读到 A 之后、CAS 之前：
// 线程2 把 A 和 B 都 pop 了，栈变成空
// 线程2 又 push 了一个新节点 A'（恰好地址和 A 相同）
// 此时 top = A'（地址等于 A）

// 线程1 的 CAS 发现 top == A（地址相等），成功！
// 但 top 现在指向的是 A'，而不是 B
// 而 A'->next 指向的是垃圾数据...

为什么会这样？因为 CAS 只比较地址值，不关心地址指向的内容是否被改过。A 和 A' 地址相同，但语义完全不同。

注意：ABA 问题不是理论上的杞人忧天。我在一个高并发内存池项目里就栽过跟头——节点被回收后又重新分配，地址恰好相同，导致 CAS 误判成功，最终数据损坏。那一次线上事故让我记住了：无锁编程，细节是魔鬼。

如何解决 ABA 问题？

常见的解法有几种，我按推荐程度排个序：

方案	原理	适用场景
带标记的指针	在指针上附加一个版本号，每次修改都递增	通用，最常用
垃圾回收（GC）	延迟回收，确保节点不被复用	有 GC 的语言（Java、Go）
危险指针（Hazard Pointer）	每个线程标记正在访问的节点，延迟释放	C++ 无锁数据结构
RCU（Read-Copy-Update）	读时不加锁，写时复制，等待所有读完成再释放	读多写少的场景

我个人最常用的是带标记的指针。C++ 里可以用 std::atomic<uint64_t> 来打包指针和版本号：

// 假设指针在低48位，版本号在高16位
struct tagged_ptr {
    uint64_t ptr : 48;   // 指针
    uint64_t tag : 16;   // 版本号
};

std::atomic<uint64_t> atomic_top;

void push(Node* node) {
    uint64_t old_top = atomic_top.load();
    uint64_t new_top;
    do {
        // 提取指针部分
        Node* old_ptr = (Node*)(old_top & 0xFFFFFFFFFFFF);
        node->next = old_ptr;
        // 组合新值：指针 + 版本号+1
        new_top = ((uint64_t)node) | ((old_top + 1) & 0xFFFF000000000000);
    } while (!atomic_top.compare_exchange_weak(old_top, new_top));
}

你看，每次 CAS 成功，版本号都会递增。就算地址相同，版本号不同，CAS 也会失败。这样 ABA 问题就被绕过去了。

我的建议：如果你不是写底层库，尽量别自己造无锁数据结构。C++ 标准库里的 std::atomic、std::shared_ptr 的原子操作、以及 Intel TBB 等库已经封装得很好了。自己手写无锁代码，十有八九会漏掉边界情况。

无锁编程的适用场景

不是所有地方都适合用无锁。我总结了几条经验：

读多写少：无锁的读操作通常很快，适合缓存、计数器等场景
冲突概率低：CAS 失败重试的开销很小，但如果冲突频繁，重试次数多了反而比锁慢
数据结构简单：栈、队列、链表相对容易实现无锁版本；红黑树、哈希表就别想了
实时系统：无锁没有优先级反转问题，适合对延迟敏感的场景

嗯，这里要注意：无锁不等于无等待。CAS 循环本质上是一种忙等待，如果冲突严重，CPU 占用率会飙升。我在一个消息中间件里见过有人用无锁队列，结果压测时 CPU 跑到 100%，换成带锁的反而降下来了——因为锁会让线程休眠，不抢 CPU。

无锁编程的核心逻辑

下面这张图展示了无锁编程的核心流程和 ABA 问题的产生原因：

总结

无锁编程是一把双刃剑。用好了，性能可以碾压锁；用不好，bug 能让你怀疑人生。我个人建议：

能用锁解决的问题，先用锁。锁的性能没那么差，而且容易推理
如果确实需要无锁，优先用成熟的库，别自己造轮子
如果非要自己写，一定要考虑 ABA 问题、内存序、以及平台差异
测试！测试！测试！无锁代码的 bug 往往在极高并发下才出现，普通单元测试根本测不出来

我曾经在一个项目里用无锁队列替换了锁，性能提升了 3 倍，但调试时间花了整整两周。值不值？看场景吧。但至少现在，你知道了 CAS 和 ABA 问题，下次遇到类似场景，心里就有底了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

45. 无锁编程：CAS、ABA问题

CAS 是什么？

ABA 问题：一个隐蔽的陷阱

如何解决 ABA 问题？

无锁编程的适用场景

无锁编程的核心逻辑

总结