C++无锁栈实现详解（从零开始掌握lock-free stack并发编程）

什么是无锁栈？

无锁栈是一种不使用互斥锁来同步线程访问的数据结构。它依赖于CPU提供的原子操作（如 compare-and-swap，简称 CAS）来保证多个线程同时操作时的数据一致性。这种设计能显著提升性能，尤其是在多核系统中。

在 C++ 中，我们可以使用 std::atomic 和 std::shared_ptr（或裸指针配合内存序控制）来实现无锁栈。

基本原理：CAS 操作

CAS 是“Compare-And-Swap”的缩写，是一种原子指令。它的逻辑是：

如果内存中的值等于预期值，则将其更新为新值；否则不做任何操作，并返回当前实际值。

C++ 标准库通过 std::atomic<T>::compare_exchange_weak() 或 compare_exchange_strong() 提供这一功能。

实现步骤

我们将构建一个简单的无锁栈，支持 push 和 pop 操作。

1. 定义节点结构

template<typename T>struct Node {    T data;    std::atomic<Node*> next;    Node(T const& d) : data(d), next(nullptr) {}};

2. 定义无锁栈类

template<typename T>class LockFreeStack {private:    std::atomic<Node<T>*> head;public:    LockFreeStack() : head(nullptr) {}    void push(T const& data) {        Node<T>* new_node = new Node<T>(data);        new_node->next = head.load();        while (!head.compare_exchange_weak(new_node->next, new_node));    }    bool pop(T& result) {        Node<T>* old_head = head.load();        while (old_head && !head.compare_exchange_weak(old_head, old_head->next));        if (old_head) {            result = old_head->data;            delete old_head;            return true;        }        return false; // 栈为空    }    ~LockFreeStack() {        while (head) {            Node<T>* tmp = head;            head = tmp->next;            delete tmp;        }    }};

代码解析

• push 操作：创建新节点，将其 next 指向当前 head，然后尝试用 CAS 将 head 更新为新节点。如果失败（说明有其他线程修改了 head），则重试。
• pop 操作：读取当前 head，尝试用 CAS 将 head 更新为 head->next。成功则返回原 head 的数据；失败则重试。若 head 为 nullptr，说明栈空。

⚠️ 注意：上述基础实现存在 ABA 问题 和 内存回收风险。在生产环境中，建议使用带有 hazard pointer 或引用计数的安全方案（如 std::shared_ptr 配合原子操作）。

为什么选择无锁栈？

在高并发系统中，传统加锁方式可能导致线程阻塞、上下文切换开销大，甚至死锁。C++并发编程中的无锁结构通过硬件级原子指令实现高效同步，具有以下优势：

• 无阻塞：线程不会因等待锁而挂起。
• 可扩展性好：适合多核 CPU 并行处理。
• 避免死锁：没有锁，自然不会有死锁。

总结

通过本文，你已经掌握了如何用 C++ 实现一个基础的 lock-free stack。虽然实际工程中还需考虑内存安全、ABA 问题等复杂因素，但理解其核心思想是迈向高性能并发编程的关键一步。

建议进一步学习：std::atomic 内存序（memory_order）、Hazard Pointer、以及 Michael-Scott 无锁栈算法等高级主题。

关键词回顾：C++无锁栈、无锁数据结构、C++并发编程、lock-free stack。