无锁数据结构的设计要点与落地难点
哪些公司问过
字节跳动1量化公司(明泓、佳琪、Avenir、九坤、非凸等)1
答案要点
- 核心手段:原子变量 + CAS 循环,把修改压缩为一次原子替换,失败重试
- 常见落地形式:SPSC 环形缓冲、无锁栈、Michael-Scott 无锁队列
- 内存序:release 写与 acquire 读配对建立 happens-before,relaxed 只保证原子性
- 难点:ABA 与安全内存回收,常用版本号指针、Hazard Pointer、epoch 回收
- 难点:正确性验证困难、高竞争下 CAS 重试开销大,需要压测和工具辅助
易错点
- 认为无锁就一定比有锁快,高竞争下 CAS 失败重试和缓存行争用可能更慢
- 全部使用 relaxed 内存序,导致读到未完整写入的数据
- 节点出队后立即 delete,其他线程仍可能在访问,造成悬空指针和 ABA
面试官常见追问
- ABA 问题怎么解决?Hazard Pointer 和 epoch 怎么选?
- lock-free 和 wait-free 有什么区别?
- seq_cst 和 acquire/release 有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 线程同步与互斥的实现方式218 场
- 线程安全的保障方法121 场
- 自旋锁与互斥锁的区别和使用场景94 场
- 无锁队列的实现与 CAS64 场
- 生产者-消费者模型47 场
- 信号量的作用与它和锁的区别45 场
- 阻塞队列与有锁队列的实现22 场
- 多线程为什么需要加锁13 场
- mutex、lock_guard 与 unique_lock 的区别11 场
- 两个线程交替打印奇偶数10 场