Java 中的 Peterson 算法？

这里没有人在Java中提供此算法的正确/安全实现。我不确定 John W 的解决方案应该如何工作，因为它缺少一些片段（即 ThreadLocal 的声明和对他的数组中应该是什么的解释 - 原语没有和）。booleansget()set()

Java 语言规范的第 17 章解释了 Java 内存模型。特别令人感兴趣的是第 17.4.5 节，它描述了“发生前”的顺序。在单个线程中很容易考虑。考虑以下代码段：

int x, y, z, w;
x = 0;
y = 5;

z = x;
w = y;

每个人都会同意，在此代码段的末尾，两者和都相等，并且都等于 。忽略声明，我们在这里有六个操作：xz0yw5

1. 写到x
2. 写到y
3. 从x
4. 写到z
5. 从y
6. 写到w

因为它们都出现在同一个线程中，所以JLS说这些读取和写入保证表现出这种顺序：上面的每个操作n（因为这些操作在单个线程中）与所有操作m，m>n都有发生之前的关系。

但是不同的线程呢？对于正常的字段访问，线程之间不会建立任何发生前关系。这意味着线程 A 可以递增共享变量，线程 B 可能会读取该变量，但看不到新值。在程序在 JVM 中的执行中，线程 A 的写入的传播可能被重新排序为在线程 B 读取之后发生。

事实上，线程 A 可以写入一个变量，然后写入一个变量，在线程 A 中的这两个操作之间建立一个发生在之前的关系。但是线程 B 可以读取 并且 B 在新值出现之前获取 的新值是合法的。规格说：xyxyyx

更具体地说，如果两个操作共享“发生前”关系，则对于它们不共享“发生前发生”关系的任何代码，它们不一定必须显示为已发生。

我们如何解决这个问题？对于正常的字段访问，关键字就足够了：volatile

对易失性变量 （§8.3.1.4） v 的写入与任何线程对 v 的所有后续读取同步（其中后续根据同步顺序定义）。

synchronizes-with 是一个比发生在之前更强的条件，并且由于 happen-before 是可传递的，如果线程 A 希望线程 B 看到其写入和 ，它只需要在写入和之后写入可变变量。线程 B 需要在读取之前读取，并且将保证看到 和 的新值。xyzxyzxyxy

在 Gabriel 的解决方案中，我们看到这样的模式：写入 发生在 ，这对其他线程是不可见的，但随后写入发生了 ，因此，只要其他线程先读取，就可以保证看到这两个写入。inturnturn

不幸的是，while 循环的条件是反向的：为了保证线程看不到 的陈旧数据，while 循环应该从第一个读取：inturn

    // ...
    while (turn == other() && in[other()]) {
        // ...

考虑到此修复，解决方案的其余部分大部分都可以：在关键部分中，我们不关心数据的过时性，因为，好吧，我们处于关键部分！唯一的另一个缺陷出现在最后：Runnable设置为新值并退出。是否能保证另一个线程看到 的新值 ？规范说不：in[id]in[id]

线程 T1 中的最终操作与另一个线程 T2 中检测到 T1 已终止的任何操作同步。T2 可以通过调用 T1.isAlive（） 或 T1.join（） 来实现此目的。

那么我们该如何解决呢？只需在方法末尾添加另一个写入：turn

    // ...
    in[id] = false;
    turn = other();
}
// ...

由于我们对 while 循环进行了重新排序，因此另一个线程将保证看到新的 false 值，因为写入发生之前 - 在写入发生之前 - 在读取发生之前 。in[id]in[id]turnturnin[id]

毋庸置疑，如果没有大量的评论，这种方法是脆弱的，有人可以过来改变一些东西，并巧妙地打破正确性。仅仅声明数组是不够的：正如Bill Pugh（Java内存模型的主要研究人员之一）在此线程中所解释的那样，声明数组会使数组引用的更新对其他线程可见。对数组元素的更新不一定可见（因此，我们只需要使用另一个变量来保护对数组元素的访问来跳过所有循环）。volatilevolatilevolatile

如果你想让你的代码清晰简洁，保持它原来的样子，并更改为一个AtomicIntegerArray（使用0表示false，1表示true;没有AtomicBooleanArray）。这个类就像一个数组，其元素都是，因此可以很好地解决我们所有的问题。或者，您可以只声明两个易失性变量和 ，然后更新它们，而不是使用布尔数组。involatileboolean in0boolean in1

除非你对 Peterson 的 agorithm 有一些特定的需求（这在 Java 这样的高级语言中工作时会很奇怪），否则我建议你看看该语言内置的同步工具。

例如，你可能会发现Java中关于“竞争条件和互斥”的书中的章节很有用：http://java.sun.com/developer/Books/performance2/chap3.pdf

在 particlar 中：

Java通过条件的概念提供了内置的支持，等待这种“状态变化”。但是，条件有点用词不当，因为条件是否实际发生完全取决于用户。此外，条件不必是特别正确或虚假的。要使用条件，必须熟悉 Object 类的三个关键方法：

• wait（）：此方法用于等待条件。当当前正在为特定（共享）对象持有锁时调用它。

• notify（）：此方法用于通知单个线程条件已（可能）已更改。同样，当当前为特定对象持有锁时，将调用此方法。由于此调用，只能唤醒单个线程。

• notifyAll（）：此方法用于通知多个线程条件已更改（可能）。将通知在调用此方法时正在运行的所有线程。