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

Алгоритм Петерсона — это программный алгоритм взаимного исключения для двух процессов (или потоков), позволяющий им безопасно обращаться к общему ресурсу, не допуская одновременного доступа (состояния гонки). Алгоритм был предложен американским учёным Гэри Петерсоном в 1981 году и является классическим решением проблемы критической секции для двух участников, не требующим аппаратной поддержки специальных инструкций (например, Test-and-Set или Compare-and-Swap), а использующим только общую память и атомарные операции чтения/записи.

История и контекст

Проблема критической секции (critical section) была сформулирована в 1960-х годах как одна из фундаментальных задач параллельного программирования. До появления алгоритма Петерсона существовали решения, основанные на строгом чередовании (например, алгоритм Деккера), но они были сложнее или требовали дополнительных предположений о порядке выполнения. Гэри Петерсон, работая в Университете Аризоны, предложил простое и элегантное решение, которое одновременно использует два флага — «желание войти» и «очередь» (turn). Алгоритм быстро стал частью учебных курсов по операционным системам и параллельным вычислениям.

Описание алгоритма

Алгоритм предназначен для двух процессов, обозначаемых как P0 и P1. Каждый процесс имеет свой флаг flag[i] (где i — номер процесса), который показывает, хочет ли процесс войти в критическую секцию. Также существует общая переменная turn, которая указывает, чья сейчас «очередь» уступать.

Псевдокод для процесса P0

`` flag[0] = true; // P0 хочет войти в критическую секцию turn = 1; // P0 уступает очередь процессу P1 while (flag[1] && turn == 1) { // ожидание: пока P1 хочет войти и его очередь } // критическая секция // ... работа с общим ресурсом ... flag[0] = false; // P0 выходит из критической секции ``

Для процесса P1 код симметричен: flag[1] = true; turn = 0; while (flag[0] && turn == 0);.

Ключевые свойства

• Взаимное исключение: в критической секции может находиться только один процесс в любой момент времени. Если оба процесса одновременно устанавливают свои флаги в true, то переменная turn гарантирует, что только один из них пройдёт цикл ожидания.
• Прогресс (отсутствие взаимной блокировки): если один процесс не хочет входить в критическую секцию (его флаг false), другой процесс не будет ждать бесконечно. Если оба хотят войти, решение принимается на основе turn — один из них обязательно пройдёт.
• Ограниченное ожидание (bounded waiting): процесс, который уступил очередь (установил turn в пользу другого), будет ждать не более одного входа другого процесса в критическую секцию. После выхода другого процесса его флаг становится false, и ожидающий процесс может войти.

Доказательство корректности

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

Предположим, что оба процесса одновременно находятся в критической секции. Тогда для P0: flag[0] == true и turn == 1 (иначе он бы не вышел из цикла). Для P1: flag[1] == true и turn == 0. Но turn не может одновременно быть равен и 0, и 1. Противоречие. Следовательно, одновременное нахождение невозможно.

Прогресс

Если только один процесс (например, P0) хочет войти, то flag[1] == false, и цикл while (flag[1] && turn == 1) сразу завершается, так как первое условие ложно. Если оба хотят войти, то turn устанавливается последним процессом, который выполнил присваивание. Например, если P0 установил turn = 1, а затем P1 установил turn = 0, то для P0 условие turn == 1 станет ложным, и он войдёт в критическую секцию. Таким образом, хотя бы один процесс всегда может войти.

Ограниченное ожидание

Если P0 уступил очередь (установил turn = 1), то P1 войдёт в критическую секцию. После выхода P1 устанавливает flag[1] = false. Теперь P0 может войти, так как условие flag[1] && turn == 1 станет ложным. Максимальное время ожидания P0 — один цикл выполнения P1.

Реализация на языках программирования

C (с использованием атомарных операций)

В реальных системах на C/C++ компилятор может оптимизировать чтение/запись переменных, поэтому для корректной работы требуется использование volatile или атомарных типов (например, std::atomic в C++11). Пример на C с использованием volatile:

```c

include <stdbool.h>

include <stdatomic.h>

volatile bool flag[2] = {false, false}; volatile int turn;

void process0() { while (1) { flag[0] = true; turn = 1; while (flag[1] && turn == 1) { // ожидание } // критическая секция flag[0] = false; // остальная часть } }

void process1() { while (1) { flag[1] = true; turn = 0; while (flag[0] && turn == 0) { // ожидание } // критическая секция flag[1] = false; // остальная часть } } ```

Python (с использованием threading)

В Python алгоритм можно реализовать с помощью общей памяти, но из-за GIL (Global Interpreter Lock) состояние гонки в CPython маловероятно, однако для учебных целей код корректен:

```python import threading

flag = [False, False] turn = 0

def process0(): global flag, turn while True: flag[0] = True turn = 1 while flag[1] and turn == 1: pass

критическая секция

flag[0] = False

def process1(): global flag, turn while True: flag[1] = True turn = 0 while flag[0] and turn == 0: pass

критическая секция

flag[1] = False ```

Ограничения и недостатки

• Только для двух процессов: алгоритм не обобщается напрямую на произвольное число процессов. Для N процессов существуют более сложные алгоритмы (например, алгоритм булочной Лампорта).
• Активное ожидание (busy waiting): процесс, ожидающий входа в критическую секцию, непрерывно выполняет цикл, что тратит процессорное время. В современных системах это неэффективно, поэтому на практике используются блокирующие примитивы (мьютексы, семафоры).
• Зависимость от модели памяти: алгоритм предполагает, что операции чтения и записи атомарны и упорядочены. На архитектурах со слабой моделью памяти (например, ARM, PowerPC) без барьеров памяти алгоритм может давать сбои. Для корректной работы требуется использование memory_order в C++11 или volatile с барьерами.
• Неприменимость для реальных многопроцессорных систем без модификаций: из-за кэширования и переупорядочивания инструкций компилятором или процессором.

Применение и значение

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

Интересные факты

• Гэри Петерсон опубликовал алгоритм в 1981 году в статье «Myths About the Mutual Exclusion Problem» (журнал Information Processing Letters).
• Алгоритм Петерсона иногда ошибочно приписывают Деккеру, но Деккер предложил более сложное решение в 1965 году.
• В 2004 году была обнаружена ошибка в реализации алгоритма на некоторых процессорах Intel Itanium из-за особенностей их архитектуры, что подтвердило важность учёта модели памяти.

Источники

• Peterson, G. L. (1981). «Myths About the Mutual Exclusion Problem». Information Processing Letters, 12(3), 115–116.
• Tanenbaum, A. S., & Bos, H. (2015). «Modern Operating Systems» (4th ed.). Pearson. Глава 2.3.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). «Operating System Concepts» (10th ed.). Wiley. Глава 6.2.
• Herlihy, M., & Shavit, N. (2012). «The Art of Multiprocessor Programming» (2nd ed.). Morgan Kaufmann. Глава 2.