c++中如何实现一个高性能的无锁队列？ (CAS操作详解)-C++-PHP中文网

直接用 std::atomic 实现无锁队列易出错，主因是MPMC场景下单指针CAS无法保证插入/弹出原子性，且面临ABA问题；安全方案需用带版本号的tagged pointer（如48位指针+16位版本号），要求指针64KB对齐，并严格配对memory_order。

c++中如何实现一个高性能的无锁队列？ (cas操作详解)

为什么直接用 `std::atomic` 实现无锁队列容易出错？

因为无锁队列本质是多生产者多消费者（MPMC）场景，仅靠对 head 或 tail 单个指针做 fetch_add 无法保证节点插入/弹出的原子性。典型错误是「ABA问题」：线程A读到 tail == p，被调度走；线程B把 p 弹出又重用了同一内存地址；线程A回来继续 CAS，误以为链表结构没变，导致指针断裂或重复释放。

真正安全的做法必须同时控制两个指针状态，常见方案是使用双字 CAS（double-word CAS），但 x86-64 的 cmpxchg16b 指令需开启特定编译选项且部分老 CPU 不支持；更通用的解法是引入版本号（tagged pointer）——把指针低几位腾出来存计数，避免 ABA。

`std::atomic` 模拟 tagged pointer 的写法

将 64 位整数拆成 48 位指针 + 16 位版本号（足够应对绝大多数场景），所有 CAS 都作用于这个整数。关键点在于：指针必须 64KB 对齐（确保低 16 位为 0），才能安全移位。

分配节点时用 aligned_alloc(65536, sizeof(Node)) 或自定义内存池
读取指针：ptr = (Node*)(val & ~0xFFFFULL)
读取版本：ver = val & 0xFFFFULL
CAS 前必须构造新值：new_val = ((uint64_t)new_ptr) | ((old_ver + 1) & 0xFFFFULL)

struct Node {
    int data;
    std::atomic<uint64_t> next; // 存储 tagged pointer
};

struct LockFreeQueue {
    std::atomic<uint64_t> head; // tagged pointer
    std::atomic<uint64_t> tail;

    LockFreeQueue() : head(0), tail(0) {}
};</uint64_t></uint64_t></uint64_t>

CAS 循环中必须检查空队列和满队列边界

无锁队列不是“无边界”，而是边界检查必须嵌入 CAS 循环内，否则多个线程可能同时判定“可入队”却争抢同一槽位。例如基于数组的环形无锁队列（如 Dmitry Vyukov 队列），enqueue 中要反复读 tail、计算索引、检查 queue[(tail + 1) % capacity] != nullptr，再尝试 CAS 更新 tail —— 这个检查不能放在 CAS 外部，否则会漏掉其他线程刚写入的值。

seo-keyword-analyzer

分析关键词进行SEO优化；研究搜索量、竞争程度和排名难度；生成关键词建议、内容创意及优化建议。

下载

基于链表的实现同样如此：插入前必须确认 tail->next == nullptr，但这个判断本身不是原子的，所以要用 CAS 尝试设置 tail->next = new_node，失败则说明已有其他线程抢先推进了 tail，需重新读取最新 tail。

实际项目中更推荐用成熟实现而非手写

Linux 内核的 lockless list、Facebook 的 Folly::MPMCQueue、Boost.Lockfree，都经过大量压测和内存模型验证。手写无锁结构最易出问题的地方不在 CAS 本身，而在内存序（memory order）选择：std::memory_order_acquire 和 std::memory_order_release 必须成对出现在读/写路径上，漏掉一个就可能导致重排序后看到脏数据；而 std::memory_order_relaxed 在某些路径下看似能提升性能，实则破坏 happens-before 关系。

如果你只是需要高吞吐队列，优先考虑 Folly::MPMCQueue 并启用 cache_line_size 对齐；若必须手写，请用 clang++ -fsanitize=thread 跑压力测试，而不是靠逻辑推演确认正确性。