java - 在 Java 中创建一个 Atomic RingBuffer

Question

我在考虑如何在 Java 和 Android 中实现线程安全的 RingBuffer(由于某种原因，即使经过这么多年，也没有一个循环队列。所以，没有(Circular/Ring )ByteBuffer，也不是 (Circular/Ring)(Buffer/Queue)。

据说大多数第三方的 RingBuffer 实现都不是线程安全的，这让我觉得它真的不像我想象的那么简单。我在想的是做这样的事情:

• 有一个对象(比如 RingBufferPosition)封装了 Head 和 Tail 的位置。
• 让 RingBuffer 维护对 RingBufferPosition 的 AtomicReference
• 当一个线程添加一些东西时，它会创建一个临时的(不幸的是，我对 Java 的了解还不够多，无法确定这个，但是“堆栈分配的”)对象，它将被一遍又一遍地回收，用新的更新头部和尾部，直到它可以 CAS 成功。
• 当线程删除某些内容时，它会执行类似于添加某些内容的操作。
• 在分配给最大长度的数组中访问所有内容，因此，头和​​尾可以在 O(1) 时间内访问/更新当前元素。

与简单地同步对集合的访问相比，这是否有效，甚至更好，是否会产生任何好处？

一个小代码示例/伪代码(尚未运行，我什至不知道如何远程测试原子数据结构，我计划将其用于缓冲/流媒体，但我还没有做到这一点因为我需要先创建它)可以找到 here .我有评论/文档详细说明了我的担忧。

最后，要解决一个可能的“为什么”问题，例如“您为什么需要这样的性能”，我会说实话。我一直发现数据结构，尤其是原子/无锁数据结构非常有趣，我发现这是一个很好的学习练习，而且我一直想创建一个 Ring Buffer。我本可以“同步”所有内容，但我也很看重性能。

Answer 1

多个读取器/多个写入器环形缓冲区很棘手。

你的方法行不通，因为你不能自动更新开始/结束位置和数组内容。考虑添加到缓冲区:如果您先更新结束位置，那么当缓冲区包含无效项时，在更新数组之前会有片刻。如果您先更新数组，则没有什么可以阻止同时添加操作对同一数组元素的踩踏。

有很多方法可以解决这些问题，但各种方法都有不同的权衡，如果你能摆脱多个读者或多个作者的要求，你就有更好的选择。

如果我不得不猜测为什么我们在标准库中没有并发环形缓冲区，我会说这是因为没有一种最好的实现它的方法适用于大多数情况。相比之下，用于 ConcurrentLinkedQueue 的数据结构简单而优雅，是需要并发链表时显而易见的选择。