Java中的免锁定阵列扩展



我有一个数组,许多线程正在向其中写入。然而,每个线程都有一个预先分配的索引范围,可以写入。此外,在所有线程完成之前,不会从数组中读取任何内容。

到目前为止,线程安全。当我需要扩展数组时,问题就出现了,当然我的意思是把它换成一个更大的数组来复制第一个数组。这只是偶尔进行的(类似于ArrayList)。

目前,我正在为数组的每一次写入获取一个锁。即使不需要锁定来保持阵列的一致性,我也必须锁定,以防阵列当前正在被复制/交换。

由于写的东西很多,我不想为它们加锁。我同意这样一种解决方案,即只在复制和交换阵列时才需要锁定编写器线程,因为这种情况很少发生。

但是,我不能只在复制/交换进行时才强制执行写锁,因为线程可能已经在向旧数组提交写操作了。

我想我需要一些不同的屏障,等待所有写入完成,然后在复制/交换数组时暂停线程。但CyclicBarrier需要我确切地知道目前有多少线程处于活动状态,这是不平凡的,可能容易受到边缘情况的影响,在这种情况下,屏障最终会永远等待,或者过早降低。特别是,我不确定在屏障已经打开时如何处理新线程,也不确定如何处理当前正在轮询作业队列的线程,因此在没有新作业时永远不会减少屏障计数。

我可能必须实现一些(原子地)计数活动线程并尝试抢占所有边缘情况的东西。

但这很可能是一个";已解决";我不知道这个问题,所以我希望有一个比循环屏障/线程计数更简单(因此更好)的解决方案。理想情况下,它使用现有的实用程序类。

顺便说一下,我已经考虑过CopyOnWriteArray。这对我来说没有用,因为它会为每次写入(大量写入)进行复制,而不仅仅是阵列扩展。

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

感谢

虽然技术上不正确,但您可能可以使用ReadWriteLock。写入单个部分的线程都使用读锁(这是技术上不正确的部分,它们没有读取…),而调整大小则使用写锁。这样,所有的编写线程都可以协同工作。调整大小必须等到所有分区写入完成,然后阻塞整个数组。一旦完成,所有分配的写入都可以继续。

有一个解决方案,尽管会有一些开销,但没有锁定。

但首先,我建议使用2-D阵列(阵列阵列),除非您绝对需要1-D阵列。然后,您可以在不影响较低级别数组内容的情况下展开顶级数组。如果愿意的话,您还可以为此编写一个包装类,使用一维索引来访问整个内容。

但是,如果真的想要有一个1-D阵列,我建议如下:

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

我还假设您有一个名为mainArray的主数组的引用,它是一个静态可访问的数组,但它也可以注入到线程中。它应该被宣布为不稳定的。

您需要另一个长度为numberOfThreads的数组currentArrays,它也可用于所有线程。每个数组元素都将包含线程当前使用的主数组的引用。

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

在访问线程中的主数组之前,您需要通过从mainArray赋值来获取对它的局部引用(即局部变量)。

然后将抓取的引用与currentArrays中的引用进行比较。如果是相同的,请继续,小心使用本地引用。

如果不同,请调用一个方法(您将编写该方法),将线程的上一个数组的一部分复制到新数组中,然后像以前一样继续。为该线程编写对currentArrays的新数组引用。再次使用本地引用,直到完成为止。

一旦所有线程都完成了对旧数组的部分复制,就应该对旧数组进行垃圾收集,这意味着直到所有线程都至少有一个请求需要它

将有一些首次使用的初始化代码,这应该是显而易见的(所有currentArrays元素都设置为mainArray)。

我认为这应该奏效。在访问数组之前,比较数组引用显然会带来开销;但是,如果您在一个事务/请求中进行了大量的数组访问,则可以保存您获取的数组引用,并将其传递出去,只有在需要再次获取时才重新检查。这样可以减少开销。

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

最新更新