Conway生命游戏的多线程Java程序 - 边界单元的争用

Question

我正在学习java中的并发编程,并为Game of Life编写模拟.

这就是我的想法:

• 使用int [] []存储单元格的状态
• 将int [] []分区为t段并使用t个工作线程
• t个线程将从其段读取,计算其段中所有单元的新值并更新单元.
• 一旦他们完成计算,他们就会等待其他工人的障碍完成
• 当屏障被越过时,主线程将更新UI.
• 工人们继续计算下一个州.

现在,这些细分市场的共同边界将会发生争执.如果一个线程在其邻居读取了之前的值之前覆盖了边界单元的状态,则该邻居的计算将是错误的.

我有什么选择？

• 使用callable而不是runnable并让工作线程返回新值(而不是更新段本身).穿过屏障后,主线程可以更新矩阵.此选项涉及将工作线程返回的结果复制到矩阵中.
• 使用两个障碍.工作者线程从邻居的段中复制边界单元格并在第一道屏障处等待.一旦通过此障碍,他们就会继续计算下一个状态并更新到位.然后他们在第二道屏障等候.主线程更新UI.

我的问题是,有没有其他方法可以处理边界单元中不涉及复制数据的争用,还是更有效的上述两种选择？可能是使用ReaderWriterLock,volatile变量还是其他同步机制？

更新:到目前为止,彼得的双缓冲解决方案是最干净的解决方案.但我有一个问题.由于这两个数组是共享数据而我们没有使用任何同步(同步访问或volatile变量),它是否会产生可见性问题？多个CPU可以缓存数组值并在每次迭代时只更新数组的一部分吗？然后线程将获得边界单元格的陈旧值.这可能吗？如果没有,为什么.如果是,我该如何解决？似乎声明两个数组volatile不会使它们各自的元素变得易变.

Answer 1

我建议有2个int [] []数组.我们称它们为A和B. A将保留所有奇数编号"ticks"的值,B将保持偶数编号.

将A初始化为初始状态.然后让你的线程松散以计算每个单元格的下一个状态,并将结果放在B中的相应单元格中.一旦完成所有线程,就可以在B中获得新状态.现在,使用B计算下一个状态每个单元格,并将结果存储在A中.在任何给定时间,一个数组将是只读的,另一个数组只写,因此永远不会有任何争用.

好处:

• 与您现在的操作相比,不会复制数据.每个单元格只发生一次写入.
• 不必担心边缘/角落情况,因为算法很简单.
• 没有持续的内存分配.只需在启动时分配两个数组.

缺点:

• 你需要分配两倍的内存.

Answer 2

它没有回答您的实际问题，但我的建议是您的第一个选择......返回新值而不是让工作线程更新它们。我会更进一步，让“聚合器”将工作线程的结果组合到一个新的板状态数组中，然后丢弃第一个。我的理由是，它将提高逻辑的整体可读性，因为您几乎不需要担心“全局交互”。

话虽这么说，我有点偏见，因为我更喜欢以函数式方式进行编程，除非有充分的理由不这样做。