Алгоритм Петерсона
Алгоритм
Петерсона, программный алгоритм взаимного
исключения потоков исполнения кода,
разработанный Г. Петерсоном в
1981 г. Хотя изначально был сформулирован
для 2-х поточного случая, алгоритм может
быть обобщён для произвольного количества
потоков. Алгоритм условно называется
программным, так как не основан на
использовании специальных команд
процессора для запрета прерываний,
блокировки шины памяти и т. д.,
используются только общие переменные
памяти и цикл для ожидания входа в
критическую секцию исполняемого кода.
Перед тем как
начать исполнение критической
секции кода (то есть региона кода,
обращающегося к защищаемым совместно
используемым ресурсам), поток должен
вызвать специальную процедуру (назовем
ее EnterRegion) со своим номером в качестве
параметра. Она должна организовать
ожидание потока своей очереди
входа в критическую секцию. После
исполнения критической секции и выхода
из нее, поток вызывает другую процедуру
(назовем ее LeaveRegion), после чего уже
другие потоки смогут войти в критическую
область. Посмотрим как реализуется этот
общий принцип А.П. для
2-х потоков.
Код EnterRegion и LeaveRegion на
языке C++
bool interested[2];
int turn;
void
EnterRegion(int threadId)
{
int other = 1 -
threadId; // Идентификатор второго
потока
interested[threadId] =
true; // Индикатор интереса текущего
потока
turn = other;
// Флаг очереди исполнения
/*
Цикл ожидания, мы находимся в этом цикле,
если второй процесс выполняет свою
критическую
секцию. Как второй процесс выйдет из
критической секции, выполнится
процедура
LeaveRegion(int threadId), флаг заинтересованности
(interested[other])
станет
равен false, и цикл закончится. */
while (turn == other &&
interested[other]);
}
void
LeaveRegion(int threadId)
{
interested[threadId] =
false;
}
Для наглядности
рассмотрим два сценария исполнения
параллельных потоков с номерами 0 и 1.
1) Потоки
вызывают EnterRegion последовательно
|
Время |
Поток
0 |
Поток
1 |
|
t1 |
int
other = 1; |
|
|
t2 |
interested[0]
= true; |
|
|
t3 |
turn =
1; |
|
|
t4 |
while
(turn == 1 && interested[1]); |
|
|
t5 |
Критическая
область кода |
int
other = 0; |
|
t6 |
interested[1]
= true; |
|
t7 |
turn =
0; |
|
t8 |
while
(turn == 0 && interested[0]); |
|
t9 |
while
(turn == 0 && interested[0]); |
|
t10 |
interested[0]
= false; |
Критическая
область кода |
|
t11 |
|
|
t12 |
|
|
t13 |
|
interested[1]
= false; |
Поток
с номером 0 вызывает EnterRegion,
задавая этим индикатор своей
«заинтересованности», устанавливая
флаг очереди так, чтобы уступить очередь
исполнения потоку номер 1. Поскольку
последний пока еще не «заинтересован»
в попадании в критическую область,
выполнение сразу же возвращается
из EnterRegion, и поток 0 входит в нее.
Теперь EnterRegionвызывается потоком 1,
для которого также выполняются описанные
выше действия. Но так как поток 0 все
еще «заинтересован» (interested[0] == true),
выполнение остается в EnterRegion —
поток 1 в ожидании (в таблице это
выражено повторением инструкции для
цикла 'while'). Как только
поток 0 вызывает LeaveRegion и
сбрасывает флаг своей «заинтересованности»,
поток 1входит в критическую область
и в конце сам вызывает LeaveRegion.
2) Потоки
вызывают EnterRegion почти одновременно
|
Время |
Поток
0 |
Поток
1 |
|
t1 |
int
other = 1; |
|
|
t2 |
|
int
other = 0; |
|
t3 |
|
interested[1]
= true; |
|
t4 |
interested[0]
= true; |
|
|
t5 |
turn =
1; |
|
|
t6 |
|
turn =
0; |
|
t7 |
|
while
(turn == 0 && interested[0]); |
|
t8 |
|
while
(turn == 0 && interested[0]); |
|
t9 |
while
(turn == 1 && interested[1]); |
|
|
t10 |
Критическая
область кода |
while
(turn == 0 && interested[0]); |
|
t11 |
while
(turn == 0 && interested[0]); |
|
t12 |
while
(turn == 0 && interested[0]); |
|
t13 |
interested[0]
= false; |
Критическая
область кода |
|
t14 |
|
|
t15 |
|
|
t16 |
|
interested[1]
= false; |
Потоки
почти одновременно вызывают EnterRegion,
устанавливая тем самым флаг своей
«заинтересованности» и уступая очередь
выполнения конкурирующему потоку
посредством установки значения
переменной turn. Поскольку последним
это делает поток 1, ему уже придется
ждать в цикле, в то время как
поток 0 беспрепятственно входит
в критическую область кода. Ожидание
потока 1, как и в предыдущей таблице,
выражено повторением инструкции while для
цикла ожидания. После того, как
поток 0 выходит из критической
области и сбрасывает флаг своей
«заинтересованности», поток 1 продолжает
свое исполнение и в конце сам сбрасывает
соответствующий флаг вызовом LeaveRegion.
Лит.: Э. Таненбаум Современные
операционные системы = Modern Operating
Systems — «Питер», 2004. — С. 1040.
— ISBN 5-318-00299-4.
