无锁内存池：CAS操作、ABA问题、Hazard Pointer与RCU

好，咱们进入第三个核心话题——无锁内存池。

前面我们聊了内存池的基础设计，也聊了多线程加锁带来的性能损耗。你想想看，在高频交易场景下，一个锁的争抢可能就让你的订单延迟从微秒级跳到毫秒级。这谁能忍？

所以，无锁（Lock-Free）就成了我们必须啃下的硬骨头。

3.1 CAS操作：无锁的基石

无锁编程的核心武器，就是CAS（Compare And Swap）。

说白了，CAS是一条CPU指令，它干的事很简单：比较某个内存地址的值，如果等于期望值，就把它换成新值。整个过程是原子的。

我个人的习惯是，把CAS想象成一个“乐观锁”。它不阻塞线程，而是让线程去“尝试”更新。成功了就继续，失败了就重试。

// 伪代码：CAS操作
bool compare_and_swap(int* ptr, int expected, int new_value) {
    if (*ptr == expected) {
        *ptr = new_value;
        return true;
    }
    return false;
}

在C++11里，标准库提供了std::atomic，我们可以直接用compare_exchange_weak或compare_exchange_strong。

#include <atomic>

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

void increment() {
    int old = counter.load();
    // 循环直到CAS成功
    while (!counter.compare_exchange_weak(old, old + 1)) {
        // 如果失败，old会被更新为当前值，继续重试
    }
}

3.2 ABA问题：一个隐蔽的陷阱

CAS虽然好用，但有个经典陷阱——ABA问题。

什么意思呢？线程1读到变量A，准备CAS。但在这期间，线程2把A改成了B，又改回了A。线程1的CAS一看，嗯，还是A，于是成功更新。但线程1不知道，这个A已经“变过心”了。

我在项目中遇到过这个坑。当时实现一个无锁栈，pop操作里用CAS修改栈顶指针。结果在高并发下，偶尔会出现节点被重复释放的bug。查了两天才定位到是ABA问题。

解决ABA问题的常见方法有两种：

• 带标签的指针（Tagged Pointer）：在指针的高位或低位附加一个版本号。每次修改指针时，版本号+1。这样即使指针值相同，版本号不同，CAS也会失败。
• 使用双字CAS（DCAS）：同时比较并交换两个连续的内存单元，比如指针和版本号。但DCAS在x86上支持有限，不如单字CAS高效。

// 带标签的指针示例
struct TaggedPointer {
    uintptr_t ptr : 48;  // 低48位存指针
    uintptr_t tag : 16;  // 高16位存版本号
};

std::atomic<TaggedPointer> head{nullptr, 0};

void push(Node* node) {
    TaggedPointer old = head.load();
    TaggedPointer new_val{node, old.tag + 1};
    while (!head.compare_exchange_weak(old, new_val)) {
        new_val.tag = old.tag + 1;
        new_val.ptr = node;
    }
}

3.3 Hazard Pointer：安全的回收机制

解决了ABA问题，下一个难题来了：内存回收。

在无锁数据结构里，一个线程正在读某个节点，另一个线程却把它删了。怎么办？

Hazard Pointer（危险指针）就是干这个的。

核心思想很简单：每个线程维护一个“危险指针列表”，里面记录它当前正在访问的节点地址。其他线程在释放节点前，先检查这个节点是否在某个线程的危险指针列表里。如果在，就延迟释放。

我个人的实现习惯是这样的：

1. 每个线程有一个线程局部的Hazard Pointer数组，大小固定（比如4个）。
2. 读节点前，把节点地址写入Hazard Pointer。
3. 读完后，清空Hazard Pointer。
4. 要删除节点时，遍历所有线程的Hazard Pointer，如果没人引用，就真的释放；否则把节点加入“待回收列表”。

// Hazard Pointer 简化实现
thread_local HazardPointer hp[4];

void* read_node(std::atomic<void*>& ptr) {
    void* node;
    do {
        node = ptr.load();
        hp[0].set(node);  // 标记为危险
    } while (ptr.load() != node);  // 检查是否被修改
    return node;
}

void retire_node(Node* node) {
    // 检查所有线程的Hazard Pointer
    for (auto& hp : all_hazard_pointers) {
        if (hp.get() == node) {
            // 还有人用，延迟释放
            deferred_list.push(node);
            return;
        }
    }
    delete node;  // 安全释放
}

3.4 RCU：读多写少的终极方案

最后聊聊RCU（Read-Copy-Update）。

RCU是Linux内核里广泛使用的同步机制，特别适合读多写少的场景。比如路由表、配置信息，这些数据读的频率远高于写。

RCU的核心思想是：读者不需要任何锁，写者通过“复制-更新-延迟回收”来保证一致性。

具体流程是这样的：

• 读：直接读取指针，不需要加锁。但需要保证在读的过程中，指针指向的内容不会被释放。
• 写：先复制一份数据，在副本上修改。然后原子地更新指针，指向新副本。
• 回收：等待所有正在读旧数据的线程完成，然后释放旧数据。

这个“等待所有读者完成”的机制，在RCU里叫宽限期（Grace Period）。

在C++里实现RCU，通常需要借助std::atomic和线程本地计数器。下面是一个极简的示例：

class RCUProtectedData {
    std::atomic<Data*> ptr_;
    std::atomic<int> readers_{0};

public:
    Data* read_begin() {
        readers_.fetch_add(1, std::memory_order_acquire);
        return ptr_.load(std::memory_order_relaxed);
    }

    void read_end() {
        readers_.fetch_sub(1, std::memory_order_release);
    }

    void update(Data* new_data) {
        Data* old = ptr_.exchange(new_data, std::memory_order_acq_rel);
        // 等待所有读者完成
        while (readers_.load() != 0) {
            std::this_thread::yield();  // 实际中可以用更高效的方式
        }
        delete old;
    }
};

3.5 知识体系总览

为了让你更直观地理解这些概念的关系，我画了一张图：

这张图把四个核心概念串起来了。CAS是基础工具，ABA是必须避开的坑，Hazard Pointer和RCU是两种不同的安全回收策略。你根据场景选就行。

好了，这一章的内容就到这里。无锁编程确实有门槛，但一旦掌握，性能提升是立竿见影的。我建议你从简单的无锁栈开始练手，慢慢过渡到内存池。