В главе 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 может читать мусор.
Чего мне не хватает?