Что произойдет, если мы изменим порядок команд в алгоритме Петерсона для взаимного исключения?

Я читал об алгоритме Петерсона для взаимного исключения. Затем возник вопрос, что произойдет, если мы изменим порядок первой и второй команд в цикле do ... while? Я не вижу, чтобы что-то происходило, если мы это сделаем ... Кто-нибудь может сказать мне, что мне не хватает?

do {
     flag[me] = TRUE;
     turn = other;
     while (flag[other] && turn == other)
             ;
     critical section
     flag[me] = FALSE;
     remainder section
   } while (TRUE);

command algorithm mutual-exclusion
person Saraki    schedule 15.03.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Если вы измените порядок этих двух команд, вы получите эти два процесса, работающих одновременно:

turn = 1;                       |      turn = 0;
flag[0] = true;                 |      flag[1] = true;
while(flag[1] && turn==1)       |      while(flag[0] && turn==0)
    ;                           |          ;
critical section 0              |      critical section 1
flag[0] = false;                |      flag[1] = false;

Это может произойти в следующем порядке:

Process 1: turn = 0;
Process 0: turn = 1;
Process 0: flag[0] = true;
Process 0: while(flag[1] && turn==1) // terminates, since flag[1]==false
Process 0: enter critical section 0
Process 1: flag[1] = true;
Process 1: while(flag[0] && turn==0) // terminates, since turn==1
Process 1: enter critical section 1
Process 0: exit critical section 0
Process 1: exit critical section 1

Что нарушает критерий взаимного исключения.

person Anton    schedule 16.03.2014