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

Алгоритм Петерсона — алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.