Могут ли два процесса одновременно войти в состояние активного ожидания по алгоритму Петерсона?

Посмотрев на алгоритм Питерсона, эквивалентная реализация на C++ выглядит так:

#include <thread>
#include <atomic>
int main(){
  std::atomic<bool> flag[2] = {false,false};
  std::atomic<int> turn = {0};
  std::thread t1([&](){
     flag[0] = true;  // flag_set_0
     turn = 1;    // turn_set_0
     while(flag[1] && turn == 1){  // flag_read_0, turn_read_0
         //busy wait
     }
     // критическая секция
     flag[0] = false;
  });
  std::thread t2([&](){
     flag[1] = true;  // flag_set_1
     turn = 0;  // turn_set_1
     while(flag[0] && turn == 0){ // flag_read_1, turn_read_1
         //busy wait
     }
     // критическая секция
     flag[1] = false;
  });
  t1.join();
  t2.join();
}

В этой программе, если порядок выполнения таков:

flag[0] = true
turn = 1
flag[1] = true
while(flag[1] && turn == 1){} // true
turn = 0
while(flag[0] && turn == 0){} //true

Единственный полный порядок это
flag_set_0 < turn_set_0 < flag_set_1 < flag_read_0 < turn_read_0 < turn_set_1 < flag_read_1 < turn_read_1,

что является допустимым единым полным порядком без противоречий, поскольку он соблюдает ограничения, требуемые t1 и t2:

t1: flag_set_0 < turn_set_0 < flag_read_0 < turn_read_0
t2: flag_set_1 < turn_set_1 < flag_read_1 < turn_read_1

Это означает, что в программе оба потока могут одновременно войти в цикл ожидания и два бесконечных цикла сделают программу не завершенной, правильно ли я понимаю?

Да, они могут оба войти. Но один из них вошел, когда turn был другим, перед последним записью в него. На следующей итерации его условие цикла будет ложным. Это не взаимная блокировка.

Циклы ожидания проверяют как flag[other_thread], так и turn на каждой итерации, с противоположными условиями для turn, которые не могут быть истинными для обоих циклов бесконечно.

Да, я понимаю ваш смысл, единственная возможность заключается в том, что реализация не подчиняется [атомарные. порядок] p11 (должна в разумные сроки), так что она всегда видит, что turn соответствует условию, даже если другой поток изменил его. Но это не вина алгоритма, это вина реализаций, верно? В этой ситуации все операции в условии предшествовали изменению turn в едином полном порядке S, верно?

Это операции seq_cst, так что я не уверен, возможно ли даже задержанное видение после того, как оба цикла вошли в свои циклы ожидания. Это предполагает, что они оба прочитали turn после его записи.

Возможно, это просто деталь реализации, что реальное оборудование должно подождать, пока seq_cst запись станет глобально видимой, прежде чем seq_cst загрузка сможет перезагрузить её (или фактически все предыдущие seq_cst записи станут видимыми). Но если нет, то последняя присваивание turn= уже видимо для другого потока к тому времени, когда второй поток входит в свой цикл ожидания. Возможно, что никакие требования seq_cst не будут нарушены, если оба потока читают противоположные значения turn на протяжении нескольких итераций в этом случае; если так, то да, только требования по «должны» видимости предотвратят взаимную блокировку.

Если вы считаете, что хорошо известный алгоритм, который известен десятилетиями, неисправен, весьма вероятно, что вы ошиблись и должны продолжать искать причины, почему он не неисправен. (Или если вам нужно попросить о помощи в его понимании, по крайней мере, сформулируйте свой вопрос с предположением, что алгоритм правильный. Например: «Как алгоритм Питерсона избегает взаимной блокировки, когда оба потока входят в циклы ожидания?» Формулировка таким образом может побудить вас взглянуть на условия цикла еще раз, или нет.)