Java中的Peterson算法？

Question

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

Answer 1

这里没有人用Java提供这种算法的正确/安全实现.我不知道约翰·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.忽略声明,我们在这里有六个动作:

1. 写给 x
2. 写给 y
3. 阅读 x
4. 写给 z
5. 阅读 y
6. 写给 w

因为它们都出现在同一个线程中,JLS说,这些读取和写入,保证出现此顺序:每个动作ñ以上(因为行动是在单个线程)具有之前发生的所有行为关系米,米 > n.

但是不同的线程呢？对于正常的字段访问,在线程之间没有建立先前发生的关系.这意味着线程A可以递增共享变量,线程B可以读取该变量但不会看到新值.在程序在JVM中的执行中,线程A的写入的传播可能已被重新排序,以便在线程B读取之后发生.

事实上,线程A可以写入一个变量x,然后写入一个变量,y在线程A中的这两个动作之间建立一个先发生的关系.但是线程B可以读取x,y并且B获取y 之前的新值是合法的.新的价值x出现了.规范说:

更具体地说,如果两个动作共享发生在之前的关系,则它们不一定必须按照该顺序发生在它们不与之共享的任何代码之间.

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

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

同步,用比之前发生更强的状态,因为之前发生的传递,如果线程A希望线程B看到它的写入x和y,它只是需要写入volatile变量z写入后x和y.线程B需要从读z读书之前x和y,这将保证看到的新的价值观x和y.

在Gabriel的解决方案中,我们看到了这样的模式:写入发生in,其他线程不可见,但随后发生写入turn,因此只要它们turn首先读取,其他线程就可以保证看到两个写入.

不幸的是,while循环的条件是向后的:为了保证线程没有看到陈旧的数据in,while循环应该从turn第一个读取:

    // ...
    while (turn == other() && in[other()]) {
        // ...

考虑到这个问题,大多数解决方案的其余部分都可以:在关键部分,我们不关心数据的陈旧性,因为我们正处于关键部分!唯一的另一个漏洞出现在最后:Runnable设置in[id]为新值并退出.另一个Thread会保证看到新的值in[id]吗？该规范说不:

线程T1中的最终操作与另一个检测到T1已终止的线程T2中的任何操作同步.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,对其进行更新,而不是使用一个布尔数组.

Answer 2

除非你对Peterson的算法有一些特殊的需求(在使用像Java这样的高级语言时会很奇怪),我建议你看看内置于该语言的同步设施.

例如,您可能会发现Java中有关"竞争条件和互斥"的本书章节非常有用:http://java.sun.com/developer/Books/performance2/chap3.pdf

特别是:

Java通过条件的概念提供等待这种"状态变化"的内置支持.然而,条件有点用词不当,因为无论条件是否实际发生,完全取决于用户.此外,条件不必具体为真或假.要使用条件,必须熟悉Object类的三个关键方法:

•wait():此方法用于等待条件.当为特定(共享)对象保持锁定时调用它.

•notify():此方法用于通知单个线程条件已(可能)已更改.同样,当目前为特定对象保持锁时,调用此方法.由于此调用,只能唤醒单个线程.

•notifyAll():此方法用于通知多个线程条件已(可能)已更改.将通知在调用此方法时运行的所有线程.