Почему алгоритм Петерсона не требует взаимного исключения на уровне доступа к памяти? - PullRequest
0 голосов
/ 19 января 2020

В главе 5 «Операционные системы» Сталлингса существует следующая проблема:

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

[..]

b. Алгоритм Петерсона.

Вот алгоритм Петерсона в псевдокоде из книги:

boolean flag[2];
int turn;
void P0()
{
    while (true) {
        flag [0] = true;
        turn = 1;
        while (flag [1] && turn == 1) /* do nothing */;
        /* critical section */;
        flag [0] = false;
        /* remainder */;
    }
}
void P1()
{
    while (true) {
        flag [1] = true;
        turn = 0;
        while (flag [0] && turn == 0) /* do nothing */;
        /* critical section */;
        flag [1] = false;
        /* remainder */
    }
}
void main()
{
    flag [0] = false;
    flag [1] = false;
    parbegin (P0, P1);
}

Мне трудно понять, как можно предположить, что взаимного исключения нет на уровне доступа к памяти.

Например: если мы не предполагаем, что записи turn = 0 и turn = 1 являются атомами c, то мне кажется, что они выполняются одновременно (или в параллельно) может гипотетически привести к turn, содержащему мусор.

Кроме того, если, например, P0 запускает flag[0] = true в то же время, когда P1 читает из flag[0], без атомарности, мне кажется, что P1 может читать мусор.

Чего мне не хватает?

...