以原子方式向ConcurrentLinkedQueue添加第一个元素

3

我希望以原子无锁的方式使用ConcurrentLinkedQueue

多个并发线程将事件推入队列,而其他一些线程将处理它们。队列没有绑定,我不希望任何线程等待或被锁定。然而,读取部分可能会注意到队列已经为空。在无锁实现中,读取线程不能阻塞,而只能结束其任务并继续执行其他任务(即作为ExecutorService)。因此,将第一个新事件推入空队列的写入者必须意识到这一点,并应重新启动读取器(即通过向ExecutorService提交新的Runnable来完成)。后续提交第二个或第三个事件的任何其他线程都不需要关心,因为它们可以假设某个读取器已经准备好/提交。

很遗憾,ConcurrentLinkedQueue的 add() 方法总是返回 true。在添加事件之前或之后询问队列是否为空并不会有帮助,因为它不是原子性的。我应该使用一些额外的AtomicInteger来监视队列的 size(),还是有更聪明的解决方案?
Dieter.

扩展 ConcurrentLinkedQueue,覆盖 add() 方法,如果需要,触发处理器线程。您可能会遇到两个或多个处理器线程被触发的竞争条件,但它们可以使用同步锁来处理 - 唯一会发生阻塞的是很快就会死亡的线程,没有合法的工作线程会被阻塞。 - corsiKa
2个回答

2

我不太明白为什么你不直接使用ExecutorService来完成这个任务。它在内部使用了一个BlockingQueue,并且自己处理了所有的信号。

// open ended thread pool
ExecutorService threadPool = Executors.newFixedThreadPool(1);
for (Job job : jobsToDo) {
    threadPool.submit(new MyJobProcessor(job));
}

除非你有充分的理由,否则不要自己重写相同的逻辑。

如果你想要利用休眠线程,我强烈建议你不要费心。线程是相对便宜的,所以分配一个线程来处理你排队的任务是可以的。重复使用线程是不必要的,并且对我来说似乎是过早优化。


这取决于需求,如果需要高吞吐量或低延迟,则可以使用actor(轻量级线程,低内存占用)或disruptor(OS线程,预分配缓冲区)实现:http://www.infoq.com/presentations/LMAX - Andriy Plokhotnyuk
嗯,当然可以@Andriy,但除非分析器告诉你ExecutorService是瓶颈,否则让事情变得更复杂是没有意义的。 - Gray
我已经这样做了。我提到了一个消耗队列的线程,但实际上它是基础ExecutorService的Runnable任务。 - Ditz
直到提交的处理器准备好开始处理事件之前,可能已经排队了更多的事件,但我不想提交其他处理器。最后,在处理完所有事件后,处理器任务不能简单地等待(如阻塞队列),因为它会阻塞我的ExecutorService的当前线程。相反,它必须终止(Runnable任务,而不是线程),如果有进一步的事件进来,则必须重新启动。<br/>同时,我认为一些AtomicInteger可以胜任这项工作。 - Ditz

1

昨晚我使用Google Caliper对MPSCQueue、AoMP的LockFreeQueue和CLQ进行了单线程基准测试。我通常看到CLQ在35ns左右,而其他两个则在500-600ns之间,并且有很高的CPU峰值(可能是由于总线争用引起的)。我的自定义无锁环形缓冲区表现最佳,但我还没有找到如何安全地处理溢出到CQL的方法。 - Ben Manes
我重新编写了基准测试,因为我在本地丢弃了它。结果相似。 - Ben Manes
我尝试了一下,但还没有弄清楚为什么基准测试结果会有如此大的差异。你的基准测试没有执行任何JVM预热或尝试在性能达到稳定状态之前进行评估,因此早期运行可能会受到不公平的惩罚。在我的环境中,我最好的猜测是Caliper正在同时运行多个测试,并且TAS样式的cas操作会导致总线风暴和CPU峰值(未利用L1自旋的mesi缓存一致性)。当然,这也可能只是一个错误的基准测试。如果您可以将我的基准测试移植到您的环境中,那就太好了。 - Ben Manes
我不会那么盲目地相信基准测试框架......这里有一个简单的测试和输出,证明MPSCQueue具有更好的性能:https://gist.github.com/3181092#gistcomment-380023 - Andriy Plokhotnyuk
谢谢Andriy。我会在CLHM上尝试并将其运行到我的其他(非Caliper)基准测试中。我可能会与编写Caliper的朋友交流,看看他们是否有任何想法。通常在单线程测试中表现良好,但我有一些想法,可能存在一些错误的假设。 - Ben Manes
显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接