无锁队列Lock-Free Queue的 CAS 实现探索C无锁队列是并发编程中的经典结构它不使用互斥锁mutex而是完全依赖原子操作主要是CAS—— Compare-And-Swap来保证线程安全和进度保证lock-free至少有一个线程能持续推进。1. 核心挑战与 ABA 问题CAS操作原型boolcompare_exchange_strong(Texpected,T desired,memory_order orderseq_cst);ABA 问题最致命的坑线程 A 读取指针p值为地址 X。线程 B 把 X 从队列中移除并释放内存然后重新分配一个新节点地址又回到 X。线程 A 执行 CAS发现指针仍是 X认为“没变”但实际节点内容已完全不同 →错误行为或崩溃。常见解决方案Tagged Pointer指针 版本号/计数器Hazard Pointers安全内存回收最通用Epoch-based reclamation延迟回收 引用计数2. Michael-Scott Lock-Free Queue经典算法这是 1996 年提出的实用无锁队列使用单向链表 dummy 头节点支持多生产者多消费者MPMC。数据结构templatetypenameTstructNode{T data;std::atomicNode*next;Node(constTval):data(val),next(nullptr){}};templatetypenameTclassLockFreeQueue{private:std::atomicNodeT*head;std::atomicNodeT*tail;public:LockFreeQueue(){NodeT*dummynewNodeT(T{});// dummy 节点head.store(dummy,std::memory_order_relaxed);tail.store(dummy,std::memory_order_relaxed);}~LockFreeQueue();// 需要正确回收内存后面讨论};Enqueue入队实现boolenqueue(constTvalue){NodeT*newNodenewNodeT(value);while(true){NodeT*ttail.load(std::memory_order_acquire);// 当前 tailNodeT*nextt-next.load(std::memory_order_acquire);if(ttail.load(std::memory_order_acquire)){// 一致性检查if(nextnullptr){// tail 指向最后一个节点// 尝试把新节点链接到 tail-nextif(t-next.compare_exchange_strong(next,newNode,std::memory_order_release,std::memory_order_relaxed)){// 成功后尝试移动 tail可能失败由其他线程帮助完成tail.compare_exchange_strong(t,newNode,std::memory_order_release,std::memory_order_relaxed);returntrue;}}else{// tail 已经落后帮它前移helpingtail.compare_exchange_strong(t,next,std::memory_order_release,std::memory_order_relaxed);}}}}Dequeue出队实现booldequeue(Tvalue){while(true){NodeT*hhead.load(std::memory_order_acquire);NodeT*ttail.load(std::memory_order_acquire);NodeT*nexth-next.load(std::memory_order_acquire);if(hhead.load(std::memory_order_acquire)){if(ht){// 队列为空或 tail 落后if(nextnullptr)returnfalse;// 真正为空// 帮助 tail 前移tail.compare_exchange_strong(t,next,std::memory_order_release,std::memory_order_relaxed);}else{valuenext-data;// 读取数据// 尝试移动 headif(head.compare_exchange_strong(h,next,std::memory_order_release,std::memory_order_relaxed)){// 回收旧 headdummy 节点——实际生产需 Hazard Pointersdeleteh;returntrue;}}}}}关键设计点Helping 机制落后线程帮助移动tail保证进度。Dummy 节点简化边界处理head 永远指向 dummy。内存序acquire用于读取release用于发布保证 Happens-before。3. 内存管理与 ABA 完整解决简单 tagged pointer 版本适用于 64 位系统低 16 位或高位留给 tagstructTaggedPtr{Node*ptr;uintptr_t tag;// 重载 和 CAS 辅助函数};std::atomicTaggedPtrhead,tail;推荐生产级方案Hazard PointersMaged Michael 提出。它能同时解决 ABA 和安全内存回收避免 use-after-free。其他高性能替代Bounded Ring Buffer固定大小数组 原子索引—— 性能更高但容量固定。moodycamel::ConcurrentQueue工业级极致优化。4. 完整注意事项与性能优点Lock-free无线程阻塞。高并发下性能优秀尤其 MPMC。缺点 / 挑战实现复杂极易引入隐蔽 Bug。内存回收困难leak 或 crash。在高负载下可能出现“帮助风暴”helping cascade。调试极难推荐 ThreadSanitizer 压力测试。性能优化方向批量操作batch enqueue/dequeue。缓存友好padding 避免 false sharing。使用memory_order_acq_rel精简。SPSC单生产单消费可简化为无 CAS 版本性能最高。5. 学习与实践建议先实现简单版不处理 ABA 和内存回收用多线程压力测试观察 Bug。加入 Tagged Pointer缓解 ABA。集成 Hazard Pointers实现生产可用版本。对比用std::queue mutex、tbb::concurrent_queue、moodycamel做性能 benchmark。工具ThreadSanitizer、perf、Google Benchmark。推荐资源原论文Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms(Michael Scott, 1996)《C Concurrency in Action》第 7 章moodycamel 的 ConcurrentQueue开源工业实现如果你想要带 Hazard Pointers 的完整可编译代码SPSC 环形缓冲区无锁实现更简单高效Tagged Pointer 版本性能测试框架特定场景优化如批量、优先级