23-10-2023
Алгоритм Петерсона — программный алгоритм взаимного исключения потоков исполнения кода, разработанный Г. Петерсоном в 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.
Алгоритм Петерсона.