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

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

Cм. также

Алгоритм Деккера

Литература

• Э. Таненбаум Современные операционные системы = Modern Operating Systems. — «Питер», 2004. — С. 1040. — ISBN 5-318-00299-4