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

问题描述

有例如实施彼得森算法在Java中互斥？

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

推荐答案

没有人在这里提供了一个正确的/安全的实现这个算法的Java。我不知道约翰·W公司的解决方案是如何工作的，因为它有个失踪（在ThreadLocals即的宣言和什么应该是在他的阵列的原始布尔解释没有的get（）和设置（））。

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 ，该描述的发生-前的顺序。这是pretty的容易想到在一个线程。考虑片段：

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 无一不是和是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. 在写是
3. 从 X中的读
4. 在写以Z
5. 从读是
6. 在写是W

1. A write to x
2. A write to y
3. A read from x
4. A write to z
5. A read from y
6. A write to w

由于它们都出现在同一个线程，JLS说，这些读取和写入，保证出现此顺序：每个动作的 N 的上方（因为行动是在单个线程）有所有行动的米发生，之前的关系的 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 ，然后给一个变量是，建立线程A.但是线程B在这两个动作之间发生的，之前的关系可以读 X 和是，这是合法的 X 出现B小 y的新的前值的的新值。该规范说：

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:

更具体地，如果两个动作   份额发生，之前的关系，   它们不一定必须出现   已经发生的顺序对任何   code与它们不共享   发生-之前的关系。

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.

我们如何解决这个问题？对于普通的字段访问时，挥发性关键字就足够了：

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

一个写volatile变量   （§8.3.1.4）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).

同步 - 以的是更强的条件比发生-面前，因为发生，之前是可传递的，如果线程A希望线程B看到其写入 X 和是，它只是需要在写入后写入volatile变量以Z X 和是。线程B需要从以Z 阅读前阅读 X 和是，这将是保证看到的新值 X 和是。

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 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循环的条件是倒退：保证线程没有看到过时的数据在，while循环应该从读转第一：

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对象，集在[ID] 来一个新的值并退出。请问其他线程保证看到的新值[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().

那么，我们如何解决这个问题？只需添加一次写打开在方法的末尾：

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

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

由于我们重新排序while循环，其他线程将保证看到的新的假值[ID] 因为写在[ID] 发生，之前在写打开发生-之前，读从打开发生-之前，读从在[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].

不用说，不评论度量的吨，这种方法是脆弱，有人可能会到来，改变的东西，巧妙地打破正确性。仅定义数组挥发性不够好：作为解释的in由比尔·普格这个线程（的牵头研究人员之一为Java内存模型），声明数组挥发性使更新到阵列的引用的可见的其他线程。更新数组元素不一定是可见的（因此所有我们刚刚通过其他挥发性变量来保护访问数组元素跳通过循环）。

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).

如果你希望你的code是简洁明了，保持它的方式，改变在是一个<一href="http://java.sun.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicIntegerArray.html">AtomicIntegerArray （用0表示假，1为真;没有AtomicBooleanArray）。该类的行为像一个数组，其元素都是挥发性，所以将解决我们所有的问题很好。或者，你可以只声明了两个volatile变量，布尔IN0 和布尔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屋！