C++无锁编程详解(经典案例)_C/C++

c++无锁编程（lock-free programming）是一种不依赖传统互斥锁（如 std::mutex）来实现线程安全的技术，其核心目标是‌避免线程阻塞、死锁和优先级反转‌，并提升多核环境下的可伸缩性。它并非“完全不用同步”，而是将同步粒度下沉到cpu提供的‌原子操作‌和‌内存序‌层面。

c++无锁编程详解

一、引言：为什么需要无锁编程？

在多核并发场景下，传统的互斥锁（如 std::mutex）通过阻塞线程来保护共享资源，虽然直观，但存在明显问题：

性能瓶颈：高并发时，锁竞争导致线程频繁阻塞和唤醒，引发上下文切换，开销巨大。
死锁风险：多个线程相互等待对方释放锁，可能导致程序永久停滞。
优先级反转：低优先级线程持锁，高优先级线程等待，影响实时性。

无锁编程（lock-free programming） 作为一种替代方案，通过底层的原子操作和内存模型来保证线程安全，避免了锁的上述缺陷，能显著提升高并发场景下的性能和可扩展性。

二、核心概念辨析：无锁、无等待与无阻碍

在深入技术之前，需要区分三个容易混淆的概念：

无锁（lock-free）：系统整体保证进度。即无论发生什么，至少有一个线程能在有限步骤内完成操作。这是最常用的目标。
无等待（wait-free）：每个线程都能在有限步骤内完成操作，有最强的实时性保证，但实现极其复杂。
无阻碍（obstruction-free）：在没有竞争时，线程能独立完成。这是最弱的一种保证。

日常讨论的“无锁编程”，大多指达到 “无锁（lock-free）” 级别。

三、无锁编程的基石：c++ 原子操作

无锁编程依赖于硬件支持的、不可中断的原子操作。

1.std::atomic类型

c++11 起，标准库提供了 std::atomic<t> 模板，将普通变量变为原子变量。对其进行的操作（如 load, store, fetch_add）是原子的，无需锁即可保证线程安全。

#include <atomic>
std::atomic<int> counter(0);
counter++; // 原子递增，线程安全

2. 核心武器：cas 操作

比较并交换（compare-and-swap, cas） 是无锁编程的基石。它原子地执行：“如果当前值等于期望值，则将其更新为新值；否则，不做任何事”。

c++ 中通过 std::atomic::compare_exchange_weak/strong 实现。weak 版本可能“假失败”（在少数架构上），通常在循环中使用。

cas 是实现无锁数据结构的关键，其典型使用模式是“循环重试”：

四、无锁编程的灵魂：c++ 内存模型

原子操作保证“原子性”，但不保证“可见性”和“顺序性”。由于cpu和编译器的优化，不同线程看到的内存操作顺序可能不同。c++ 内存模型通过内存顺序（memory order） 参数来控制这些行为-。

常用的内存顺序有：

memory_order_relaxed (松散)：仅保证操作的原子性，不提供任何同步或顺序保证。最快，适用于纯计数器等简单场景。
memory_order_acquire (获取)：用于读操作。保证当前线程中，该读操作之后的读写操作不会被重排到该读操作之前。能“看到”其他线程释放（release）操作之前的所有写入。
memory_order_release (释放)：用于写操作。保证当前线程中，该写操作之前的读写操作不会被重排到该写操作之后。其效果会“发布”给后续获得（acquire）该变量的线程。
memory_order_acq_rel (获取-释放)：用于读-改-写操作（如cas），兼具 acquire 和 release 的效果。
memory_order_seq_cst (顺序一致性)：最强的顺序，提供全局一致的操作顺序，但性能开销最大。

核心原则：release 与 acquire 必须配对使用，才能建立 happens-before 关系，保证线程间数据的可见性。

五、经典案例：实现一个无锁栈

以最简单的无锁栈（lock_free_stack）为例，展示如何应用上述概念。

template<typename t>
class lock_free_stack {
private:
    struct node {
        t data;
        node* next;
        node(const t& data) : data(data), next(nullptr) {}
    };
    std::atomic<node*> head; // 原子指针指向栈顶
public:
    void push(const t& data) {
        node* new_node = new node(data);
        new_node->next = head.load(std::memory_order_relaxed);
        // 使用 cas 将新节点设为栈顶，失败则重试
        while (!head.compare_exchange_weak(new_node->next, new_node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed));
    }
    std::shared_ptr<t> pop() {
        node* old_head = head.load(std::memory_order_acquire);
        while (old_head && 
               !head.compare_exchange_weak(old_head, old_head->next,
                                           std::memory_order_release,
                                           std::memory_order_relaxed)) {
            // 循环重试，重新加载 head
        }
        if (!old_head) return nullptr;
        std::shared_ptr<t> res = std::make_shared<t>(old_head->data);
        delete old_head; // 注意：此处存在内存管理问题（见下文）
        return res;
    }
};

代码解析：

push：创建节点，用 cas 尝试更新 head。使用 memory_order_release 确保新节点数据对其他线程可见。
pop：用 cas 尝试将 head 指向下一个节点。使用 memory_order_acquire 确保能看到其他线程 push 的数据。

六、无锁编程的常见挑战与陷阱

aba 问题：cas 操作中，值从 a 变为 b 又变回 a，cas 会误认为没变过。常见于内存重用场景。解决方案：使用带版本号的指针（如 std::atomic<std::pair<void*, size_t>>）或垃圾回收机制。
内存管理困难：如上例 pop 中 delete old_head 是危险的。其他线程可能正通过 cas 读取该节点。常用技术包括 hazard pointers（风险指针）或 epoch based reclamation（基于时代的回收）。
实现极其复杂：无锁算法的正确性难以推理和验证，存在许多微妙的并发问题。
并非总是更快：在低并发场景下，无锁算法的循环重试和复杂内存管理开销可能不如互斥锁高效。

七、c++ 无锁编程资源与库

标准库：<atomic> 提供基础原子操作。可用 atomic_var.is_lock_free() 检查该类型在当前平台是否真正无锁-。
boost.lockfree：提供了 boost::lockfree::queue 和 boost::lockfree::stack 等现成的无锁容器-。
开源实现：
- concurrentqueue：一个高性能的多生产者多消费者（mpmc）无锁队列。
- readerwriterqueue：一个高速的单生产者单消费者（spsc）队列。
- mpsc-queue：vyukov 的多生产者单消费者（mpsc）队列实现。

总结

c++ 无锁编程是追求极致性能的利器，但也是复杂度极高的领域。它要求开发者深入理解原子操作、内存模型，并能妥善处理 aba、内存管理等问题。

何时使用？

适合：超高并发、对延迟极度敏感的核心路径（如高频交易、游戏引擎、网络框架）。
不适合：一般业务逻辑、低并发场景。此时，使用互斥锁是更安全、更明智的选择。

建议先从 std::atomic 和基本内存顺序开始实践，理解其原理，再逐步挑战更复杂的无锁数据结构设计。

aba问题详解

一、回顾：aba问题是什么？

aba问题是无锁编程中，使用cas（比较并交换） 操作时可能遇到的一个隐蔽陷阱。

简单来说，它的核心在于：一个线程在两次读取同一内存位置之间，该位置的值从 a 变成了 b，最后又变回了 a。 由于cas只比较最终值是否仍为 a，它会认为数据没有被修改过，从而错误地执行更新操作，尽管数据的中间状态（b）已经发生了变化。

可以用一个生活中的例子来理解：

你等红灯时看了一眼，是红灯（a）。低头玩了一会儿手机，再抬头看，还是红灯（a）。你因此得出结论，红灯一直亮着。但实际上，在你低头期间，红灯可能已经变成了绿灯（b），又变回了红灯（a），完成了一个完整的红绿灯周期。

在无锁编程中，这个“被骗”的后果可能导致数据结构的破坏或程序崩溃。

二、aba问题如何发生？一个具体的例子

以最常见的无锁栈为例：

线程t1 读取栈顶指针，发现它指向节点 a，并准备执行cas操作，将栈顶从 a 更新为 a 的下一个节点 b。
在t1执行cas之前，线程t2 抢占了cpu并完成了一系列操作：
- 从栈中弹出节点 a。
- 接着又推入了两个新节点，最后将节点 a 重新推回栈顶。
- 此时，栈顶指针又指向了 a。线程t1 恢复执行，它的cas操作发现栈顶仍然是 a，与预期相符，于是成功地将栈顶更新为它之前保存的 b 节点。

问题发生了：此时栈顶被错误地指向了一个可能已经被删除或重新用于其他目的的内存地址（b），导致数据结构损坏。

三、c++中解决aba问题的常见方案

解决aba问题的核心思想是：让cas操作不仅能比较“值”，还能比较一个“版本号”或“标记”，确保值和状态都未发生变化。

方案一：带标记的指针（tagged pointer）——最常用

这是最通用、最有效的解决方案。它将一个递增的版本号（tag/counter） 与指针捆绑在一起，形成一个原子变量。每次修改指针时，版本号都必须一起更新。

c++中可以通过组合std::atomic与一个结构体来实现：

#include <atomic>
#include <cstdint>
// 1. 定义一个结构体，包含指针和版本号
struct tagged_ptr {
    void* ptr;
    uintptr_t tag; // 版本号，每次修改时递增
};
// 2. 使用 std::atomic 包装这个结构体
std::atomic<tagged_ptr> atomic_head;
void push(node* new_node) {
    tagged_ptr old_head = atomic_head.load();
    tagged_ptr new_head;
    new_head.ptr = new_node;
    new_head.tag = old_head.tag + 1; // 新头的版本号递增
    new_node->next = static_cast<node*>(old_head.ptr);
    // cas 操作会比较整个 tagged_ptr 结构体
    // 只有当 ptr 和 tag 都匹配时，才会更新
    while (!atomic_head.compare_exchange_weak(old_head, new_head)) {
        // 如果失败，重新读取最新的 head，更新 new_head 并重试
        new_head.ptr = new_node;
        new_head.tag = old_head.tag + 1;
        new_node->next = static_cast<node*>(old_head.ptr);
    }
}

注意事项与变种：

双倍宽度的cas（double-width cas）：如果指针和版本号加起来超过一个机器字（例如，64位系统上指针+64位计数器=128位），就需要硬件支持16字节的cas指令（如x86-64的cmpxchg16b）。并非所有平台都支持，std::atomic<tagged_ptr> 可能不是无锁的，可以通过is_always_lock_free检查。
利用未使用的地址位：在64位系统上，实际使用的虚拟地址通常只有48位。可以利用剩余的16位作为版本号，从而将指针和版本号打包进一个64位变量，这样单次cas就能完成。boost库的tagged_ptr就采用了类似思路。
使用线程本地唯一的tag：用一个线程独有的、不变的标记值（如线程id）作为tag，而不是递增计数器。这样做的好处是tag不会溢出，避免了计数器归零可能带来的新aba问题。

方案二：风险指针（hazard pointers）

这种方法主要解决无锁算法中的内存回收问题，但同时也能有效防止aba问题-。

其核心思想是：一个线程在访问一个指针之前，会先将其声明为一个“风险指针”（hazard pointer），告知其他线程“我正在使用这个对象，请勿删除”。

当另一个线程想要删除一个节点时，它会检查所有线程的“风险指针”列表。如果该节点正在被任何人“声明”，则暂不删除，稍后再试；否则，可以安全回收-。

由于一个节点在被“声明”为风险指针期间不会被删除和重新分配，因此不会出现“指针a被删除后又重新分配为a”的情况，从而从根源上杜绝了aba问题。

注意：c++标准库目前没有内置风险指针，但c++26标准中可能会引入相关支持-。目前可以使用第三方库或自行实现。

方案三：读-复制-更新（rcu，read-copy-update）

rcu是一种常用于读多写少场景的同步机制。

读者（reader）：不需要任何锁或原子操作，可以无阻塞地访问数据。
写者（writer）：进行更新时，会创建一个新的数据副本，在副本上完成修改，然后通过一个原子操作将指向旧数据的指针替换为指向新数据的指针。

在指针替换后，写者会等待所有可能正在访问旧数据的读者完成，然后安全地回收旧数据。

为什么能解决aba？ rcu保证在更新期间，旧数据副本依然有效且不会被回收，直到所有读者都离开。因此，不会出现一个指针指向的对象被回收又重新分配的情况，aba问题也就不会发生。

四、方案对比与总结

方案	核心思想	优点	缺点与适用场景
带标记的指针	为指针附加一个单调递增的版本号，cas时同时比较两者。	实现相对直接，性能开销小，是应用最广的方案。	需要处理双倍宽度cas或地址位复用等平台相关细节。
风险指针	线程访问对象前“声明”保护，阻止其被回收。	能同时解决aba问题和内存安全回收问题。	实现复杂，有一定的性能开销，c++标准库尚无直接支持。
rcu	写者创建副本，原子替换指针，延迟回收旧数据。	读者端性能极高（无锁、无原子操作）。	适用于读多写少的场景，实现复杂，对写者有一定延迟。