8

我正在学习 Java 中的并发编程，并为 Game of Life 编写模拟。

这是我的想法：

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

现在将在段的共同边界处发生争用。如果一个线程在其邻居读取之前的值之前覆盖了边界单元的状态，则邻居的计算将是错误的。

我有哪些选择？

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

我的问题是，有没有其他方法可以处理不涉及复制数据或比上述两个选项更有效的边界单元格的争用？可能是在使用 ReaderWriterLock、volatile 变量或其他同步机制？

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

4

5 回答 5

5

我建议有 2 个 int[][] 数组。我们称它们为 A 和 B。A 将保存所有奇数“刻度”的值，B 将保存偶数刻度。

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

优点：

  • 与您现在所做的相比，无需复制数据。每个单元只发生一次写入。
  • 无需担心边缘/角落情况，因为算法很简单。
  • 没有持续的内存分配。只需在开始时分配两个数组。

缺点：

  • 您需要分配两倍的内存。
于 2010-02-24T20:47:20.383 回答
1

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

话虽如此，我还是有点偏见，因为我更喜欢以功能方式编程，除非有充分的理由不这样做。

于 2010-02-24T20:22:09.703 回答
1

我会尝试以下方法：

  • 让工作人员执行计算，但只将值写回内部单元格。
  • 对于边界单元格，存储结果。
  • 计算完成后，在障碍物处等待。
  • 当所有工作人员都在第一个屏障时，然后释放并允许每个工作人员写入边界单元格。
  • 在 UI 更新时等待第二个障碍

n x m切片所需的存储空间为2 * (n + m - 1)，因此通常较大的切片（8x8 或更多）需要相应较少的内存用于缓存值。

于 2010-02-24T20:31:35.077 回答
0

要回答有关双缓冲缓存问题的更新，这不是问题。CPU 具有一致的高速缓存，并且它们知道数据何时在另一个 cpu 高速缓存中发生更改。

于 2010-02-25T19:01:36.893 回答
0

我只是偶然发现java.util.concurrent.Exchanger<V>。它充当交换点。我可能可以使用它在相邻线程之间交换单元状态列表。那会比屏障更好，因为我只需要在相邻的工作人员之间进行同步。

于 2010-02-24T22:17:59.520 回答