Алгоритм Maekawas - Википедия - Maekawas algorithm

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

Алгоритм

Терминология

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

Алгоритм

Запрашивающий сайт:

  • Запрашивающий сайт отправляет сообщение ко всем сайтам в наборе кворума .

Принимающий сайт:

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

Критический раздел:

  • Сайт входит в критическую секцию при получении сообщение со всех сайтов в .
  • При выходе из критической секции отправляет сообщение для всех сайтов в .

Набор кворума ():
Кворумный набор должен соответствовать следующим свойствам:

  1. Сайт содержится точно в наборы запросов
Следовательно:

Спектакль

  • Количество сетевых сообщений; к
  • Задержка синхронизации: 2 задержки распространения сообщения
  • Алгоритм может блокироваться без защиты.[1][2]

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

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

  1. ^ «Алгоритм взаимного исключения Маэкавы: подход к голосованию».
  2. ^ «Распределенное взаимное исключение» (PDF).
  • М. Маэкава, «Алгоритм A √N для взаимного исключения в децентрализованных системах», ACM

Транзакции в компьютерных системах, т. 3., нет. 2. С. 145–159, 1985.

  • Мамору Маэкава, Артур Э. Олдехофт, Родни Р. Олдехофт (1987). Операционные системы: расширенная концепция. Benjamin / Cummings Publishing Company, Inc.
  • Б. Сандерс (1987). Информационная структура распределенных алгоритмов взаимного исключения. ACM-транзакции в компьютерных системах, Vol. 3, № 2, с. 145–59.