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

Алгоритм Петерсона — алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, так как не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т. д., используются только общие переменные памяти и цикл для ожидания входа в критическую секцию исполняемого кода.

Принцип работы

Перед тем, как начать исполнение критической секции кода, поток должен вызвать специальную процедуру (назовем её lock()) со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру (назовем её unlock()), после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип алгоритмом Петерсона для двух потоков.

Код на языке C++

class PetersonMutex
{
public:
    PetersonMutex()
    {
        want[0].store(false);
        want[1].store(false);
        waiting.store(0);
    }

    void lock(int threadId)
    {
		int other = 1 - threadId;
        want[threadId].store(true); // индикатор интереса текущего потока
        waiting.store(threadId); // говорим, что этот поток будет ждать, если понадобится
        /* Цикл ожидания. Мы находимся в этом цикле, если второй процесс выполняет свою 
        критическую секцию. Когда второй процесс выйдет из критической секции, выполнится
        процедура unlock(int threadId), флаг заинтересованности (want[other]) 
        станет равен false, и цикл закончится. */
        while (want[other].load() && waiting.load() == threadId) {
            // wait
        }
    }

    void unlock(int threadId) {
        want[threadId].store(false);
    }

private:
    std::array<std::atomic<bool>, 2> want; // флаги заинтересованности потоков
    std::atomic<int> waiting; // номер ждущего потока
};

Для наглядности рассмотрим два сценария исполнения параллельных потоков с номерами 0 и 1.

Потоки вызывают lock последовательно

Время	Поток 0	Поток 1
t1	int other = 1;
t2	want[0] = true;
t3	waiting = 0;
t4	while (waiting == 0 && want[1]);
t5	Критическая область кода	int other = 0;
t6		want[1] = true;
t7		waiting = 1;
t8		while (waiting == 1 && want[0]);
t9		while (waiting == 1 && want[0]);
t10	want[0] = false;	Критическая область кода
t11
t12
t13		want[1] = false;

Поток с номером 0 вызывает lock, задавая этим индикатор своей «заинтересованности», устанавливая флаг очереди так, чтобы уступить очередь исполнения потоку номер 1. Поскольку последний пока еще не «заинтересован» в попадании в критическую область, выполнение сразу же возвращается из lock, и поток 0 входит в неё. Теперь lock вызывается потоком 1, для которого также выполняются описанные выше действия. Но так как поток 0 все еще «заинтересован» (want[0] == true), выполнение остается в lock — поток 1 в ожидании (в таблице это выражено повторением инструкции для цикла 'while'). Как только поток 0 вызывает unlock и сбрасывает флаг своей «заинтересованности», поток 1 входит в критическую область и в конце сам вызывает unlock.

Потоки вызывают lock почти одновременно

Время	Поток 0	Поток 1
t1	int other = 1;
t2		int other = 0;
t3		want[1] = true;
t4	want[0] = true;
t5	waiting = 0;
t6		waiting = 1;
t7		while (waiting == 1 && want[0]);
t8		while (waiting == 1 && want[0]);
t9	while (waiting == 0 && want[1]);
t10	Критическая область кода	while (waiting == 1 && want[0]);
t11		while (waiting == 1 && want[0]);
t12		while (waiting == 1 && want[0]);
t13	want[0] = false;	Критическая область кода
t14
t15
t16		want[1] = false;

Потоки почти одновременно вызывают lock, устанавливая тем самым флаг своей «заинтересованности» и уступая очередь выполнения конкурирующему потоку посредством установки значения переменной waiting. Поскольку последним это делает поток 1, ему уже придется ждать в цикле, в то время как поток 0 беспрепятственно входит в критическую область кода. Ожидание потока 1, как и в предыдущей таблице, выражено повторением инструкции while для цикла ожидания. После того, как поток 0 выходит из критической области и сбрасывает флаг своей «заинтересованности», поток 1 продолжает своё исполнение и в конце сам сбрасывает соответствующий флаг вызовом unlock.

Корректность алгоритма

Взаимное исключение

Потоки 0 и 1 никогда не могут попасть в критическую секцию в один момент времени: если 0 вошёл в секцию, он установил want[0] в true. Тогда либо want[1] == false (тогда поток 1 не в критической секции), либо waiting == 1 (тогда поток 1 пытается войти в критическую секцию и крутится в цикле), либо поток 1 пытается войти в критическую секцию после установки want[1] == true, но до установки waiting и цикла. Таким образом, если оба процесса находятся в критической секции, должно быть want[0] && want[1] && waiting == 0 && waiting == 1, но такого не может быть одновременно и мы пришли к противоречию.

Свобода от взаимной блокировки

Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной waiting, что невозможно.

Свобода от голодания

Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения unlock и повторного захода в lock процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.

См. также

• Алгоритм Деккера
• Алгоритм пекарни Лампорта

Литература

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