C++ 并发专题 - 无锁数据结构（队列）

一：概述：

        当我们在并发程序中使用队列时，通常会使用锁来同步推入（push）和弹出（pop）操作。我们会在执行推入或弹出操作之前加锁，并在函数结束之前解锁。然而，锁的使用会带来一些开销，包括创建和获取锁的成本。因此，如果我们能够完全避免使用锁，并仍然支持并发操作，那将是非常理想的。对于许多数据结构，如链表、栈和队列，我们可以借助原子操作中的比较并交换（CAS）来实现同步、无锁版本。在 C++ 中，它被称为 std::atomic<T>::compare_exchange_weak。

二：什么是CAS

        CAS 最初是 IBM 在 1973 年引入的 CPU 指令。请记住，只有原始的 CPU 指令才能真正做到原子操作。我们要感谢硬件工程师们给我们带来了 CAS，因为它确实是一个非常棒且有用的指令。

        std::atomic<T>::compare_exchange_weak 会将 std::atomic<T> 的当前值与预期值进行比较，如果相等，则将 std::atomic<T> 的值替换为期望的目标值。以下是一个简化的 C++ 代码示例，展示了它的工作原理：

template <typename T>
bool compare_exchange_weak_example(std::atomic<T>& atomic_var, T& expected, T desired) {// 进行比较交换bool success = atomic_var.compare_exchange_weak(expected, desired);// 如果交换成功，返回 true；否则，返回 falsereturn success;
}

三：实现

template<typename T>
class lock_free_queue
{
private:// 节点结构，队列中的每个元素都封装在一个节点中struct node{std::shared_ptr<T> data;  // 存储数据，使用 shared_ptr 自动管理内存std::atomic<node*> next;  // 原子指针，指向下一个节点node(T const& data_) :data(std::make_shared<T>(data_)) {}  // 构造函数，初始化节点数据};std::atomic<node*> head;  // 队列头部的原子指针std::atomic<node*> tail;  // 队列尾部的原子指针public:// 向队列尾部添加一个元素void push(T const& data){// 创建一个新的节点并初始化数据std::atomic<node*> const new_node = new node(data);// 获取当前尾节点的指针node* old_tail = tail.load();// 尝试更新尾节点的 next 指针，直到成功while (!old_tail->next.compare_exchange_weak(nullptr, new_node)) {// 如果尾节点的 next 指针不是 nullptr，表示其他线程已经插入了节点// 需要重新加载尾节点并重试old_tail = tail.load();}// 尝试将尾节点更新为新的节点tail.compare_exchange_weak(old_tail, new_node);}// 从队列头部弹出一个元素std::shared_ptr<T> pop(){// 获取当前头节点的指针node* old_head = head.load();// 尝试更新队列的头节点，直到成功while (old_head &&!head.compare_exchange_weak(old_head, old_head->next)) {// 如果头节点的 next 指针不为空，表示其他线程已经移除了节点// 需要重新加载头节点并重试old_head = head.load();}// 如果成功获取到头节点，则返回数据；否则返回空的 shared_ptr，表示队列为空return old_head ? old_head->data : std::shared_ptr<T>();}
};