java - Dekker 的算法不适用于三个进程

Question

我试过修改著名的'Dekker's algorithm '，因此您可以同时将其与三个进程一起使用。这是我的代码:

package DekkersAlgorithm;

class DekkerAlg {
    /* Iterations done by each Thread */
    static final int iterations = 2000000;
    /* Shared variable */
    static volatile int sharedInteger = 0;
    /* P Thread for critical section */
    static volatile boolean wantp = false;
    /* Q Thread for critical section */  
    static volatile boolean wantq = false;
    /* Z Thread for critical section */ 
    static volatile boolean wantz = false;
    /* Thread turn */
    static volatile int turn = 1;

class P extends Thread {
    public void run() {
        for (int i=0; i<iterations; ++i) {
            /* No critical section */
            wantp = true;
            while (wantq || wantz) {
                if (turn == 2) {
                    wantp = false;
                    while (turn == 2)
                        Thread.yield();
                    wantp = true;
                }
            }

            /* Critical section */
            ++sharedInteger;
            /* End critical section */

            turn = 2;
            wantp = false;
        }
    }
}

class Q extends Thread {
    public void run() {
        for (int i=0; i<iterations; ++i) {
            /* No critical section */
            wantq = true;
            while (wantp || wantz) {
                if (turn == 1) {
                    wantq = false;
                    while (turn == 1)
                        Thread.yield();
                    wantq = true;
                }
            }

            /* Critical section */
            --sharedInteger;
            /* End critical section */

            turn = 1;
            wantq = false;
        }
    }
}

class Z extends Thread {
    public void run() {
        for (int i=0; i<iterations; ++i) {
            /* No critical section */
            wantz = true;
            while (wantp || wantq) {
                if (turn == 3) {
                    wantz = false;
                    while (turn == 3)
                        Thread.yield();
                    wantz = true;
                }
            }

            /* Critical section */
            ++sharedInteger;
            /* End critical section */

            turn = 3;
            wantz = false;
        }
    }
}

DekkerAlg() {
    Thread p = new P();
    Thread q = new Q();
    Thread z = new Z();
    p.start();
    q.start();
    z.start();

    try {
        p.join();
        q.join();
        z.join();
        System.out.println("The value of the sharedInteger is " + sharedInteger);
        System.out.println("It should be different from 0.");
    }
    catch (InterruptedException e) {}
}

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

它在低迭代时运行良好，但当我将此变量设置为 500(+) 时，程序有时无法完成。我认为 livelock 发生在最后两个 Threads 之间，但我需要有关如何解决它的线索。

你能帮帮我吗？

Answer 1

我认为您没有正确扩展turn。在 Dekker 中，这意味着如果双方都愿意，谁可以进入他们的 CS；在这里它似乎意味着如果其他人想要进入他们的CS，谁必须等待。对于 2 个过程，它们是直接相反的； 3 个，没那么多。

一种方法是拥有一个进程列表，指定在争用 CS 时谁必须等待谁。这样，如果 P & Q 想进入，而 Z 刚刚退出，Z 将被移动到列表的末尾，这样你就可以在 P & Q 之间进行选择。(如果你能表示这个“列表”在某种程度上，对它的修改可以是原子的，这是可行的，因为只有 6 种不同的模式可以表示，更好!)