无锁队列通过原子操作实现多线程高效安全的数据共享，避免互斥锁开销。其核心是使用CAS等原子指令更新head和tail指针，确保线程安全。SPSC场景下可用循环缓冲区简化实现，MPMC则常用Michael-Scott链表算法，通过原子操作维护节点连接，并解决ABA问题与内存回收难题。需注意内存序选择、伪共享规避及悬空指针风险，推荐在高竞争场景使用，否则优先考虑带锁队列以降低复杂度。
实现无锁队列（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场景，无需强内存序，性能高。但不适用于多生产者或多消费者，因为可能出现写冲突或读脏数据。
多生产者多消费者的无锁队列（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），否则存在悬空指针风险。
注意事项与优化建议
实现无锁队列时需注意：
- 使用合适的内存序（memory_order_acq_rel等）减少同步开销。
- 避免伪共享：确保head和tail不在同一缓存行。
- 考虑使用现成库如abseil、folly中的无锁队列，更稳定高效。
- 调试困难，建议充分测试边界情况和压力场景。
基本上就这些。无锁队列虽能提升并发性能，但实现复杂，应优先评估是否真的需要。对于多数应用，带锁的队列（如std::queue + mutex）已足够高效。只有在高竞争场景下才考虑无锁方案。不复杂但容易忽略的是内存管理和ABA防护。
