java Java中的彼得森算法？

Peterson algorithm in Java?

提问by Gabriel ??erbák

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

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

回答by jasonmp85

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 booleansdon't have get()and set()).

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

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

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

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

z = x;
w = y;

Everyone will agree that at the end of this snippet, both xand zare equal to 0and both yand ware equal to 5. Ignoring the declarations, we have six actions here:

每个人都会同意，在这个片段的最后，都x和z都等于0两者y并w等于5。忽略声明，我们在这里有六个动作：

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

1. 写给 x
2. 写给 y
3. 读自 x
4. 写给 z
5. 读自 y
6. 写给 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 nabove (because the actions are in a single thread) has a happens-before relationship with all actions m, m> n.

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

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 可以增加共享变量，线程 B 可能读取该变量但看不到新值。在 JVM 中程序的执行过程中，线程 A 的写入的传播可能已被重新排序，以便在线程 B 的读取之后发生。

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 xand yand it is legal for B to get the new value of ybeforethe new value of xappears. The spec says:

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

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.

更具体地说，如果两个操作共享一个happens-before 关系，那么对于与它们不共享happens-before 关系的任何代码，它们不一定必须按照该顺序发生。

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

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

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

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

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

同步是比发生之前更强的条件，并且因为发生之前是可传递的，如果线程 A 想让线程 B 看到它对xand 的写入y，它只需要z在写入xand之后写入一个易失性变量y。线程B需要从读z读书之前x和y，这将保证看到的新的价值观x和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 turnfirst.

在 Gabriel 的解决方案中，我们看到了这种模式：写入发生在 上in，这对其他线程不可见，但随后发生在 上turn，因此只要其他线程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 turnfirst:

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

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

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

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

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

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

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

    // ...
    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 turnhappens-before the read from turnhappens-before the read from in[id].

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

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

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

If you want your code to be clear and concise, keep it the way it is and change into 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 in0and boolean in1, and update them instead of using a boolean array.

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

回答by Daniel Renshaw

Unless you have some specific need for Peterson's agorithm (which would be strange when working in a high level language like Java), I suggest you take a look at the synchronization facilities built in to the language.

除非您对 Peterson 算法有某些特定需求（这在使用 Java 等高级语言时会很奇怪），否则我建议您查看该语言内置的同步工具。

For example, you may find this book chapter on "Race Conditions and Mutual Exclusion" in Java useful: http://java.sun.com/developer/Books/performance2/chap3.pdf

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

In particlar:

特别是：

Java provides built-in support awaiting this “change in state” via the notion of a condition. A condition is a bit of a misnomer, however, because it is entirely up to the user whether or not a condition actually occurred. Furthermore, a condition need not be specifically true or false. To use conditions, one must become familiar with three key methods of the Object class:

? wait(): This method is used to await a condition. It is called when a lock is presently being held for a particular (shared) object.

? notify(): This method is used to notify a single thread that a condition has (possibly) changed. Again, this method is called when a lock is presently being held for a particular object. Only a single thread can be awakened as a result of this call.

? notifyAll(): This method is used to notify multiple threads that a condition has (possibly) changed. All threads that are running at the time this method is called will be notified.

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

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

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

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

回答by Gabriel ??erbák

I could not find one on the web myself, so I decided to try writing it:

我自己在网上找不到，所以我决定尝试编写它：

public class Peterson implements Runnable {

    private static boolean[] in = { false, false };
    private static volatile int turn = -1;

    public static void main(String[] args) {
        new Thread(new Peterson(0), "Thread - 0").start();
        new Thread(new Peterson(1), "Thread - 1").start();
    }

    private final int id;

    public Peterson(int i) {
        id = i;
    }

    private int other() {
        return id == 0 ? 1 : 0;
    }

    @Override
    public void run() {
        in[id] = true;
        turn = other();
        while (in[other()] && turn == other()) {
            System.out.println("[" + id + "] - Waiting...");
        }
        System.out.println("[" + id + "] - Working ("
                + ((!in[other()]) ? "other done" : "my turn") + ")");
        in[id] = false;
    }
}

Feel free to comment, it will be appreciated:)

随意评论，将不胜感激:)

回答by John Vint

You should really check out the book The Art of Multiprocessor Programming. He in great detail goes over different lock implementations (both spin, and blocking). He also goes over different other types of concurrent algorithms (skip list for instance). Here is a snippet from his book on the Peterson Lock algorithm

你真的应该看看《多处理器编程的艺术》这本书。他详细介绍了不同的锁实现（自旋和阻塞）。他还介绍了其他不同类型的并发算法（例如跳过列表）。这是他关于 Peterson Lock 算法的书中的一个片段

Class Peterson implements Lock{
   private final boolean []flag = new boolean[2];
   private volatile int victim;

   public void lock(){
        int i = ThreadID.get(); // ThreadID is a ThreadLocal field
        int j= 1 - i;
        flag[i] = true;    // I'm Interested
        victim = i;        // You go first
        while(flag[j] && victim == i){}; //wait
   }
   public void unlock(){
       int i = ThreadID.get();
       flag[i] = false;      //Not interested anymore
   }
 }

回答by Peter Lawrey

While not the paterson algo, the AtomicBoolean and Atomic* classes use the approach of lockless, busy loops to update shared data. They may suit your requirements.

虽然不是 paterson 算法，但 AtomicBoolean 和 Atomic* 类使用无锁、繁忙循环的方法来更新共享数据。它们可能适合您的要求。