Почему в алгоритме Петерсона требуются ограждения памяти

Question

bool in_critical[2] = {false,false}; 
int turn;

enter(int me, int other) {
  (S1:) in_critical[me] = true;
  (S2:) turn = other;

  while(in_critical[other] && (turn == other)) ;
}

exit(int me) {
  in_critical[me] = false;
}

выше простая реализация алгоритма Петерсона.

В разных онлайн-ресурсах говорится, что перед while(..) требуется ограничение памяти, чтобы предотвратить проблемы с out-of-order execution. Таким образом, порядок S1 and S2 не меняется.

Но я не могу определить точное созвездие, в котором это могло бы стать проблемой. Итак, мой вопрос: в каком именно переупорядочивании может возникнуть проблема?

Или, если это больше связано с проблемами согласованности. Так что, возможно, in_critical[me] никогда не будет записан, и оба процессора могут просто использовать его внутри (регистр процессора никогда не записывается в кеш). В этом случае оба процессора попадут в критическую секцию. И забор памяти заставил бы сделать in_critical[me] видимым.

Answer 1

Предположим, система может переупорядочить S1 и S2. Тогда можно одновременно поместить оба процесса в критическую секцию.

P0 начинается с установки turn = 1 (переупорядочено). Далее идет P1, устанавливая in_critical[1] = true и turn = 0, затем считывает false из in_critical[0] в состоянии while и входит в критическую секцию. Теперь у P0 есть черед: запись in_critical[0] = true (переупорядочена), чтение true из in_critical[1], но 0 из turn, поэтому P0 также входит в критическую секцию.