手撕无锁 intrusive LIFO 栈
哪些公司问过
量化公司(明泓、佳琪、Avenir、九坤、非凸等)1
答案要点
- intrusive:next 指针内嵌在用户节点中,栈不额外分配内存,只维护原子 head
- push:读 head,设 node->next,CAS(head, old, node) 失败重试,成功用 release
- pop:acquire 读 head,读 next,CAS(head, old, next),成功返回旧节点
- ABA 用带版本号的指针(双宽度 CAS)解决,节点提前释放用 hazard pointer 或 epoch 回收解决
- 若一次弹出全部节点,可用 exchange(head, nullptr) 规避 ABA
易错点
- pop 时直接 delete 弹出的节点,其他线程仍可能在读它的 next
- 忽略 ABA,认为 CAS 成功就意味着中间没有变化
- 所有原子操作都用 relaxed,导致节点内容可见性问题
面试官常见追问
- 带版本号的指针怎么实现?
- 为什么 push 一般不受 ABA 影响?
- 各操作的内存序怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 线程同步与互斥的实现方式218 场
- 线程安全的保障方法121 场
- 自旋锁与互斥锁的区别和使用场景94 场
- 无锁队列的实现与 CAS64 场
- 生产者-消费者模型47 场
- 信号量的作用与它和锁的区别45 场
- 阻塞队列与有锁队列的实现22 场
- 多线程为什么需要加锁13 场
- mutex、lock_guard 与 unique_lock 的区别11 场
- 两个线程交替打印奇偶数10 场