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

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

¶История

Алгоритм был впервые описан Лесли Лампортом в статье «A New Solution of Dijkstra’s Concurrent Programming Problem» (1974). Лампорт работал в компании SRI International (США) и занимался проблемами синхронизации в распределённых системах. Его алгоритм стал первым решением задачи взаимного исключения, которое не требовало общей памяти и могло работать в системах с асинхронной передачей сообщений. Впоследствии алгоритм лёг в основу многих протоколов распределённой синхронизации, включая протоколы, используемые в отказоустойчивых кластерах и базах данных.

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

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

¶Основные шаги

1. Выбор номера: процесс генерирует номер, который больше всех номеров, видимых в данный момент. Для этого он считывает номера всех других процессов и выбирает максимальный, затем прибавляет 1.
2. Ожидание: процесс проверяет, есть ли процессы с меньшими номерами, которые ещё не завершили критическую секцию. Если такие есть, процесс ожидает.
3. Вход в критическую секцию: когда все процессы с меньшими номерами завершили работу, процесс входит в критическую секцию.
4. Выход: после завершения работы в критической секции процесс сбрасывает свой номер до 0 (или другого значения, означающего «неактивен»).

¶Пример

Пусть есть три процесса (P1, P2, P3). Процесс P1 получает номер 1, P2 — номер 2, P3 — номер 3. P1 входит в критическую секцию. P2 и P3 ждут. После выхода P1 номер 1 сбрасывается, и теперь наименьший номер — 2 у P2, поэтому P2 входит в секцию, затем P3. Если бы P3 получил номер 2, а P2 — номер 3, то порядок был бы обратным.

¶Реализация в распределённых системах

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

¶Требования к системе

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

¶Свойства

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

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

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

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

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

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

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

Алгоритм обеспечивает FIFO-подобную справедливость: процессы получают доступ в порядке возрастания номеров, что соответствует порядку их запросов.

¶Критика и ограничения

• Высокая стоимость: каждый процесс должен общаться со всеми остальными, что приводит к O(n²) сообщений при каждом входе в критическую секцию (где n — число процессов). Это делает алгоритм непригодным для систем с большим числом узлов.
• Зависимость от времени: номера генерируются на основе текущих значений, что может привести к коллизиям, если два процесса одновременно считают одно и то же значение. Лампорт решил эту проблему, добавив идентификаторы процессов в качестве младших разрядов номера.
• Неустойчивость к сбоям: в базовой версии алгоритм не работает, если процесс может выйти из строя (crash). Существуют модификации, устойчивые к сбоям, но они сложнее.

¶Применение

• Распределённые файловые системы: для синхронизации доступа к метаданным.
• Базы данных с репликацией: для обеспечения последовательности операций (например, в протоколах консенсуса, таких как Paxos, которые также разработаны Лесли Лампортом).
• Операционные системы: в некоторых реализациях мьютексов для многопроцессорных систем без общей памяти.
• Образовательные цели: алгоритм часто используется в курсах по распределённым системам для иллюстрации принципов синхронизации.

¶Варианты и модификации

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

¶Источники

• Lamport L. «A New Solution of Dijkstra’s Concurrent Programming Problem» // Communications of the ACM, 1974, vol. 17, no. 8, pp. 453–455.
• Lamport L. «The Part-Time Parliament» // ACM Transactions on Computer Systems, 1998, vol. 16, no. 2, pp. 133–169.
• Tanenbaum A. S., Van Steen M. «Distributed Systems: Principles and Paradigms» (2nd ed.), Prentice Hall, 2007.
• Coulouris G., Dollimore J., Kindberg T. «Distributed Systems: Concepts and Design» (5th ed.), Addison-Wesley, 2011.