C++中的无锁队列（Lock-free Queue）是什么？（如何在高并发场景下实现）

无锁队列是基于原子操作和内存序实现的线程安全队列，避免锁开销但逻辑复杂、易出aba等问题；需用std::atomic管理指针、延迟回收节点、防伪共享，并优先选用成熟实现如moodycamel::concurrentqueue。

无锁队列不是“没锁”，而是不依赖互斥量的线程安全队列

它靠原子操作（如 compare_exchange_weak）和内存序（memory_order）保障多生产者/多消费者下的正确性，避免了锁带来的阻塞、优先级反转和上下文切换开销。但代价是逻辑更复杂、调试困难、对硬件内存模型敏感。

常见错误现象：segmentation fault 在高并发下偶发出现；队列看似“吞”了元素却读不到；ABA 问题 导致指针被错误重用。

• 必须用 std::atomic<t></t> 管理节点指针，不能只对数据域做原子操作
• memory_order_relaxed 仅适用于计数器等无依赖场景；入队/出队关键路径至少需 memory_order_acquire / memory_order_release
• 节点内存不能在出队后立刻 delete——其他线程可能还在读它的 next 指针，得用 Hazard pointer 或 RCU 延迟回收

MPMC 场景下最实用的实现：基于 Michael-Scott 算法的变种

这是工业级无锁队列（如 Boost.Lockfree、Facebook Folly 的 ProducerConsumerQueue）的底层基础。它用两个原子指针 head 和 tail，配合“懒删除”处理竞争。

使用场景：日志批量写入、网络包分发、事件循环任务投递——要求低延迟、高吞吐，且能容忍少量内存占用增长。

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

• 入队时先 CAS 更新 tail->next，再 CAS 移动 tail；失败则重试，不阻塞
• 出队时类似，但需跳过已被标记为“已出队”的节点（通过将 next 最低位设为 1 实现标记）
• 别直接抄教科书代码：x86 上 memory_order_acq_rel 可行，ARM/AArch64 必须显式补 memory_order_acquire + memory_order_release，否则可能乱序

std::queue + std::mutex 不是“慢”，而是成了扩展瓶颈

单核性能差距可能不到 2 倍，但 32 线程争抢同一把 std::mutex 时，90% 时间花在 futex 等待上。这不是锁写得不好，是设计范式冲突。

性能影响：锁队列的吞吐量在 8 核以上基本持平甚至下降；无锁队列在 64 核下仍近似线性增长，但前提是节点分配不碰全局堆（要用对象池或 std::pmr::polymorphic_allocator）。

• 不要用 new 在入队时分配节点——内存分配器本身是锁保护的，瞬间退化成“伪无锁”
• 如果业务允许固定大小，优先用环形缓冲（boost::lockfree::spsc_queue），它连原子操作都省了，只靠指针+内存屏障
• 调试时加 assert 检查 head == tail 时是否真为空，很多 bug 来自对“空/满”边界的误判

别自己从零手撸，但得看懂开源实现在防什么

linux 内核的 lockless list、Folly 的 AtomicUnorderedMap 底层、甚至 rust 的 crossbeam-queue 都在反复验证同一批坑。自己实现前，先跑通 moodycamel::ConcurrentQueue 的 stress test。

容易被忽略的地方：缓存行伪共享（false sharing）。把 head 和 tail 放同一个 cache line 里，两个 CPU 核疯狂 ping-pong 同一行，性能比有锁还差。

• 用 alignas(64) 强制分离热字段，或填充 char pad[64]
• 所有指针操作必须配对检查：CAS 成功后立即读新值，不能假设“刚写完就一定可见”
• 测试不能只跑 1 秒——无锁 bug 往往在 10 分钟连续压测后才触发，用 ThreadSanitizer + UndefinedBehaviorSanitizer 是底线

真正难的不是写对第一个版本，是让那个版本在不同编译器（GCC/Clang/MSVC）、不同优化等级（-O2 vs -O3）、不同 CPU 架构（x86-64/ARM64/RISC-V）下行为一致。这点没人能跳过。