Алгоритм распределенного взаимного исключения Лэмпорта - Википедия - Lamports distributed mutual exclusion algorithm

Смотрите также: Алгоритм пекарни Лэмпорта

Распределенный алгоритм взаимного исключения Лэмпорта алгоритм на основе конкуренции для взаимное исключение на распределенная система.

Алгоритм

Узловые свойства

  1. Каждый процесс поддерживает очередь ожидающих запросов на вход в критический раздел по порядку. Очереди упорядочены по виртуальным отметкам времени, полученным из Отметки времени Лэмпорта.[1]

Алгоритм

Процесс запроса

  1. Отправка запроса в собственную очередь (упорядоченная по отметкам времени)
  2. Отправка запроса каждому узлу.
  3. Жду ответов от всех остальных узлов.
  4. Если собственный запрос находится во главе очереди и все ответы получены, войдите в критический раздел.
  5. После выхода из критического раздела удалите его запрос из очереди и отправьте сообщение о выпуске каждому процессу.

Другие процессы

  1. После получения запроса отправка запроса в собственную очередь запросов (упорядоченная по меткам времени) и ответ с меткой времени.
  2. После получения сообщения о выпуске удалите соответствующий запрос из собственной очереди запросов.

Сложность сообщения

Этот алгоритм создает 3 (N - 1) сообщений на запрос, или (N - 1) сообщения и 2 трансляции. 3 (N - 1) сообщения на запрос включают:

  • (N - 1) общее количество запросов
  • (N - 1) общее количество ответов
  • (N - 1) общее количество выпусков

Недостатки

У этого алгоритма есть несколько недостатков. Они есть:

  • Это очень ненадежно, поскольку отказ любого из процессов остановит прогресс.
  • Он имеет высокую сложность сообщения 3 (N - 1) сообщений на вход / выход в критическую секцию.

Смотрите также

Рекомендации

  1. ^ Кшемкаляни А. и Сингхал М. Глава 9: Распределенные алгоритмы взаимного исключения. Распределенные вычисления: принципы, алгоритмы и системы (страница 10 из 93). Издательство Кембриджского университета.