Java中无锁数组扩展

Question

我有一个数组，许多线程都在写入。但是每个线程都有一个预分配的索引范围可以写入。此外，在所有线程完成之前，没有任何内容将从该数组中读取。

到目前为止，非常安全。当我需要扩展数组时，问题就出现了，当然，我指的是将其交换为一个复制第一个的更大的数组。这只偶尔发生（类似于 ArrayList）。

目前，我对数组的每个单独写入都进行锁定。即使不需要锁定以保持数组一致，我也必须锁定，以防数组当前正在被复制/交换。

由于有很多写操作，我不想要求它们进行锁定。只要在复制和交换数组时只要求编写器线程进行锁定的解决方案是可以接受的，因为这是不频繁的。

但我不能仅在复制/交换进行时施加写入锁定，因为线程可能已经将写入提交给旧数组。

我认为我需要某种障碍，等待所有写入完成，然后暂停线程，同时我复制/交换数组。但是CyclicBarrier需要我准确地知道目前有多少个活动线程，这是棘手的，并且可能容易受到边缘情况的影响，其中障碍最终会永远等待，或者太早降低。特别是我不确定如何处理在障碍已经存在的情况下新线程的到来，或者如何处理当前正在轮询作业队列的线程，因此，在没有新作业的情况下，将永远不会减少障碍计数。

我可能必须实现某些（原子）计算活动线程并尝试预先处理所有边缘情况的东西。

但这可能是一个我不知道的“已解决”的问题，因此我希望有比循环栅栏/线程计数更简单（因此更好）的解决方案。理想情况下，可以使用现有的实用程序类。

顺便说一下，我考虑过 CopyOnWriteArray。这对我没用，因为它为每个写入（很多）都进行复制，而不仅仅是数组扩展。

还要注意的是，结构写入基本上必须是一个数组或基于数组的。

谢谢

- barneypitt

---

为什么不给每个线程分配一个自己的数组，在所有写入操作完成后将它们复制到最终数组中呢？ - tgdavies

“However each thread has a pre-assigned range of indices which it may write to"和"The problem arises when I need to expand the array"这两句话如何联系在一起？预先分配的索引范围会发生什么变化？如果只是添加新的“插槽”，为什么不实现一个类来保存许多数组并根据需要添加新的数组呢？ - knittl

你能否用二维数组替换一维数组？如果需要以一维格式访问它，你可以编写一个包装类，将一维索引映射到二维索引。 - rghome

@tgdavies 线程来自执行器池，并在拾取新作业后一次执行一个作业，每个作业都有一个预订项。大多数情况下，预订项仅适用于单行，偶尔会涉及范围。因此，当我说每个线程都有自己的“范围”时，我进行了简化：该范围将针对线程拾取的每个作业而更改。 - barneypitt

@knittl 是的，这是一个可行的解决方案。实际上，这是一个相当不错的解决方案！虽然需要一定的工作量，但它绝对是一个备选方案，并且肯定会起作用。谢谢。 - barneypitt

Answer 1

尽管它在技术上并不正确，但你可能可以使用ReadWriteLock。所有写入单个部分的线程都使用读取锁（这是技术上不正确的部分，它们并没有读取……），而调整大小则使用写入锁。这样，所有写入线程就可以一起工作。调整大小必须等待所有分区写入完成，然后阻止整个数组。完成后，所有分区写入就可以继续进行。

- Rob Spoor

---

可以说他们确实在“读取”和“写入” - 他们读取数组的引用，并编写一个新的数组引用。他们所有人都写入所引用的数组事实上有些不重要 :) - Jon Skeet

在那种方式下使用 ReadWriteLock 没有任何“技术上不正确”的问题。如果有任何问题，那就是“ReadWriteLock”是一个糟糕的名称。“SharedExclusiveLock”会更好。readLock() 对象授予调用者对受保护数据的共享访问权限，而 writeLock() 对象授予独占访问权限。在许多应用程序中，如果线程只想要共享访问权限，那是因为它只会读取数据。但是，正如 OP 的问题证明的那样，还有其他安全的共享访问方式。 - Solomon Slow

@SolomonSlow，你说得完全正确。我只是考虑了名称，但我非常喜欢你建议的名称。 - Rob Spoor

哎呀，我应该想到这个的。我脑海中闪过使用ReadWriteLock的想法，但我猜“读”这一位让我拒绝了它。我非常确定这会起作用。谢谢。 - barneypitt

Answer 2

有一个解决方案，虽然会有一些开销，但没有锁定。

但首先，我建议使用二维数组（数组的数组），除非您绝对需要一维数组。然后，您可以扩展顶层数组而不影响下层数组的内容。如果您希望，还可以编写一个包装器类来使用一维索引访问整个内容。

但是，如果您真的想要一个一维数组，我建议如下：

我假设每个线程都有一个数字，它知道自己的唯一标识符并且可以转换为小索引（否则，我不知道如何索引到主数组）。

我还假设您拥有一个称为“mainArray”的主数组的引用，它是静态可访问的，但也可以注入到线程中。它应该被声明为易失性。

您需要另一个长度为“numberOfThreads”的数组“currentArrays”，也可供所有线程使用。每个数组元素将包含线程当前正在使用的主数组的引用。

当您需要扩展数组时，请分配一个新数组并将其引用写入“mainArray”。此时，您无需复制任何内容。

在您的线程中访问主数组之前，您需要通过从“mainArray”赋值来获取对其的本地引用（即本地变量）。

然后将抓取的引用与“currentArrays”中的引用进行比较。如果相同，请继续，注意使用本地引用。

如果不同，请调用一个方法（您将编写该方法）将线程的先前数组部分复制到新数组中，然后像以前一样继续。将新数组引用写入该线程的“currentArrays”。直到完成之前，请再次使用本地引用。

旧数组应在所有线程完成其部分复制后进行垃圾回收，这意味着直到所有线程都至少有一个需要它的请求之前都不会进行垃圾回收。

第一次使用时会有一些初始化代码，这应该很明显（所有“currentArrays”元素都设置为“mainArray”）。

我认为这应该可以工作。显然，需要在访问数组之前比较数组引用的开销；但是，如果您在单个事务/请求中执行了大量数组访问，则可以保存抓取的数组引用，传递它并仅在需要再次获取它时重新检查。这应该减少开销。

免责声明：我没有测试过。欢迎评论。

- rghome

---

变量不必是静态的，只需要被工作线程访问即可。算法的解释不应该强制要求这样的技术细节。除此之外，似乎根本没有必要使用previousArray变量。在您的描述中，它被写了下来但从未被读取。此外，还缺少最后一步：一旦检测到所有工作线程都已完成，应该对currentArrays进行最后一次遍历，以检查是否所有工作线程在终止之前都看到了最终数组。否则，必须复制该特定部分。 - Holger

@Holger：感谢您的评论。您关于previousArray的观点是正确的，我漏掉了这一点。我会修改答案。至于数组字段是否需要静态，currentArrays不必如此。我曾考虑过在这些无锁解决方案中，切换mainArray需要是原子性的（通常情况下是这样），但实际上我认为并非如此。因此，这两个值都可以以某种方式注入到线程中。 - rghome

我认为它可以让它工作。这是一个相对复杂的解决方案，所以我可能会选择Rob Spoor的答案（即使它不完全无锁），因为它非常简单。感谢你的输入。 - barneypitt