Peterson算法在Java？ [英] Peterson algorithm in Java?

问题描述

在Java中有互斥的Peterson算法的示例实现吗？

解决方案

在Java中实现这个算法。我不知道John W的解决方案应该如何工作，因为它缺少了一些东西（即ThreadLocals的声明和对他的数组原语的解释 booleans 没有 get（）和 set（））。

Java的第17章语言规范解释了Java内存模型。特别感兴趣的是第17.4.5节，描述发生先前订单。在单个线程中考虑很容易。考虑下面的代码片段：

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

大家都同意，在这个片段的结尾， code>和 z 等于 0 和 y 和 w 等于 5 。忽略声明，我们在这里有六个动作：

1. 写入 x / li>
   
2. 写入 y


3. 读取 code>


4. 写入 z


5. $ c> y


6. 写入 w

因为它们都出现在同一个线程中，所以JLS说这些读写保证显示这种排序：上面的每个动作 n 动作在单个线程中）具有与所有动作 m ， m > n 的happens-before关系。

但是不同的线程呢？ 对于正常的字段访问，在线程之间没有建立happens-before关系。这意味着线程A可以增加一个共享变量，线程B可能读取该变量，但是没有看到新值。在程序在JVM中的执行中，线程A的写入的传播可能已经在线程B被读取之后被重新排序。

事实上，线程A可以写入变量 x ，然后到变量 y ，在线程A中的这两个动作之间建立一个发生先前的关系。线程B可以读取 x 和 y ，并且B获取 y 之前，将显示 x 的新值。规范说：

更具体地说，如果两个动作
共享一个发生先前的关系，
必须出现
发生在任何
代码，他们不共享一个
发生之前的关系。

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

volatile变量
（§8.3.1.4）v与任何线程
（其中后续根据
定义为同步顺序）的所有
后续读取v同步。 p>

同步是一个比发生前更强的条件，因为发生之前是可传递的，如果线程A需要线程B看到它对 x 和 y 的写入，它只需要写入一个volatile变量<$写入 x 和 y 后，c $ c> z 。线程B需要在读取 x 和 y z >，并且将确保看到 x 和 y 的新值。

在Gabriel的解决方案中，我们看到这种模式：在中发生写操作，这对其他线程是不可见的， turn ，因此只要首先读取转动，其他线程就可以保证看到这两个写入。

$不幸的是，while循环的条件是向后的：为了保证线程不会在 c>中看到的过期数据，while循环应该从 turn 第一个：

  // ... 
 （turn == other（）&& in [other（）]）{
 // ... 
  

有了这个解决方案，大部分的解决方案是确定的：在关键部分，我们不关心数据的陈旧，因为，我们在关键部分！唯一的另一个缺点是结束：Runnable将[id] 中的设置为一个新值并退出。将另一个线程保证看到在[id] 中的新值？规范说不：

线程中的最后一个动作T1
同步
中的任何动作另一个线程T2检测到T1
已终止。 T2可以通过调用T1.isAlive（）或
T1.join（）来完成
。

我们如何解决它？只需在方法结尾添加另一个写入<$​​ c $ c> turn ：

  // ... 
 in [id] = false; 
 turn = other（）; 
} 
 // ... 
  

因为我们重新排序了while循环，另一个线程将保证在[id] 中看到的新的false值，因为写入 in [id] 在从之前的之前写入发生 $ c> in [id] 。

不用说，没有指标吨是脆弱的，有人可以来，改变一些东西，巧妙地打破正确性。只是声明数组 volatile 还不够好：在此线程中 by Bill Pugh（关于Java内存模型的领导研究者），声明数组 volatile 更新数组 >对其他线程可见。对数组元素的更新不一定是可见的（因此所有的循环，我们只需要使用另一个 volatile 变量来保护对数组元素的访问）。

如果你希望你的代码清晰简洁，保持它的样子，并改变中为 AtomicIntegerArray （使用0表示false， 1为true;没有AtomicBooleanArray）。这个类的行为就像一个数组，其元素都是 volatile ，因此会很好地解决我们所有的问题。或者，你可以只声明两个volatile变量， boolean in0 和 boolean in1 ，并更新它们，而不是使用布尔数组。

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

解决方案

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

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;

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

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.

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.

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.

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

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

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.

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()]) {
        // ...

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:

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();
}
// ...

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

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

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.

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