无锁队列 CAS 原理及 C++ 实现示例

无锁队列使用 CAS (Compare and Swap) 原子操作实现，CAS 是一种原子性的操作，可以在不使用锁的情况下对共享变量进行原子的读-修改-写操作。其实现原理是比较共享变量的值和期望值，如果相等则将共享变量的值修改为新值，否则不做任何操作。

无锁队列的实现需要两个指针，head 和 tail，分别指向队列头和尾部。当一个新元素进入队列时，需要先将它插入到 tail 指针所指向的位置，然后将 tail 指针后移一位。当一个元素被取出时，需要先将 head 指针后移一位，然后返回 head 指针所指向的元素。

以下是一个简单的 C++ 实现示例：

#include <atomic>

template<typename T>
class LockFreeQueue {
public:
    LockFreeQueue() : head_(new Node), tail_(head_.load()) {}

    ~LockFreeQueue() {
        T value;
        while (dequeue(value));
        delete head_;
    }

    void enqueue(const T& value) {
        Node* node = new Node(value);
        Node* tail = tail_.load();
        while (true) {
            Node* next = tail->next_.load();
            if (next == nullptr) {
                if (tail->next_.compare_exchange_strong(next, node)) {
                    tail_.compare_exchange_strong(tail, node);
                    return;
                }
            } else {
                tail_.compare_exchange_strong(tail, next);
            }
        }
    }

    bool dequeue(T& value) {
        Node* head = head_.load();
        while (true) {
            Node* next = head->next_.load();
            if (next == nullptr) {
                return false;
            }
            if (head_.compare_exchange_strong(head, next)) {
                value = next->value_;
                delete head;
                return true;
            }
        }
    }

private:
    struct Node {
        T value_;
        std::atomic<Node*> next_;

        Node() : next_(nullptr) {}

        explicit Node(const T& value) : value_(value), next_(nullptr) {}
    };

    std::atomic<Node*> head_;
    std::atomic<Node*> tail_;
};

在该示例中，LockFreeQueue 类中包含一个 Node 结构体，用于存储队列中的元素。enqueue() 函数用于将元素插入到队列尾部，dequeue() 函数用于从队列头部取出元素。在 enqueue() 函数中，我们首先创建一个新的 Node 节点，然后通过 CAS 操作将它插入到 tail 指针所指向的位置，如果插入成功，则将 tail 指针后移一位。如果插入失败，则说明有其他线程已经修改了 tail 指针，我们需要重新获取 tail 指针的值并重试。在 dequeue() 函数中，我们首先获取 head 指针所指向的节点，然后通过 CAS 操作将 head 指针后移一位，如果操作成功，则返回 head 指针所指向的元素。如果操作失败，则说明有其他线程已经修改了 head 指针，我们需要重新获取 head 指针的值并重试。