Java中的彼得森算法? [英] Peterson algorithm in Java?

问题描述

Java 中是否有用于互斥的 Peterson 算法的示例实现?

Is there example implementation of Peterson algorithm for mutual exclusion in Java?

推荐答案

这里没有人提供该算法在 Java 中的正确/安全实现.我不确定 John W 的解决方案应该如何工作，因为它缺少一些部分(即 ThreadLocals 的声明以及对他的数组中应该包含的内容的解释 - 原始 booleans 不有 get() 和 set()).

No one here has provided a correct/safe implementation of this algorithm in Java. I'm not sure how John W's solution is supposed to work since it's got pieces missing (namely the declarations of the ThreadLocals and an explanation of what is supposed to be in his array—primitive booleans don't have get() and set()).

Java 语言规范第 17 章 解释了 Java 内存模型.特别感兴趣的是第 17.4.5 节，它描述了 happens-before 顺序.在单个线程中考虑非常容易.考虑片段:

Chapter 17 of the Java Language Specification explains the Java memory model. Of particular interest is Section 17.4.5, which describes the happens-before order. It's pretty easy to think about within a single thread. Consider the snippet:

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

z = x;
w = y;

每个人都会同意，在这段代码的最后，x 和 z 都等于 0 和 y 和 w 等于 5.忽略声明，我们在这里有六个动作:

Everyone will agree that at the end of this snippet, both x and z are equal to 0 and both y and w are equal to 5. Ignoring the declarations, we have six actions here:

1. 写入x
2. 写入y
3. 读取x
4. 写入z
5. 从y
读取
6. 写入w

因为它们都出现在同一个线程中，所以 JLS 说这些读取和写入保证表现出这种顺序:上面的每个操作 n(因为这些操作在单个线程中)都有一个与所有动作的先发生关系 m, m > n.

Because they all appear in the same thread, the JLS says that these reads and writes are guaranteed to exhibit this ordering: each action n above (because the actions are in a single thread) has a happens-before relationship with all actions m, m > n.

但是不同的线程呢?对于普通的字段访问，线程之间没有建立之前发生的关系.这意味着线程 A 可以增加共享变量，线程 B 可能读取该变量但看不到新值.在JVM中程序的执行过程中，线程A的写的传播可能已经重新排序，发生在线程B的读之后.

But what about different threads? For normal field accesses, there are no happens-before relationships established between threads. This means a Thread A could increment a shared variable and Thread B might read that variable but not see the new value. In the program's execution in the JVM, the propagation of Thread A's write may have been reordered to happen after Thread B's read.

实际上，线程 A 可以写入变量 x，然后写入变量 y，从而在线程 A 内的这两个操作之间建立发生之前的关系.但是线程 B 可以读取 x 和 y 并且 B 获取 y 之前 的新值是合法的x 的新值出现.规范说:

In fact, Thread A could write to a variable x, and then to a variable y, establishing a happens-before relationship between those two actions within Thread A. But Thread B may read x and y and it is legal for B to get the new value of y before the new value of x appears. The spec says:

更具体地说，如果两个动作分享先发生的关系，他们不一定要出现以那个顺序发生在任何他们不共享的代码发生在关系之前.

More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-before relationship.

我们如何解决这个问题?对于普通的字段访问，volatile 关键字就足够了:

How do we fix this? For normal field accesses, the volatile keyword is enough:

写入易失性变量(§8.3.1.4) v 与所有同步任何线程对 v 的后续读取(其中后续是根据到同步顺序).

A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent reads of v by any thread (where subsequent is defined according to the synchronization order).

synchronizes-with 是比happens-before 更强的条件，并且由于happens-before 是可传递的，如果线程A 希望线程B 看到它对x 的写入并且y，在写完x和y之后，只需要写入一个易变的变量z即可.线程B在读取x和y之前需要先从z读取，保证看到x的新值code> 和 y.

synchronizes-with is a stronger condition than happens-before, and since happens-before is transitive, if Thread A wants Thread B to see its writes to x and y, it just needs to write to a volatile variable z after writing x and y. Thread B needs to read from z before reading x and y and it will be guaranteed to see the new values of x and y.

在 Gabriel 的解决方案中，我们看到这种模式:写发生在 in 上，其他线程不可见，但随后写发生在 turn，所以只要其他线程先读取turn，就可以保证看到这两个写入.

In Gabriel's solution, we see this pattern: a write occurs to in, which would not be visible to other threads, but then a write occurs to turn, so other threads are guaranteed to see both writes as long as they read turn first.

不幸的是，while 循环的条件是向后的:为了保证线程不会看到 in 的陈旧数据，while 循环应该首先从 turn 读取:

Unfortunately, the while loop's conditional is backwards: to guarantee a thread does not see stale data for in, the while loop should read from turn first:

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

考虑到这个修复，剩下的大部分解决方案都可以:在临界区，我们不关心数据的陈旧，因为，好吧，我们在临界区！唯一的另一个缺陷出现在最后:Runnable 将 in[id] 设置为一个新值并退出.是否可以保证另一个线程看到 in[id] 的新值?规范说不:

With this fix in mind, most of the rest of the solution is ok: in the critical section, we don't care about staleness of data because, well, we're in the critical section! The only other flaw comes at the end: the Runnable sets in[id] to a new value and exits. Will the other Thread be guaranteed to see the new value of in[id]? The spec says no:

线程T1中的最终动作与任何动作同步另一个线程 T2 检测到 T1已终止.T2 可以完成这通过调用 T1.isAlive() 或T1.join().

The final action in a thread T1 synchronizes-with any action in another thread T2 that detects that T1 has terminated. T2 may accomplish this by calling T1.isAlive() or T1.join().

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

So how do we fix it? Just add another write to turn at the end of the method:

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

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

Since we reordered the while loop, the other thread will be guaranteed to see the new false value of in[id] because the write to in[id] happens-before the write to turn happens-before the read from turn happens-before the read from in[id].

毋庸置疑，如果没有度量吨的评论，这种方法很脆弱，有人可能会改变某些东西并巧妙地破坏正确性.仅仅声明数组 volatile 还不够好:正如 在此线程中 作者:Bill Pugh(Java 内存模型的主要研究人员)，声明一个数组 volatile 使对数组的更新 reference 对其他线程可见.数组元素的更新不一定是可见的(因此，我们只需要使用另一个 volatile 变量来保护对数组元素的访问，从而跳过所有循环).

Needless to say, without a metric ton of comments, this method is brittle and someone could come along and change something and subtly break the correctness. Just declaring the array volatile is not good enough: as explained in this thread by Bill Pugh (one of the lead researchers for the Java memory model), declaring an array volatile makes updates to the array reference visible to other threads. Updates to array elements are not necessarily visible (hence all the loops we just had to jump through by using another volatile variable to guard access to the array elements).

如果您希望您的代码清晰简洁，请保持原样并将 in 更改为 AtomicIntegerArray(使用 0 表示假，1 表示真；没有 AtomicBooleanArray).这个类就像一个数组，它的元素都是 volatile，因此可以很好地解决我们所有的问题.或者，您可以只声明两个可变变量，boolean in0 和 boolean in1，然后更新它们而不是使用布尔数组.

If you want your code to be clear and concise, keep it the way it is and change in to be an AtomicIntegerArray (use 0 for false, 1 for true; there is no AtomicBooleanArray). This class acts like an array whose elements are all volatile, and so will solve all our problems nicely. Alternatively, you could just declare two volatile variables, boolean in0 and boolean in1, and update them instead of using a boolean array.

这篇关于Java中的彼得森算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！