Tantrum队列与LCRQ有界实现中的活锁问题排查

问题描述 #

我正在研究无锁多生产者多消费者（MPMC）队列，阅读相关设计与实践文献后了解到：

• Tantrum队列是一种模拟无限数组的无锁数据结构，通过内存连续的Segment执行核心操作，借助Fetch-Add指令分散生产者/消费者以降低CAS热点开销，但这类队列易出现活锁，需通过关闭并分配新Segment解决。

此前我研究的LCRQ（当前主流无锁MPMC队列方案）仅有无界实现，因此尝试两种朴素方案实现有界LCRQ：

1. 通过共享计数器itemsPushed、itemsPopped计算队列当前元素数，当达到容量上限时让push操作返回虚假失败；
2. 通过限制Segment的分配数量来实现队列有界。

但测试发现这两种方案均极易出现活锁，无法定位具体原因，希望得到技术上的分析和建议。

活锁原因分析 #

方案1：共享计数器判断容量的问题 #

• 竞争循环与无效重试：itemsPushed和itemsPopped是全局共享变量，高并发下Fetch-Add或CAS操作会产生严重竞争。当队列接近满时，大量生产者会同时读取到“队列未满”的状态，执行push前的准备操作，随后发现队列实际已满，返回虚假失败；接着立即重试，陷入“检测-准备-失败-重试”的循环，CPU空转形成活锁。
• 内存可见性偏差：无锁结构依赖内存屏障保证变量可见性，但高并发下计数器的更新无法及时被所有线程感知。部分线程会基于过期的计数判断队列未满，持续执行无效操作，进一步加剧活锁。

方案2：限制Segment数量的问题 #

• Segment竞争集中：LCRQ的Segment是生产者/消费者的核心竞争点，限制Segment数量后，所有生产者会集中在有限的几个Segment上竞争写入位置。当队列接近满时，消费者的弹出操作无法及时释放Segment空间，生产者持续尝试CAS写入失败，进入无限重试循环。
• 热点无法分散：Tantrum队列通过分配新Segment分散CAS热点来缓解活锁，而限制LCRQ的Segment数量后，相当于强制所有线程在固定热点上竞争，无法通过扩容分散压力，直接触发了类似Tantrum的活锁场景。

优化建议 #

• 分层计数减少全局竞争：给每个Segment分配局部的push_count和pop_count，全局容量通过各Segment的计数总和计算。同时让每个线程维护本地计数缓存，定期同步到全局，避免频繁的全局计数器操作。
• Segment复用与负载引导：限制Segment总数，但允许已被完全消费的Segment标记为可回收复用。给每个Segment设置写入阈值，当达到阈值时引导生产者转向其他可用Segment，避免集中竞争。
• 指数退避机制：在push操作失败时，采用指数退避策略（而非立即重试），减少线程间的竞争频率。退避时长可根据并发压力动态调整，平衡重试效率和资源消耗。
• 位置预分配策略：生产者发起push前，先通过Fetch-Add预留队列位置，预留时直接判断全局已预留位置是否超过容量，只有预留成功才执行后续写入，从根源上避免无效操作循环。

内容的提问来源于stack exchange，提问作者Mattia Piras