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

Алгоритм Петерсона — алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 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
t ₁	`int other = 1;`
t ₂	`want[0] = true;`
t ₃	`waiting = 0;`
t ₄	`while (waiting == 0 && want[1]);`
t ₅	`Критическая область кода`	`int other = 0;`
t ₆		`want[1] = true;`
t ₇		`waiting = 1;`
t ₈		`while (waiting == 1 && want[0]);`
t ₉		`while (waiting == 1 && want[0]);`
t ₁₀	`want[0] = false;`	`Критическая область кода`
t ₁₁
t ₁₂
t ₁₃		`want[1] = false;`

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

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

Время	Поток 0	Поток 1
t ₁	`int other = 1;`
t ₂		`int other = 0;`
t ₃		`want[1] = true;`
t ₄	`want[0] = true;`
t ₅	`waiting = 0;`
t ₆		`waiting = 1;`
t ₇		`while (waiting == 1 && want[0]);`
t ₈		`while (waiting == 1 && want[0]);`
t ₉	`while (waiting == 0 && want[1]);`
t ₁₀	`Критическая область кода`	`while (waiting == 1 && want[0]);`
t ₁₁		`while (waiting == 1 && want[0]);`
t ₁₂		`while (waiting == 1 && want[0]);`
t ₁₃	`want[0] = false;`	`Критическая область кода`
t ₁₄
t ₁₅
t ₁₆		`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 процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.