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

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

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

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

Потоки 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.

Эта страница в последний раз была отредактирована 17 апреля 2023 в 23:02.