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

Question

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.

Answer 1

When trying to get an idea if any given implementation of an algorithm works, reason about it ("proof" of correctness) or test it.
With your implementation, have Q assign P's id to turn, and don't (instantiate, start, and) join R.
When refactoring to use instances of just one runnable class: volatile type[] declares a volatile reference to an array of type - you need something else.

With more than two processes, your extension will starve the process that, without being done, sets turn to the id of a process that will never set turn to any other value (is done or terminated), and any other processes neither done or terminated.

---

The difficult part will be mutual exclusion for 3 processes […] without [changing Dekker's] entire algorithm - you may find yourself retracing the history of MutEx implementations.
Early one were created with a model of memory much different from the JVM Memory Model.

Answer 2

Dekker's Algorithm doesn't work.

Let this sink in, the classic algorithm for consistency does not work and has not worked since about 1980 when IBM started releasing multi-CPU mainframes.

The hardware memory model is too weak; what happens is one of the threads observes the memory writes in the wrong order because one CPU can write to a variable while another CPU can read from it.

Source: https://jakob.engbloms.se/archives/65

A curious case was on some exam they had the Dekker's algorithm, and then the Peterson algorithm (unnamed) and some discussion on whether or not to trust the faster algorithm. My answer was I don't trust either of these two but only the atomic assembly instructions. My guess is they were looking for some risk-averseness. Doesn't matter. They got "don't write synchornization primitives in high-level languages". Turns out I was more right than I thought. My line of reasoning is was the assembly instructions are easier to prove. Turns out they also take care of the memory model.