Java中的彼得森算法?

这里没有人在Java中提供这个算法的正确/安全的实现。我不确定John W的解决方案应该如何工作,因为它丢失了一些片段(即线程局部变量的声明和对其数组“原始”中应包含的内容的解释)。 booleans 没有 get() 和 set() )

Chapter 17 of the Java Language Specification 解释Java内存模型。特别感兴趣的是 Section 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 上面(因为操作在一个线程中)与所有操作都有一个“发生在前”关系 米 , 米 gt; n .

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

实际上,线程A可以写入变量 X ,然后转换为变量 Y ,在线程A中的这两个操作之间的关系之前建立A。但线程B可以读取 X 和 Y 对B来说,获得 Y 之前 新的价值 X 出现。规格说明:

更具体地说,如果两个动作 A股发生在关系之前, 它们不一定非得出现 以这样的顺序发生 他们不共享的代码 发生在关系之前。

我们如何解决这个问题?对于正常的现场访问, volatile 关键字足够:

写入可变变量 (_§8.3.1.4)V与所有 任何线程随后读取v (如果后续定义依据 同步顺序)。

与同步 如果线程A希望线程B看到它的写入操作,则是比以前发生的情况更强的条件,并且由于以前发生的情况是可传递的。 X 和 Y ,它只需要写入可变变量 Z 写作后 X 和 Y . 线程B需要读取 Z 阅读前 X 和 Y 它将保证看到 X 和 Y .

在加布里埃尔的解决方案中,我们看到了这样一个模式:一个写入发生在 in ,它对其他线程不可见,但随后发生写入 turn ,因此其他线程在读取时保证看到这两个写操作。 转 第一。

不幸的是,while循环的条件是向后的:为了保证线程不会看到 在里面 ,while循环应该从 转 第一:

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

考虑到这个修正,剩下的大部分解决方案都是可以的:在关键部分,我们不关心数据的过时,因为,好吧,我们在关键部分!最后还有一个缺陷:可运行集 in[id] 到新值并退出。另一个线程是否保证看到 在[身份证]中 ?规范上说不:

线程T1中的最终操作 与中的任何操作同步 另一个检测T1的线程t2 已终止。t2可以完成 通过调用T1.isalive()或 T1.连接()。

那么我们该如何修复它呢?只需添加另一个写入 转 方法结束时:

    // ...
    in[id] = false;
    turn = other();
}
// ...

由于我们重新排序了while循环,另一个线程将保证看到 在[身份证]中 因为写信给 在[身份证]中 在写入之前发生 转 在读取之前发生 转 在读取之前发生 在[身份证]中 .

不用说,没有度量标准 吨 在评论中,这个方法是脆弱的,有人可能会过来改变一些东西,并巧妙地破坏正确性。只是声明数组 不稳定的 不够好:如前所述 in this thread 作者:Bill Pugh lead researchers 对于Java内存模型,声明数组 不稳定的 更新阵列 参考 其他线程可见。对数组元素的更新不一定是可见的(因此,我们只需要使用另一个 不稳定的 用于保护对数组元素的访问的变量)。

如果您希望您的代码清晰简洁,请保持原样并进行更改。 在里面 成为一个 AtomicIntegerArray (使用0表示假,1表示真;没有原子布尔射线)。这个类的作用就像一个数组,其元素都是 不稳定的 这样就能很好地解决我们所有的问题。或者,您可以声明两个可变变量, boolean in0 和 boolean in1 ,并更新它们,而不是使用布尔数组。

除非您对彼得森的算法有特定的需求(当使用Java这样的高级语言时,这将是奇怪的),我建议您查看内置在语言中的同步设施。

例如,您可以在本书中找到关于“比赛条件和 “互斥”在Java中有用: http://java.sun.com/developer/Books/performance2/chap3.pdf

在粒子中:

Java提供内置支持 等待这个州的变化通过 条件的概念。条件 不过,有点用词不当, 因为这完全取决于用户 是否有条件 发生。此外,条件 无需特别真实或 错误的。使用条件必须 熟悉三种关键方法 对象类的:

_窋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;
    }
}

请随时发表评论,我们将不胜感激:)

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

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

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