Алгоритм Петерсона: взаимное исключение двух потоков

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

Ниже можно собрать конкретный запрос по своей задаче - разобрать трассировку выполнения, доказать корректность или сравнить алгоритм с альтернативами - и получить пошаговый разбор.

Зачем нужно взаимное исключение

Представим, что два потока увеличивают общий счётчик: $counter = counter + 1$. На уровне процессора это три действия - прочитать значение, прибавить единицу, записать обратно. Если планировщик переключит потоки между чтением и записью, оба прочитают одно и то же старое значение, оба прибавят единицу и оба запишут одинаковый результат. Одно увеличение потеряется. Это состояние гонки (race condition).

Чтобы такого не было, участок кода, работающий с общими данными, должен выполняться только одним потоком в каждый момент времени. Это и есть взаимное исключение (mutual exclusion). Алгоритм Петерсона даёт протокол входа и выхода, который гарантирует это свойство для двух потоков, опираясь лишь на чтение и запись общих переменных.

Рассчитать для своей задачи

Идея алгоритма: два флага и переменная turn

Алгоритм оперирует тремя общими переменными. Два булевых флага $flag[0]$ и $flag[1]$ сообщают: «поток номер $i$ хочет войти в критическую секцию». Целочисленная переменная $turn$ хранит номер потока, чья очередь уступать. Поток с номером $i$ перед входом выполняет:

$$\begin{aligned} &\text{flag}[i] := \text{true} \\ &\text{turn} := 1 - i \\ &\textbf{while } (\text{flag}[1-i] = \text{true} \ \wedge \ \text{turn} = 1-i) \ \textbf{do } \text{ничего} \end{aligned}$$

Идея в двух сигналах. Флаг говорит о намерении: «я хочу войти». Переменная $turn$ разрешает спор о приоритете: поток вежливо уступает очередь сопернику, записывая в $turn$ чужой номер. Войти он сможет, только если соперник либо не претендует ($flag[1-i] = false$), либо сам уступил очередь ($turn = i$). После работы поток выходит, сбрасывая свой флаг: $flag[i] := false$.

Тонкость - в порядке двух присваиваний. Сначала поднимается флаг, и только потом выставляется $turn$. Если бы порядок был обратным, оба потока могли бы записать $turn$ так, что ни один не дождался бы своей очереди корректно.

Почему это работает: взаимное исключение

Докажем главное свойство: оба потока не могут оказаться в критической секции одновременно. Предположим обратное - пусть оба вошли. Значит, оба прошли цикл ожидания: для потока 0 ложно условие $(\text{flag}[1] \wedge \text{turn} = 1)$, для потока 1 ложно $(\text{flag}[0] \wedge \text{turn} = 0)$.

Перед входом каждый поднял свой флаг, поэтому в момент проверки $flag[0]$ и $flag[1]$ оба истинны. Тогда первое слагаемое в каждом условии истинно, и пройти цикл поток смог только потому, что ложно условие на $turn$. Получается, для потока 0 нужно $\text{turn} \ne 1$, а для потока 1 нужно $\text{turn} \ne 0$. То есть одновременно $\text{turn} = 0$ и $\text{turn} = 1$ - противоречие: переменная $turn$ хранит одно значение. Значит, предположение неверно и оба потока в секции быть не могут.

Ключевой приём доказательства - $turn$ действует как арбитр: какое бы значение в ней ни осталось последним, ровно один из спорящих потоков получает право входа.

Рассчитать для своей задачи

Отсутствие тупика и справедливость

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

Отсутствие тупика (deadlock-free): хотя бы один поток всегда сможет войти. Если оба ждут, переменная $turn$ равна либо 0, либо 1. Тот поток, на чей номер $turn$ не указывает, обнаружит ложное условие цикла и войдёт. Ситуации, когда оба крутятся в цикле бесконечно, возникнуть не может.

Ограниченное ожидание (bounded waiting): поток, желающий войти, ждёт не дольше одного прохода соперника. Как только соперник выходит и сбрасывает свой флаг, ждущий немедленно проходит. Даже если соперник тут же снова захочет войти, он сначала уступит очередь, записав $turn$, и пропустит того, кто ждал. Это свойство справедливости - никто не голодает (no starvation).

Сравните это с примитивной блокировкой через единственную переменную-замок: там быстрый поток может бесконечно перехватывать замок, а медленный голодать. Такая же забота о худшем случае и гарантиях лежит в основе анализа сложности в теории алгоритмов - например, при оценке цикломатической сложности кода с ветвлениями протокола входа.

Обобщение на N потоков: фильтр

Классический алгоритм Петерсона рассчитан строго на два потока. Для $N$ потоков существует обобщение - алгоритм-фильтр (filter lock). В нём $N-1$ уровень, и на каждом уровне отсеивается хотя бы один поток, как на лестнице: чтобы попасть на следующую ступень, поток выставляет свой уровень и уступает очередь, ждёт, пока выше него никого нет или кто-то уступил.

Идея та же, что в базовом случае, но повторённая по уровням: на каждом уровне работает та же связка «намерение плюс уступка очереди». В критическую секцию пройдёт лишь тот, кто поднялся на верхний уровень. Фильтр гарантирует взаимное исключение и отсутствие тупика, но честность у него слабее: ограниченное ожидание не гарантировано без дополнительных условий.

Подводный камень: переупорядочение памяти

Главная практическая проблема алгоритма Петерсона на современных процессорах - он не работает «как написано» без барьеров памяти. Доказательство корректности опирается на то, что записи и чтения происходят в том порядке, в каком стоят в коде. Реальные процессоры и компиляторы переупорядочивают операции с памятью ради скорости.

Чтобы алгоритм работал на реальном железе, между записью флага/$turn$ и чтением чужого флага нужен полный барьер памяти (memory fence), а сами переменные должны быть объявлены так, чтобы компилятор не кэшировал их в регистрах (в C это atomic с подходящим порядком, не просто volatile). Именно поэтому в продакшене используют готовые мьютексы, построенные на атомарных инструкциях процессора, а Петерсона держат как учебную и теоретическую конструкцию.

Сравнение с аппаратными примитивами

Современная синхронизация почти никогда не пишется на чистых чтениях и записях. Процессоры дают атомарные команды: test-and-set, compare-and-swap (CAS), fetch-and-add. Мьютекс или спинлок на CAS короче, быстрее и сразу работает на любом числе потоков.

В чём же ценность алгоритма Петерсона? Он доказывает фундаментальный факт: взаимное исключение в принципе достижимо без специальной аппаратной поддержки, на одних обычных переменных. Это теоретический результат уровня теоремы. На практике же выгоднее опереться на атомарные инструкции - они снимают проблему переупорядочения и масштабируются. Петерсон остаётся в учебниках как мостик между интуицией («просто поставлю флажок») и строгим пониманием гонок, барьеров и моделей памяти.

Частые ошибки

• Перепутан порядок присваиваний. Если выставить $turn$ раньше флага, доказательство ломается и появляется окно, в котором оба потока входят одновременно. Сначала $flag[i] := true$, затем $turn := 1 - i$.
• $turn := i$ вместо $turn := 1 - i$. Поток должен уступать очередь сопернику, записывая чужой номер. Запись своего номера превращает протокол в неработающий.
• Забыт сброс флага на выходе. Без $flag[i] := false$ после критической секции соперник навсегда останется в цикле ожидания - это тупик.
• Расчёт на работу без барьеров памяти. На ARM/POWER код «как в учебнике» нарушает взаимное исключение из-за переупорядочения. Нужны fence и атомарные переменные.
• Попытка применить к трём и более потокам. Базовый алгоритм только для двух. Для большего числа - фильтр-алгоритм или другие протоколы (Лампорта, Эйзенберга-МакГвайра).

FAQ

Чем алгоритм Петерсона отличается от алгоритма Деккера? Оба решают взаимное исключение для двух потоков без атомарных команд. Алгоритм Деккера старше и сложнее: он использует вложенную логику уступок с дополнительной проверкой флагов. Петерсон проще и элегантнее - одна переменная $turn$ заменяет всю громоздкую конструкцию Деккера, поэтому именно его обычно изучают первым.

Можно ли использовать алгоритм Петерсона в реальном коде на C или Java? Технически да, но только с явными барьерами памяти и атомарными переменными (std::atomic в C++, volatile плюс семантика happens-before в Java). Без них компилятор и процессор переупорядочат операции, и алгоритм перестанет гарантировать взаимное исключение. На практике берут готовый мьютекс - он быстрее и корректен по умолчанию.

Почему алгоритму нужны именно два сигнала - флаг и turn? Один флаг сообщает о намерении войти, но при одновременном намерении обоих не разрешает спор - оба будут ждать друг друга (тупик). Переменная $turn$ выступает арбитром: при ничьей она однозначно указывает, чья очередь уступить. Без неё нет гарантии отсутствия тупика, без флагов - нет информации о намерениях.

Коротко

Алгоритм Петерсона - классический протокол взаимного исключения для двух потоков на обычных общих переменных. Поток поднимает флаг намерения, уступает очередь сопернику через переменную $turn$ и ждёт, пока соперник не претендует или не уступил сам. Это гарантирует взаимное исключение, отсутствие тупика и ограниченное ожидание, что доказывается через арбитраж $turn$. Обобщение на $N$ потоков - фильтр-алгоритм. Главное ограничение: на современных процессорах со слабой моделью памяти алгоритм требует барьеров памяти, иначе переупорядочение записей нарушает корректность, поэтому в продакшене используют мьютексы на атомарных инструкциях, а Петерсона - как учебный и теоретический эталон.