Алгоритм булочной¶

Алгоритм булочной — это алгоритм параллельного взаимного исключения, предназначенный для организации доступа нескольких процессов или потоков к общему ресурсу без использования аппаратной поддержки атомарных операций, таких как Test-and-Set или Compare-and-Swap. Алгоритм гарантирует отсутствие взаимных блокировок (deadlock) и голодания (starvation), основываясь на принципе выдачи номеров, аналогичном работе очереди в магазине или булочной. Разработан Лесли Лампортом в 1974 году.

¶История

Алгоритм был предложен американским учёным в области информатики Лесли Лампортом в 1974 году в статье «A New Solution of Dijkstra’s Concurrent Programming Problem». Работа Лампорта была направлена на создание корректного решения задачи взаимного исключения для произвольного числа процессов, работающих с общей памятью, без использования специальных машинных команд. До этого существовали решения, основанные на аппаратных примитивах, но они требовали поддержки со стороны процессора. Алгоритм булочной стал одним из первых программных решений, доказанно обеспечивающих взаимное исключение и справедливость на основе только операций чтения и записи в разделяемую память.

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

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

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

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

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

¶Псевдокод

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

``` 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] != 0) { / ждём, пока процесс j выберет номер / } while ((number[j] != 0) && ((number[j] < number[i]) || ((number[j] == number[i]) && (j < i)))) { / ждём, пока процесс j не закончит критическую секцию / } }

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

number[i] = 0; ```

¶Пояснение этапов

1. Выбор номера: Процесс устанавливает choosing[i] = 1, чтобы другие процессы знали, что он выбирает номер. Затем он вычисляет максимальное значение среди всех number и увеличивает его на единицу. Это гарантирует, что новый номер будет уникальным и больше всех предыдущих. После выбора choosing[i] сбрасывается в 0.
2. Ожидание очереди: Процесс последовательно проверяет все другие процессы. Для каждого процесса j он сначала ждёт, пока тот завершит выбор номера (если choosing[j] не равно 0). Затем, если процесс j имеет ненулевой номер, процесс i ждёт, пока номер j не станет меньше номера i (или равным, но с меньшим идентификатором процесса). Таким образом, процесс с наименьшим номером первым входит в критическую секцию.
3. Выход: После завершения критической секции процесс сбрасывает свой номер в 0, сигнализируя, что он больше не претендует на ресурс.

¶Свойства

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

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

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

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

¶Отсутствие голодания

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

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

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

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

• Зависимость от общей памяти: Алгоритм предполагает, что все процессы имеют доступ к общей памяти, где хранятся массивы choosing и number. В распределённых системах без общей памяти алгоритм неприменим.
• Ненадёжность при сбоях: Если процесс аварийно завершается во время выбора номера или в критической секции, он может оставить choosing[i] или number[i] в некорректном состоянии, что приведёт к зависанию других процессов. Алгоритм не предусматривает механизмов восстановления после сбоев.
• Производительность: Алгоритм требует O(N) операций чтения и записи для каждого входа в критическую секцию, где N — количество процессов. При большом числе процессов накладные расходы становятся значительными. Кроме того, активное ожидание (busy waiting) в циклах while потребляет процессорное время.
• Переполнение номеров: Теоретически, при бесконечной работе системы номера могут достичь максимального значения и переполниться. На практике это решается использованием достаточно большого типа данных (например, 64-битного целого) или периодическим сбросом номеров, что усложняет реализацию.

¶Применение

Алгоритм булочной в основном используется в учебных целях для демонстрации принципов параллельного программирования и доказательства корректности алгоритмов взаимного исключения. В реальных операционных системах и библиотеках многопоточности (например, pthreads, Java concurrency, .NET) применяются более эффективные аппаратные примитивы (спин-блокировки, мьютексы, семафоры), которые используют атомарные инструкции процессора. Однако алгоритм Лампорта остаётся важным теоретическим результатом, показывающим, что взаимное исключение возможно без специальной аппаратной поддержки.

¶Вариации

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

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

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

• Алгоритм булочной является одним из первых примеров использования «конкурентного программирования» в качестве формальной модели.
• Лесли Лампорт получил премию Тьюринга в 2013 году, в том числе за вклад в разработку алгоритмов взаимного исключения и распределённых систем.
• Название алгоритма происходит от аналогии с очередью в булочной, где покупатели берут номерки и обслуживаются по порядку. Лампорт использовал этот образ, чтобы сделать алгоритм более интуитивно понятным.

¶Критика

Основная критика алгоритма связана с его практической неприменимостью в современных многопроцессорных системах из-за высоких накладных расходов и зависимости от последовательной согласованности памяти. На архитектурах со слабой моделью памяти (например, ARM, PowerPC) алгоритм может работать некорректно без дополнительных барьеров памяти (memory barriers). Кроме того, отсутствие устойчивости к сбоям делает его непригодным для отказоустойчивых систем.

¶Источники

• Lamport, L. «A New Solution of Dijkstra’s Concurrent Programming Problem». Communications of the ACM, 1974.
• Tanenbaum, A. S. «Современные операционные системы». 4-е издание, 2015.
• Herlihy, M., Shavit, N. «The Art of Multiprocessor Programming». 2nd edition, 2012.
• Дейкстра, Э. «Взаимное исключение в параллельных процессах». 1965.