C++无锁算法实现（从零开始掌握C++无锁编程与原子操作）

C++中的原子操作基础

自 C++11 起，标准库引入了 <atomic> 头文件，提供了 std::atomic<T> 模板类，用于声明原子类型变量。这些变量的操作（如读、写、比较交换）是不可分割的，即其他线程无法在操作中途“插队”。

关键函数：compare_exchange_weak 和 compare_exchange_strong 是实现无锁算法的核心，它们实现了著名的 CAS（Compare-And-Swap） 操作。

实战：用C++实现一个无锁计数器

我们先从最简单的例子开始——一个线程安全的无锁计数器。这个例子将帮助你理解 原子操作C++ 的基本用法。

#include <iostream>#include <atomic>#include <thread>#include <vector>std::atomic<int> counter{0}; // 声明一个原子整型变量void increment(int n) {    for (int i = 0; i < n; ++i) {        counter.fetch_add(1, std::memory_order_relaxed);    }}int main() {    const int num_threads = 4;    const int increments_per_thread = 100000;    std::vector<std::thread> threads;    for (int i = 0; i < num_threads; ++i) {        threads.emplace_back(increment, increments_per_thread);    }    for (auto& t : threads) {        t.join();    }    std::cout << "Final counter value: " << counter << std::endl;    // 输出应为 400000    return 0;}

这段代码中，fetch_add 是一个原子加法操作，确保即使多个线程同时调用，计数器也不会出错。这就是 C++并发编程 中无锁思想的简单体现。

进阶：无锁栈（Lock-Free Stack）

接下来，我们实现一个更复杂的无锁数据结构——单向链表栈。核心思想是使用 CAS 操作来安全地修改栈顶指针。

#include <atomic>#include <memory>template<typename T>class LockFreeStack {private:    struct Node {        T data;        std::shared_ptr<Node> next;        Node(T const& d) : data(d) {}    };    std::atomic<std::shared_ptr<Node>> head{nullptr};public:    void push(T const& data) {        auto new_node = std::make_shared<Node>(data);        new_node->next = head.load();        while (!head.compare_exchange_weak(new_node->next, new_node));        // 如果 CAS 失败（head 被其他线程修改），循环重试    }    std::shared_ptr<T> pop() {        auto old_head = head.load();        while (old_head && !head.compare_exchange_weak(old_head, old_head->next));        return old_head ? std::make_shared<T>(old_head->data) : nullptr;    }};

注意：compare_exchange_weak 可能会“虚假失败”（spurious failure），因此通常放在循环中重试。而 compare_exchange_strong 不会虚假失败，但性能略低。

注意事项与常见陷阱

• ABA 问题：指针值相同但中间已被修改过。可通过“带标签指针”（tagged pointer）解决。
• 内存顺序（Memory Order）：合理选择 std::memory_order 参数，平衡性能与正确性。
• 调试困难：无锁代码难以调试，建议先写有锁版本验证逻辑，再转换为无锁。

总结

通过本教程，你已经掌握了 C++无锁算法 的基本原理和实现方法。从原子计数器到无锁栈，你学会了如何利用 std::atomic 和 CAS 操作构建高效、安全的并发程序。

记住，无锁编程教程只是起点，真正的挑战在于设计复杂无锁数据结构（如队列、哈希表）。建议多阅读开源项目（如 folly、boost.lockfree）的源码，加深理解。

现在，你可以自信地说：我已入门 C++并发编程 和 原子操作C++！