Алгоритм Петерсона в Java?

На самом деле, поток A может записывать в переменную x, а затем в переменную y, устанавливая связь между этими двумя действиями в потоке A. Но поток B может читать x и y, и B имеет право получить новое значение y до появления нового значения x. Спецификация говорит:

Более конкретно, если два действия имеют общую связь «происходит до», они не обязательно должны казаться произошедшими в этом порядке для любого кода, с которым они не имеют общей связи «произошло до».

Как это исправить? Для обычного доступа к полям достаточно ключевого слова volatile:

Запись в изменчивую переменную (§8.3.1.4) v синхронизируется со всеми последующими операциями чтения v любым потоком (где последующее определяется в соответствии с порядком синхронизации).

синхронизируется с является более сильным условием, чем "происходит-до", и, поскольку "происходит-до" является транзитивным, если поток A хочет, чтобы поток B видел свои записи в x и y, ему просто нужно записать в volatile переменная z после записи x и y. Поток B должен прочитать из z перед чтением x и y, и он гарантированно увидит новые значения x и y.

В решении Габриэля мы видим такую ​​закономерность: запись происходит в in, которая не будет видна другим потокам, но затем происходит запись в turn, так что другие потоки гарантированно увидят обе записи, пока они читают turn первыми.

К сожалению, условное выражение цикла while является обратным: чтобы гарантировать, что поток не увидит устаревшие данные для in, цикл while должен сначала прочитать из turn:

    // ...
    while (turn == other() && in[other()]) {
        // ...

Имея в виду это исправление, большая часть остального решения в порядке: в критической секции нас не волнует устаревание данных, потому что мы находимся в критической секции! Единственный другой недостаток возникает в конце: Runnable устанавливает in[id] в новое значение и завершает работу. Будет ли гарантировано, что другой поток увидит новое значение in[id]? Спецификация говорит нет:

Последнее действие в потоке T1 синхронизируется с любым действием в другом потоке T2, обнаружившем завершение T1. T2 может выполнить это, вызвав T1.isAlive() или T1.join().

Итак, как мы это исправим? Просто добавьте еще одну запись в turn в конце метода:

    // ...
    in[id] = false;
    turn = other();
}
// ...

Поскольку мы переупорядочили цикл while, другой поток гарантированно увидит новое ложное значение in[id], потому что запись в in[id] происходит до того, как произойдет запись в turn, до того, как произойдет чтение из turn, до того, как произойдет чтение из in[id].

Излишне говорить, что без метрики тонны комментариев этот метод хрупок, и кто-то может прийти и что-то изменить и тонко нарушить правильность. Простого объявления массива volatile недостаточно: как объясняется в этом поток Билла Пью (одного из ведущих исследователей модель памяти Java), объявление массива volatile делает обновления массива reference видимыми для других потоков. Обновления элементов массива не обязательно видны (отсюда и все циклы, через которые нам только что пришлось пройти, используя другую переменную volatile для защиты доступа к элементам массива).

Если вы хотите, чтобы ваш код был ясным и лаконичным, оставьте его таким, какой он есть, и измените in на AtomicIntegerArray (используйте 0 для false, 1 для true; AtomicBooleanArray не существует). Этот класс действует как массив, все элементы которого равны volatile, и поэтому прекрасно решит все наши проблемы. В качестве альтернативы вы можете просто объявить две изменчивые переменные, boolean in0 и boolean in1, и обновить их вместо использования логического массива.