在Java中是否有用于互斥的Peterson算法的示例实现？
问问题
14638 次
5 回答
27
这里没有人在 Java 中提供该算法的正确/安全实现。我不确定 John W 的解决方案应该如何工作，因为它缺少部分（即 ThreadLocals 的声明和对他的数组中应该包含的内容的解释 - 原始booleans没有get()and 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 说这些读取和写入保证表现出这种顺序：上面的每个动作n（因为动作在单个线程中）与所有动作m，m具有发生前的关系> n。
但是不同的线程呢？对于正常的字段访问，线程之间没有建立之前发生的关系。这意味着线程 A 可以增加一个共享变量，而线程 B 可能读取该变量但看不到新值。在 JVM 中的程序执行过程中，线程 A 的写入传播可能已重新排序，以发生在线程 B 的读取之后。
实际上，线程 A 可以先写入一个变量x，然后再写入一个变量，从而y在线程 A 中的这两个动作之间建立发生前的关系。但是线程 B 可以读取x，并且 B 获得beforey的新值是合法的的新值出现。规范说：y x
更具体地说，如果两个动作共享一个happens-before 关系，那么对于它们不共享happens-before 关系的任何代码，它们不一定必须以该顺序发生。
我们如何解决这个问题？对于普通的字段访问，volatile关键字就足够了：
对 volatile 变量（第 8.3.1.4 节）v 的写入与任何线程对 v 的所有后续读取同步（其中后续是根据同步顺序定义的）。
synchronizes-with是比happens-before 更强的条件，并且由于happens-before 是传递性的，如果线程A 想要线程B 看到它对and 的写入x，y它只需要在写入andz之后写入一个volatile 变量。线程 B 需要在读取 and 之前读取 from ，并且可以保证看到and的新值。xyzxyxy
在 Gabriel 的解决方案中，我们看到了这种模式：写入发生在 上in，这对其他线程是不可见的，但随后写入发生在 上turn，因此只要其他线程turn先读取，就可以保证看到这两个写入。
不幸的是，while 循环的条件是向后的：为了保证线程不会看到过时的数据in，while 循环应该从turn第一个开始读取：
// ...
while (turn == other() && in[other()]) {
// ...
考虑到这个修复，解决方案的其余大部分都可以：在临界区，我们不关心数据的陈旧性，因为，好吧，我们在临界区！唯一的其他缺陷出现在最后：Runnable 设置in[id]为新值并退出。是否可以保证其他线程看到 的新值in[id]？规范说不：
线程 T1 中的最终操作与另一个线程 T2 中检测到 T1 已终止的任何操作同步。T2 可以通过调用 T1.isAlive() 或 T1.join() 来完成此操作。
那么我们该如何解决呢？turn只需在方法末尾添加另一个写入：
// ...
in[id] = false;
turn = other();
}
// ...
由于我们对 while 循环进行了重新排序，因此另一个线程将保证看到新的 false 值，in[id]因为写入in[id]发生之前发生在写入turn发生之前发生在读取turn发生之前发生在读取发生之前in[id]。
不用说，如果没有大量的评论，这种方法很脆弱，有人可能会出现并改变某些东西并巧妙地破坏正确性。仅仅声明数组volatile还不够好：正如Bill Pugh（Java 内存模型的主要研究人员之一）在此线程中所解释的，声明数组会使对数组引用的更新对其他线程可见。数组元素的更新不一定是可见的（因此我们必须通过使用另一个变量来保护对数组元素的访问来跳过所有循环）。volatilevolatile
如果您希望代码清晰简洁，请保持原样并更改in为AtomicIntegerArray（使用 0 表示 false，1 表示 true；没有 AtomicBooleanArray）。这个类就像一个数组，其元素都是volatile，因此可以很好地解决我们所有的问题。或者，您可以只声明两个 volatile 变量boolean in0和boolean in1, 并更新它们，而不是使用布尔数组。
于 2010-05-26T20:21:41.900 回答
5
除非您对 Peterson 算法有某种特殊需要（在使用 Java 等高级语言时会很奇怪），否则我建议您查看该语言中内置的同步工具。
例如，您可能会发现本书中关于 Java 中“竞争条件和互斥”的章节很有用：http: //java.sun.com/developer/Books/performance2/chap3.pdf
特别是：
Java 通过条件的概念提供了等待这种“状态变化”的内置支持。然而，条件有点用词不当，因为条件是否实际发生完全取决于用户。此外，一个条件不需要特别是真或假。要使用条件，必须熟悉 Object 类的三个关键方法：
• wait()：此方法用于等待条件。当当前为特定（共享）对象持有锁时调用它。
• notify()：此方法用于通知单个线程条件已（可能）更改。同样，当当前为特定对象持有锁时，将调用此方法。此调用只能唤醒单个线程。
• notifyAll()：此方法用于通知多个线程条件已（可能）更改。将通知在调用此方法时正在运行的所有线程。
于 2010-05-26T10:23:31.273 回答
4
我自己在网上找不到，所以我决定试着写一下：
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;
}
}
欢迎评论，不胜感激：）
于 2010-05-26T10:10:45.183 回答
3
你真的应该看看《多处理器编程的艺术》这本书。他详细介绍了不同的锁实现（自旋和阻塞）。他还讨论了其他不同类型的并发算法（例如跳过列表）。这是他关于彼得森锁算法的书中的一个片段
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
}
}
于 2010-05-26T13:39:17.417 回答
0
虽然不是 paterson 算法，但 AtomicBoolean 和 Atomic* 类使用无锁、繁忙循环的方法来更新共享数据。它们可能适合您的要求。
于 2010-05-26T21:07:59.553 回答