Dekker 的 3 个进程算法（不起作用）

Question

我正在尝试使用 Dekker 算法编写一个简单的程序，但有 3 个进程。这是我的代码：

class DekkerAlg {

static final int iter = 2000000;
static volatile int sharedResource = 0;
/* Thread P wants to enter in the CS */
static volatile boolean wantp = false;
/* Thread Q wants to enter in the CS */  
static volatile boolean wantq = false;
/* Thread R wants to enter in the CS */  
static volatile boolean wantr = false;
/* Who's next? */
static volatile int turn = 1;

    class P extends Thread {
        public void run() {
            for (int i=0; i<iter; ++i) {
                wantp = true;
                while (wantq || wantr) {
                    if (turn == 2 || turn == 3) {
                        wantp = false;
                        while (turn == 2 || turn == 3)
                            Thread.yield();
                        wantp = true;
                    }
                }

                ++sharedResource;

                turn = 2;
                wantp = false;
            }
        }
    }

    class Q extends Thread {
        public void run() {
            for (int i=0; i<iter; ++i) {
                wantq = true;
                while (wantp || wantr) {
                    if (turn == 1 || turn == 3) {
                        wantq = false;
                        while (turn == 1 || turn == 3)
                            Thread.yield();
                        wantq = true;
                    }
                }

                --sharedResource;

                turn = 3;
                wantq = false;
            }
        }
    }

    class R extends Thread {
        public void run() {
            for (int i=0; i<iter; ++i) {
                wantr = true;
                while (wantp || wantq) {
                    if (turn == 1 || turn == 2) {
                        wantr = false;
                        while (turn == 1 || turn == 2)
                            Thread.yield();
                        wantr = true;
                    }
                }

                ++sharedResource;

                turn = 1;
                wantr = false;
            }
        }
    }

    DekkerAlg() {
        Thread p = new P();
        Thread q = new Q();
        Thread r = new R();
        p.start();
        q.start();
        r.start();

        try {
            p.join();
            q.join();
            r.join();
            System.out.println("Shared Resource value: " + sharedResource);
            System.out.println("Should be 2000000.");
        }
        catch (InterruptedException e) {}
    }

    public static void main(String[] args) {
        new DekkerAlg();
    }
}

我不知道我的代码是否 100% 正确。如果P要进入CS，首先要检查Q或R是否也想进入，如果还没轮到他，就等待。与 Thread Q 和 R 相同的过程。

迭代 2000000 次：程序无法运行
迭代 200 次：程序有时能运行

我想 Dekker 的算法不适用于 3 个进程，但我需要知道我的代码是否正确以及我的程序失败的原因。

谢谢。

Answer 1

当试图了解算法的任何给定实现是否有效时，请对其进行推理（"proof" 正确性）或对其进行测试。
在您的实施中，让 Q 将 P 的 ID 分配给 turn，并且不要（实例化、启动和）加入 R.
当重构仅使用一个可运行对象 class 的实例时：volatile type[] 声明对 type 数组的易失性引用 - 您还需要其他东西。

如果有两个以上的进程，您的扩展程序将使进程饿死，该进程在未完成的情况下将 turn 设置为永远不会将 turn 设置为任何其他值的进程的 ID（是完成或终止），以及任何其他既未完成也未终止的过程。

困难的部分将是 mutual exclusion for 3 processes […] without [changing Dekker's] entire algorithm - 您可能会发现自己正在追溯 MutEx 实现的历史。
早期的一个是使用与 JVM Memory Model.

大不相同的内存模型创建的

Answer 2

Dekker 的算法不起作用。

让我们明白这一点，经典的一致性算法不起作用，而且自 1980 年 IBM 开始发布多 CPU 大型机以来就一直没有起作用。

硬件内存模型太弱；发生的事情是其中一个线程观察到内存以错误的顺序写入，因为一个 CPU 可以写入变量而另一个 CPU 可以从中读取。

来源：https://jakob.engbloms.se/archives/65

一个奇怪的案例是在一些考试中他们有 Dekker 的算法，然后是 Peterson 算法（未命名）以及关于是否信任更快的算法的一些讨论。我的回答是我不信任这两个中的任何一个，只信任原子汇编指令。我的猜测是他们正在寻找一些规避风险的因素。没关系。他们得到了“不要用高级语言编写同步原语”。事实证明我比我想象的更正确。我的推理是汇编指令更容易证明。结果他们也负责内存模型。

Dekker 的 3 个进程算法（不起作用）

Dekker's Algorithm for 3 processes (Doesn't Work)

java

algorithm

concurrency

livelock