无锁队列的设计思路与 ABA 问题处理
哪些公司问过
字节跳动1完美世界1
答案要点
- 用CAS或原子exchange代替锁,失败重试,保证至少一个线程能前进
- Michael-Scott队列:哑节点+head/tail原子指针,入队CAS链接next再推进tail,并帮助推进落后的tail
- 原子swap方案:exchange取得旧尾节点后链接next,常用于多生产者单消费者
- ABA:值A→B→A使CAS误判成功,多由节点释放后地址复用引起
- 解决:指针加版本号(双宽CAS、AtomicStampedReference),配合Hazard Pointer或epoch延迟回收
易错点
- 把无锁等同于没有任何同步,实际依赖原子操作和内存序
- 只用CAS比较裸指针而不处理ABA和节点回收
- 以为无锁一定比有锁快,高竞争下CAS重试和缓存行争用可能更慢
面试官常见追问
- 多生产者多消费者下,锁+信号量方案和无锁方案怎么选?
- 为什么无锁结构的内存回收是难点?
- 有界无锁队列怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。