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

Алгоритм Деккера решает задачу взаимных исключений, но достаточно сложным путем, корректность которого не так легко доказать. Петерсон (Peterson) предложил простое и элегантное решение [РЕТЕ81]. Как и ранее, глобальная переменная flag указывает положение каждого процесса по отношению к взаимоисключению, а глобальная переменная turn разрешает конфликты одновременности. Алгоритм представлен в листинге 5.3.

Листинг 5.3. Алгоритм Петерсона для двух процессов

boolean flag[2];
int turn;
void P0()
{
while (true)
{
flag[0] = true;
turn = 1;
while(flagfl] && turn == 1)
/* Ничего не делать */;
/* Критический раздел */;
flagfO] = false;
/* Остальной код */;
}
}
void PI () I
{
while(true)
{
flag[l] = true;
turn = 0;
while(flag[0] && turn == 0)
/* Ничего не делать */;
/* Критический раздел */;
flagfl] = false;
/* Остальной код */;
}
}
void main ()
{
flag[0] = false;
flag[l] = false;
parbegin(PO,PI);
}

Выполнение условий взаимоисключения легко показать. Рассмотрим процесс Р0. После того как flag[0] установлен им равным true, P1 войти в критический раздел не может. Если же Р1 уже находится в критическом разделе, то flag[l] = true и для Р0 вход в критический раздел заблокирован. Однако взаимная блокировка в данном алгоритме предотвращена. Предположим, что Р0 заблокирован в своем цикле while. Это означает, что flag[l] равен true, a turn = 1. Р0 может войти в критический раздел, когда либо flag[l] становится равным false, либо turn становится равным 0. Рассмотрим три исчерпывающих случая.

1. Р1 не намерен входить в критический раздел. Такой случай невозможен,
   поскольку при этом выполнялось бы условие flag[l] = false.
2. P1 ожидает вход в критический раздел. Такой случай также невозможен,
   поскольку если turn = 1, то P1 способен войти в критический раздел.
3. Р1 циклически использует критический раздел, монополизировав доступ к
   нему. Этого не может произойти, поскольку Р1 вынужден перед каждой
   попыткой входа в критический раздел дать такую возможность процессу
   Р0, устанавливая значение turn равным 0.

Следовательно, у нас имеется простое решение проблемы взаимных исключений для двух процессов. Впрочем, алгоритм Петерсона легко обобщается на случай п процессов [HOFR90].