Алгоритм Деккера для 3 процессов (не работает)

Question

Я пытаюсь сделать простую программу с алгоритмом Деккера, но с 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 тоже войти, если не его ход, он ждет. Та же процедура с Нитью Q и R.

• С 2000000 итераций: программа не работает
• С 200 итерациями: программа иногда работает

Я предполагаю, что алгоритм Деккера не работает для 3 процессов, но мне нужно знать, правильный ли мой код и почему моя программа не работает.

Благодарю.

Answer 1

Когда вы пытаетесь понять, работает ли какая-либо конкретная реализация алгоритма, подумайте об этом ("доказательство" правильности) или протестируйте ее.
С вашей реализацией Q назначать PID для turnи не присоединять (создавать, запускать и) R,
При рефакторинге использовать экземпляры только одного запускаемого класса: volatile тип[] объявляет переменную ссылку на массив типа - вам нужно что-то еще.

С более чем двумя процессами, ваше расширение будет голодать процесс, который, без необходимости, устанавливает turn на идентификатор процесса, который никогда не будет установлен turn к любому другому значению (выполнено или завершено), а любые другие процессы не выполнены или не завершены.

---

Трудная часть будет mutual exclusion for 3 processes […] without [changing Dekker's] entire algorithm - вы можете обнаружить историю внедрения MutEx.
Ранние были созданы с моделью памяти, сильно отличающейся от модели памяти JVM.

Answer 2

Алгоритм Деккера не работает.

Позвольте этому понять, что классический алгоритм согласованности не работает и не работает примерно с 1980 года, когда IBM начала выпускать многопроцессорные мейнфреймы.

Аппаратная модель памяти слишком слаба; что происходит, так это то, что один из потоков наблюдает, как память записывает в неправильном порядке, потому что один ЦП может записывать в переменную, а другой ЦП может читать из нее.

Источник: https://jakob.engbloms.se/archives/65

Любопытный случай: на каком-то экзамене у них был алгоритм Деккера, а потом алгоритм Петерсона (безымянный) и какое-то обсуждение, доверять или нет более быстрому алгоритму. Мой ответ был таким: я не доверяю ни одному из этих двух, а только инструкциям по атомарной сборке. Я предполагаю, что они искали некоторую неприязнь к риску. Не имеет значения. Они получили «не писать примитивы синхронизации на языках высокого уровня». Оказывается, я был прав больше, чем думал. Моя логика заключается в том, что инструкции по сборке легче доказать. Оказывается, они также заботятся о модели памяти.