Java中的Peterson算法？
在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;
每个人都同意在这个片段的末尾， x和z都等于0 ， y和w都等于5 。 忽略声明，我们在这里有六个动作：
- 写入
x - 写给
y - 从
x读取 - 写给
z - 从
y读 - 写给
w
因为它们都出现在同一个线程中，所以JLS表示这些读取和写入保证表现出这种顺序：上面的每个动作（因为动作都在一个线程中）与所有动作m ， m之前发生过关系> n 。
但是不同的线程呢？ 对于正常的字段访问，在线程之间没有建立先前发生的关系。 这意味着线程A可以递增共享变量，线程B可以读取该变量但不会看到新值 。 在程序在JVM中的执行中，线程A的写入的传播可能已被重新排序，以便在线程B读取之后发生。
实际上，线程A可以写入变量x ，然后写入变量y ，在线程A中的这两个动作之间建立先发生关系。但是线程B可以读取x和y ，B获取x的新值出现之前的新值y 。 规范说：
更具体地说，如果两个动作共享发生在之前的关系，则它们不一定必须按照该顺序发生在它们不与之共享的任何代码之间。
我们如何解决这个问题？ 对于普通的字段访问， volatile关键字就足够了：
对volatile变量（第8.3.1.4节）的写入v与任何线程对v的所有后续读取同步（其中后续根据同步顺序定义）。
synchronize-with是一个比之前发生的更强的条件，并且因为before-before是传递的，如果线程A希望线程B看到它对x和y写入，它只需要在写入x和y之后写入volatile变量z 。 线程B需要在读取x和y之前从z读取，并且将保证看到x和y的新值。
在Gabriel的解决方案中，我们看到了这种模式：写入发生in其中，其他线程看不到，但随后发生写入turn ，因此只要读取turn ，其他线程就可以保证看到两次写入。
不幸的是，while循环的条件是向后的：为了保证线程没有看到in过时数据，while循环应该首先从turn读取：
// ... while (turn == other() && in[other()]) { // ...
考虑到这个问题，大多数解决方案的其余部分都可以：在关键部分，我们不关心数据的陈旧性，因为我们正处于关键部分！ 唯一的另一个漏洞出现在最后：Runnable将in[id]为一个新值并退出。 是否可以保证其他线程能够看到in[id]的新值？ 该规范说不：
线程T1中的最终操作与另一个检测到T1已终止的线程T2中的任何操作同步。 T2可以通过调用T1.isAlive（）或T1.join（）来完成此操作。
那么我们该如何解决呢？ 只需在方法结尾添加另一个写入：
// ... in[id] = false; turn = other(); } // ...
由于我们对while循环进行了重新排序，因此另一个线程将保证in[id]看到新的false值，因为in[id]的写入发生在写入转发之前 – 在turn读取发生之前 – 在从in[id]读取。
毋庸置疑，如果没有一公吨的评论，这种方法很脆弱，有人可能会出现并改变一些东西并巧妙地打破正确性。 只是声明数组volatile是不够好的：正如Bill Pugh（Java内存模型的主要研究人员之一） 在此主题中所解释的那样，声明一个数组volatile使得对其他线程可见的数组引用更新。 对数组元素的更新不一定是可见的（因此我们只需通过使用另一个volatile变量来保护对数组元素的访问而跳过所有循环）。
如果您希望您的代码清晰简洁，请保持原样并更改为AtomicIntegerArray （使用0表示false，使用1表示true;没有AtomicBooleanArray）。 这个类就像一个数组，其元素都是volatile ，因此可以很好地解决我们所有的问题。 或者，您可以声明两个volatile变量boolean in0和boolean in1 ，并更新它们而不是使用布尔数组。
除非你对Peterson的算法有一些特殊的需求（当用Java这样的高级语言工作时会很奇怪），我建议你看看内置于该语言的同步设施。
例如，您可能会发现Java中有关“种族条件和互斥”的这一章有用： http ： //java.sun.com/developer/Books/performance2/chap3.pdf
特别是：
Java通过条件的概念提供等待这种“状态变化”的内置支持。 然而，条件有点用词不当，因为无论条件是否实际发生，完全取决于用户。 此外，条件不必具体为真或假。 要使用条件，必须熟悉Object类的三个关键方法：
•wait（）：此方法用于等待条件。 当为特定（共享）对象保持锁定时调用它。
•notify（）：此方法用于通知单个线程条件已（可能）已更改。 同样，当当前为特定对象保持锁时，调用此方法。 由于此调用，只能唤醒单个线程。
•notifyAll（）：此方法用于通知多个线程条件已（可能）已更改。 将通知在调用此方法时运行的所有线程。
我自己在网上找不到一个，所以我决定尝试写一下：
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; } }
随意评论，将不胜感激:)
你应该看看“多处理器编程的艺术”一书。 他非常详细地介绍了不同的锁实现（旋转和阻塞）。 他还讨论了不同类型的并发算法（例如跳过列表）。 以下是他的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 } }
虽然不是专利算法，但AtomicBoolean和Atomic *类使用无锁，繁忙循环的方法来更新共享数据。 它们可能符合您的要求。