0

i'm trying to do a simple program with Dekker's Algorithm but with 3 processes. Here's my code:

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();
    }
}

I don't know if my code is 100% correct. If P wants to enter in the CS, first, he has to check if Q or R wants to enter too, if it isn't his turn, he waits. Same procedure with Thread Q and R.

  • With 2000000 iterations: the program doesn't work
  • With 200 iterations: the program works sometimes

I guess Dekker's Algorithm doesn't work for 3 processes but i need to know if my code is correct and why my program fail.

Thanks.

4

2 回答 2

0

当试图了解算法的任何给定实现是否有效时，请对其进行推理（“正确性证明”）或对其进行测试。
通过您的实现，Q将Pid 分配给turn，并且不要（实例化、启动和） join R。
当重构为只使用一个可运行类的实例时：volatile type声明一个对类型[]数组的 volatile 引用——你需要别的东西。

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

困难的部分将是mutual exclusion for 3 processes […] without [changing Dekker's] entire algorithm- 您可能会发现自己追溯 MutEx 实现的历史。早期的内存模型是使用与JVM 内存模型
大不相同的内存模型创建的。

于 2016-11-17T18:31:06.750 回答
0

Dekker 算法不起作用。

让我们深入了解一下，经典的一致性算法不起作用，并且自 1980 年左右 IBM 开始发布多 CPU 大型机以来一直不起作用。

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

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

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

于 2022-01-10T04:18:31.707 回答