无锁队列(Lock-free Queue) 是一种多线程共享的先进先出数据结构:它不靠互斥锁保护,而是靠一条 CPU 原子指令 CAS(Compare-And-Swap,比较并交换)来保证并发安全,并且始终保证至少有一个线程能继续推进。
CAS 怎么替代锁
CAS 的意思是:你给我一个旧值和一个新值,如果这块内存现在正好等于旧值,就把它改成新值并返回成功;否则什么都不改,返回失败,我重读一遍再试。整套动作由硬件保证不可被打断。
打个比方。锁像试衣间门上的挂锁:一个人进去,把牌子翻成“占用”,其他人只能排队干等。CAS 更像墙上贴的一张取号纸:谁想改号码,先核对纸上还是不是自己刚才看到的那个数,是就划掉重写,不是就说明别人刚改过,重新看一遍再动手。没人被挂起,也就没有“锁一忘放,全场卡死”。
出队操作大致是:读队头指针 p,读 p 的下一个节点 n,CAS 把队头从 p 改成 n。CAS 失败就重来。入队同理,把尾节点的 next 从 null 改成新节点。
麻烦一:ABA 问题
还看那张取号纸。你看到纸上写着 5,低头准备改;这时别人把它改成 6,又改回 5。等你抬头,纸上还是 5,CAS 判断“没变”,就放心改了——可这中间已经发生过两次变化,你的判断是基于过期信息。
队列里会这样出事:线程 A 读到队头指针指向节点 X;线程 B 把 X 弹出、释放,又新建了个节点恰好占了同一块地址;A 的 CAS 一看“还是 X 那个地址”,就把 B 的新节点接了上去,队列结构就乱了。常见解法是给指针配一个只增不减的版本号,把“指针 + 版本号”打包成一个双字一起 CAS。
麻烦二:内存回收
这是无锁队列最难的地方。线程 A 已经从队头读出指针,还没访问完;线程 B 就弹出这个节点并 free 掉了。A 再解引用,就是访问已释放内存——在 C/C++ 里这是随时可能崩的未定义行为。
锁的版本里不会有这问题:谁弹出谁释放,因为别人根本拿不到锁、碰不到这个节点。无锁就没有这个“天然屏障”。
工程上的对策有几种:危险指针(Hazard Pointer),使用前先登记“我正在用这个节点”,释放方看到登记就跳过;基于世代的回收(Epoch-Based Reclamation),等所有线程都跨过某个时间点再统一释放;引用计数;或者干脆依赖垃圾回收器,让运行时替你判断——Java 的并发队列走的正是这条路,这也是有 GC 的语言写无锁结构轻松得多的原因。
和相邻概念的区别
| 概念 | 推进保证 | 卡住时会发生什么 | 主要代价 |
|---|---|---|---|
| 互斥锁队列 | 阻塞式 | 一个线程出事,整条链停摆 | 上下文切换、死锁风险 |
| 自旋锁(Spinlock) | 阻塞式,忙等 | 空转烧 CPU | 临界区一长就亏 |
| 无锁(Lock-free) | 至少一个线程能前进 | 个别线程可能被反复抢先而饿死 | 实现难,要处理 ABA 与回收 |
| 无等待(Wait-free) | 每个线程都能在有限步内完成 | 不会饿死 | 更难写,常数开销更大 |
注意“无锁”不等于“无等待”,也不等于“更快”。它换来的是:没有线程被挂起,中断和实时场景下延迟更可预测。
对从业者的意义
AI 系统里它出现得很密:训练时数据预取的多生产者多消费者队列、推理服务的请求排队、日志与指标采集的缓冲区、多线程任务分发。这些地方往往是“临界区极短、并发度极高”,锁的上下文切换开销反而成了主要开销。
实践建议只有两条:第一,除非你在写基础库,否则不要自己实现——ABA 和内存回收的坑足够埋掉一个季度;用成熟库,具体行为和平台保证以官方页面为准。第二,无锁不是默认更优,务必用真实负载测。在低争用场景里,一把老老实实的互斥锁经常赢得毫不费力。
