12、锁无关编程（Lock-Free）：CAS操作、ABA问题、无锁栈的实现

说到并发编程，很多人第一反应就是加锁。互斥锁、读写锁、条件变量……这些确实是经典方案。但我在实际项目中遇到过一种场景：锁的争用非常激烈，线程数一多，性能反而下降得厉害。这时候，锁无关编程就派上用场了。

说白了，Lock-Free 的核心思想就是：不让线程阻塞等待。如果某个线程的操作失败了，它自己重试，而不是让出 CPU。这样就不会出现「锁住等别人」的情况。

CAS 操作：Lock-Free 的基石

CAS 的全称是 Compare-And-Swap，也就是「比较并交换」。C++11 把它封装成了 compare_exchange_weak 和 compare_exchange_strong。这两个函数是原子操作，底层由 CPU 指令直接支持。

它的逻辑很简单：

bool compare_exchange_weak(T& expected, T desired);
bool compare_exchange_strong(T& expected, T desired);

我来解释一下：

  • 当前值与 expected 相等，就把值改成 desired，返回 true
  • 不相等，就把当前值写回 expected，返回 false

你想想看，这其实就是一条指令完成了「读-比较-写」三个步骤，而且不会被中断。这就是 Lock-Free 能实现的关键。

weak 和 strong 的区别

compare_exchange_weak 在某些平台上可能出现「伪失败」——明明值相等，却返回 false。而 compare_exchange_strong 保证不会伪失败。我个人的习惯是：在循环中使用 weak，因为它性能更好；在非循环场景用 strong，避免意外退出。

ABA 问题：一个隐蔽的陷阱

CAS 虽然好用，但有个经典坑——ABA 问题。我在几年前写一个无锁队列时就踩过这个坑，排查了好久。

什么是 ABA？举个例子：

  1. 线程 1 读取到共享变量值为 A
  2. 线程 1 被调度出去，线程 2 把 A 改成 B，又改回 A
  3. 线程 1 醒来，CAS 发现值还是 A，认为没被修改过，于是执行更新

问题就出在这里：值虽然没变，但状态已经变了。比如在无锁链表中，节点 A 可能已经被释放，又被重新分配，但地址恰好相同。CAS 以为节点没变，实际上它指向的内存已经不属于原来的对象了。

我曾经遇到的一个真实案例

在实现无锁栈时，我用 CAS 来操作栈顶指针。结果在高并发下偶尔出现段错误。排查了两天才发现是 ABA 问题——一个节点被弹出后又压入，地址相同但内容已经变了。后来用带标记的指针才解决。

解决 ABA：带标记的指针

最常见的方案是给指针加一个版本号或标记。每次修改指针时，标记也递增。这样即使地址相同，标记不同，CAS 也会失败。

C++ 里可以用 std::atomic<uintptr_t> 来打包指针和标记：

struct Node {
    int value;
    Node* next;
};

// 把指针和标记打包成一个 uintptr_t
// 低 48 位存指针，高 16 位存标记
std::atomic<uintptr_t> head;

bool push(Node* new_node) {
    uintptr_t old_head = head.load();
    new_node->next = reinterpret_cast<Node*>(old_head & 0xFFFFFFFFFFFF);
    
    uintptr_t new_head = (old_head & 0xFFFFFFFFFFFF) | 
                         ((old_head + 1) & 0xFFFF000000000000);
    
    return head.compare_exchange_weak(old_head, new_head);
}

嗯，这里要注意：不同平台指针的位数不同，打包方式要适配。我一般用 std::atomic<std::uintptr_t> 配合位运算，或者直接用 std::atomic<TaggedPointer> 结构体。

无锁栈的实现

有了 CAS 和 ABA 防护，我们就可以实现一个无锁栈了。核心思路是：用 CAS 原子地更新栈顶指针。

template<typename T>
class LockFreeStack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& val) : data(val), next(nullptr) {}
    };
    
    // 带标记的栈顶指针
    struct TaggedPtr {
        Node* ptr;
        uint64_t tag;
    };
    
    std::atomic<TaggedPtr> head_;

public:
    LockFreeStack() : head_({nullptr, 0}) {}
    
    void push(const T& value) {
        Node* new_node = new Node(value);
        TaggedPtr old_head = head_.load();
        
        do {
            new_node->next = old_head.ptr;
            TaggedPtr new_head = {new_node, old_head.tag + 1};
        } while (!head_.compare_exchange_weak(old_head, new_head));
    }
    
    bool pop(T& result) {
        TaggedPtr old_head = head_.load();
        
        while (old_head.ptr != nullptr) {
            TaggedPtr new_head = {old_head.ptr->next, old_head.tag + 1};
            if (head_.compare_exchange_weak(old_head, new_head)) {
                result = old_head.ptr->data;
                delete old_head.ptr;
                return true;
            }
        }
        return false;  // 栈为空
    }
};

这段代码里，push 和 pop 都用了一个 do-while 循环。为什么？因为 CAS 可能失败，失败了就重试。这就是 Lock-Free 的典型模式——乐观地尝试，失败了就再来一次。

个人经验

无锁栈的 pop 操作有个内存管理问题：删除节点时，其他线程可能还在访问它。我一般用延迟回收（如 Hazard Pointer 或 Epoch-Based Reclamation）来解决。不过为了示例简洁，这里直接 delete 了——生产环境千万别这么干。

知识体系总览

下面这张图总结了本章的核心逻辑：

锁无关编程（Lock-Free）知识体系 CAS 操作 compare_exchange_weak compare_exchange_strong ABA 问题 ABA 问题 带标记指针（TaggedPtr） 带标记指针（TaggedPtr） 无锁栈实现

性能对比：锁 vs 无锁

我整理了一份对比表格，方便你直观理解两者的差异：

特性 互斥锁 无锁 CAS
线程阻塞 会阻塞等待 不会阻塞，自旋重试
上下文切换 可能触发 不会触发
ABA 问题 不存在 存在，需额外处理
实现复杂度 低 高
适用场景 临界区大、操作耗时 临界区小、操作极快

说白了，无锁编程不是银弹。它适合那些操作非常短、锁争用激烈的场景。如果你的临界区里要做大量计算或 I/O，那还是老老实实加锁吧。

核心要点回顾

  • CAS 是 Lock-Free 的基础，compare_exchange_weak 适合循环，strong 适合非循环
  • ABA 问题是无锁编程的常见陷阱，用带标记的指针解决
  • 无锁栈的核心是 CAS 更新栈顶指针，配合循环重试
  • 内存管理是无锁数据结构的难点，生产环境需要 Hazard Pointer 或 RCU

嗯，这一章的内容就到这里。无锁编程的门槛确实比加锁高一些，但一旦掌握，你会发现它在高并发场景下的威力。下次遇到性能瓶颈时，不妨想想：能不能用 CAS 替代锁？

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

← 上一章 📖 返回目录 下一章 →