Алгоритм пекарни

Алгоритм пекарни (англ. Bakery algorithm) — это алгоритм взаимного исключения для нескольких процессов (потоков), работающих в общей памяти, который гарантирует отсутствие взаимных блокировок, голодания и обеспечивает справедливое распределение ресурсов. Разработан американским учёным Лесли Лампортом в 1974 году. Название алгоритма происходит от аналогии с работой пекарни, где клиенты получают номерки и обслуживаются в порядке возрастания номеров.

История и контекст создания

В начале 1970-х годов, с развитием многозадачных операционных систем и многопроцессорных вычислительных систем, остро встала проблема синхронизации доступа к разделяемым данным. Существовавшие на тот момент решения, такие как алгоритм Деккера и алгоритм Петерсона, были рассчитаны только на два процесса. Лесли Лампорт, работавший в компании Xerox PARC, предложил обобщённый алгоритм, пригодный для произвольного числа процессов. Алгоритм был опубликован в 1974 году в статье «A New Solution of Dijkstra’s Concurrent Programming Problem» в журнале Communications of the ACM. Алгоритм пекарни стал одним из первых строго доказанных решений проблемы взаимного исключения для n процессов, не использующих аппаратных инструкций типа test-and-set или compare-and-swap.

Принцип работы

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

Основные переменные

Для реализации алгоритма используется два глобальных массива, разделяемых всеми процессами:

• choosing[i] — булевый массив, показывающий, находится ли процесс i в процессе выбора номера (1 — да, 0 — нет).
• number[i] — целочисленный массив, хранящий текущий номер процесса i (0 означает, что процесс не участвует в соревновании).

Псевдокод

Для процесса с индексом i (от 0 до N-1) алгоритм выглядит следующим образом:

``` while (true) { / Предпротокол / choosing[i] = 1; number[i] = max(number[0], number[1], ..., number[N-1]) + 1; choosing[i] = 0;

for (j = 0; j < N; j++) { while (choosing[j] == 1) { / ждать, пока процесс j выбирает номер / } while ((number[j] != 0) && ((number[j] < number[i]) || ((number[j] == number[i]) && (j < i)))) { / ждать / } }

/ Критическая секция / // ... работа с разделяемыми данными ...

/ Постпротокол / number[i] = 0;

/ Некритическая секция / // ... остальная работа процесса ... } ```

Пояснение работы

1. Выбор номера: процесс устанавливает choosing[i] = 1, вычисляет новый номер как максимальный среди всех текущих номеров плюс 1, затем сбрасывает choosing[i] = 0. Флаг choosing необходим для предотвращения ситуации, когда два процесса одновременно читают номер друг друга и получают одинаковые значения.
2. Ожидание: процесс проверяет все остальные процессы (j от 0 до N-1). Сначала он ждёт, пока процесс j закончит выбор номера (если choosing[j] == 1). Затем процесс ждёт, пока процесс j не станет «меньше» по правилу: номер j не равен 0 И (номер j меньше номера i ИЛИ (номера равны И j < i)). Это правило гарантирует, что процесс с меньшим номером (или с равным номером, но меньшим индексом) пройдёт в критическую секцию раньше.
3. Вход в критическую секцию: как только все процессы с меньшими номерами завершили работу, процесс входит в критическую секцию.
4. Выход: процесс устанавливает свой номер в 0, сигнализируя, что он покинул критическую секцию.

Свойства алгоритма

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

Алгоритм гарантирует, что в любой момент времени только один процесс может находиться в критической секции. Доказательство основано на том, что если два процесса A и B одновременно находятся в критической секции, то их номера должны быть равны, а индексы — различны, что противоречит правилу ожидания (один из них не смог бы пройти проверку).

Отсутствие взаимной блокировки (deadlock)

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

Отсутствие голодания (starvation)

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

Справедливость

Алгоритм является справедливым в том смысле, что процессы обслуживаются в порядке получения номеров (FIFO). Если процесс A получил номер раньше процесса B, то A войдёт в критическую секцию раньше B.

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

Зависимость от общей памяти

Алгоритм требует, чтобы все процессы имели доступ к общей памяти для чтения и записи массивов choosing и number. В распределённых системах без общей памяти он неприменим.

Производительность

Алгоритм имеет сложность O(N) для каждого входа в критическую секцию, где N — число процессов. Это связано с необходимостью проверять все остальные процессы. При большом количестве процессов (например, сотни) производительность существенно падает.

Атомарность операций

Алгоритм предполагает, что операции чтения и записи целых чисел и булевых значений являются атомарными. В современных многоядерных системах с кэшами и переупорядочиванием инструкций это может не выполняться. Для корректной работы требуются барьеры памяти (memory barriers) или атомарные инструкции.

Риск переполнения

Номера могут неограниченно расти, что в конечном итоге может привести к переполнению целочисленного типа. На практике это редкость, так как процессы обычно не входят в критическую секцию бесконечно часто, но теоретически проблема существует.

Применение

Алгоритм пекарни в основном используется в учебных целях и в теоретических исследованиях в области параллельного программирования. Он демонстрирует, что взаимное исключение можно реализовать без специальных аппаратных инструкций, используя только обычные операции чтения и записи. В реальных операционных системах (Windows, Linux, macOS) для синхронизации применяются более эффективные примитивы: мьютексы, семафоры, спин-блокировки, реализованные с помощью атомарных инструкций процессора (например, xchg, cmpxchg, lock add). Однако алгоритм пекарни лёг в основу некоторых программных реализаций мьютексов для встраиваемых систем с ограниченными аппаратными возможностями.

Вариации и модификации

Существует несколько модификаций алгоритма, направленных на устранение его недостатков:

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

Критика

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

Источники

• Lamport L. A New Solution of Dijkstra’s Concurrent Programming Problem // Communications of the ACM. — 1974. — Vol. 17, No. 8. — P. 453–455.
• Таненбаум Э., Бос Х. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2015. — 1120 с.
• Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. — 10th ed. — Wiley, 2018. — 1040 p.
• Herlihy M., Shavit N. The Art of Multiprocessor Programming. — 2nd ed. — Morgan Kaufmann, 2020. — 560 p.