C++怎么实现一个无锁队列_C++并发编程与无锁队列实现-C++-PHP中文网

C++怎么实现一个无锁队列_C++并发编程与无锁队列实现

穿越時空

发布： 2025-11-20 18:17:53

原创

731人浏览过

无锁队列通过原子操作实现多线程高效安全的数据共享，避免互斥锁开销。其核心是使用CAS等原子指令更新head和tail指针，确保线程安全。SPSC场景下可用循环缓冲区简化实现，MPMC则常用Michael-Scott链表算法，通过原子操作维护节点连接，并解决ABA问题与内存回收难题。需注意内存序选择、伪共享规避及悬空指针风险，推荐在高竞争场景使用，否则优先考虑带锁队列以降低复杂度。

c++怎么实现一个无锁队列_c++并发编程与无锁队列实现

实现无锁队列（Lock-Free Queue）是C++并发编程中的高级话题，核心目标是在多线程环境下实现高效、安全的数据共享，避免使用互斥锁带来的性能开销和潜在死锁问题。无锁队列依赖原子操作和内存序控制来保证线程安全。

无锁队列的基本原理

无锁数据结构的关键在于使用原子操作（如 compare-and-swap, CAS）来更新共享状态。队列通常采用链表结构，每个节点包含数据和指向下一个节点的指针。通过原子地修改头指针（head）和尾指针（tail），多个线程可以同时进行入队和出队操作。

主要挑战包括：

A-B-A问题：某个值被修改后又恢复原值，导致CAS误判。
内存回收困难：无法立即删除出队节点，因为其他线程可能仍在访问。
ABA问题可通过引入版本号（如使用双字CAS或tagged pointer）缓解。

单生产者单消费者模型下的简单实现

在SPSC（Single Producer Single Consumer）场景中，可以简化设计。以下是一个基于循环缓冲区的无锁队列框架：

立即学习“C++免费学习笔记（深入）”；

#include <atomic>
#include <vector>
<p>template<typename T, size_t N>
class LockFreeQueue {
std::vector<T> buffer;
std::atomic<size_t> head{0};
std::atomic<size_t> tail{0};</p><p>public:
LockFreeQueue() : buffer(N) {}</p><pre class='brush:php;toolbar:false;'>bool push(const T& value) {
    size_t current_tail = tail.load();
    size_t next_tail = (current_tail + 1) % N;

    if (next_tail == head.load()) {
        return false; // 队列满
    }

    buffer[current_tail] = value;
    tail.store(next_tail);
    return true;
}

bool pop(T& value) {
    size_t current_head = head.load();

    if (current_head == tail.load()) {
        return false; // 队列空
    }

    value = buffer[current_head];
    size_t next_head = (current_head + 1) % N;
    head.store(next_head);
    return true;
}

登录后复制

};

这个版本适用于SPSC场景，无需强内存序，性能高。但不适用于多生产者或多消费者，因为可能出现写冲突或读脏数据。

如此AI员工

国内首个全链路营销获客AI Agent

172

查看详情

多生产者多消费者的无锁队列（Michael-Scott算法）

Michael和Scott提出的链表式无锁队列是经典MPMC实现。核心思想是：

使用链表节点，每个节点有data和next指针。
head和tail为原子指针。
push操作原子更新tail->next和tail本身。
pop操作检查head，移动head到next。

关键代码片段：

struct Node {
    T data;
    std::atomic<Node*> next;
<pre class='brush:php;toolbar:false;'>Node(const T& d) : data(d), next(nullptr) {}

登录后复制

};

std::atomic<Node> head; std::atomic<Node> tail;

bool push(const T& value) { Node new_node = new Node(value); Node old_tail = tail.load();

while (!tail.compare_exchange_weak(old_tail, new_node)) {
    // 尝试将新节点接在旧tail后面
    Node* next = old_tail->next.load();
    if (!next) {
        old_tail->next.compare_exchange_strong(next, new_node);
    }
    old_tail = tail.load(); // 更新old_tail
}
old_tail->next.store(new_node); // 连接节点
return true;

登录后复制

}

实际完整实现需处理内存释放（如使用 Hazard Pointer 或 RCU），否则存在悬空指针风险。