Алгоритм Maekawas - Maekawas algorithm - Wikipedia

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

Алгоритм

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

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

Алгоритм

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

• Запрашивающий сайт ${\displaystyle P_{i}}$ отправляет сообщение ${\displaystyle {\text{request}}(ts,i)}$ ко всем сайтам в наборе кворума ${\displaystyle R_{i}}$.

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

• При получении ${\displaystyle {\text{request}}(ts,i)}$ сообщение, принимающий сайт ${\displaystyle P_{j}}$ буду:
  • Если сайт ${\displaystyle P_{j}}$ не имеет выдающихся ${\displaystyle {\text{grant}}}$ сообщение (то есть ${\displaystyle {\text{grant}}}$ сообщение, которое не было опубликовано), то сайт ${\displaystyle P_{j}}$ отправляет ${\displaystyle {\text{grant}}(j)}$ сообщение на сайт ${\displaystyle P_{i}}$.
  • Если сайт ${\displaystyle P_{j}}$ имеет выдающийся ${\displaystyle {\text{grant}}}$ сообщение с процессом с более высоким приоритетом, чем запрос, затем сайт ${\displaystyle P_{j}}$ отправляет ${\displaystyle {\text{failed}}(j)}$ сообщение на сайт ${\displaystyle P_{i}}$ и сайт ${\displaystyle P_{j}}$ ставит в очередь запрос с сайта ${\displaystyle P_{i}}$.
  • Если сайт ${\displaystyle P_{j}}$ имеет выдающийся ${\displaystyle {\text{grant}}}$ сообщение с процессом с более низким приоритетом, чем запрос, затем сайт ${\displaystyle P_{j}}$ отправляет ${\displaystyle {\text{inquire}}(j)}$ сообщение для процесса, которому в настоящее время предоставлен доступ к критическому разделу сайтом ${\displaystyle P_{j}}$. (То есть сайт с выдающимся ${\displaystyle {\text{grant}}}$ сообщение.)
• При получении ${\displaystyle {\text{inquire}}(j)}$ сообщение, сайт ${\displaystyle P_{k}}$ буду:
  • Отправить ${\displaystyle {\text{yield}}(k)}$ сообщение на сайт ${\displaystyle P_{j}}$ если и только если сайт ${\displaystyle P_{k}}$ получил ${\displaystyle {\text{failed}}}$ сообщение с другого сайта или если ${\displaystyle P_{k}}$ отправил доход на другой сайт, но не получил нового ${\displaystyle {\text{grant}}}$.
• При получении ${\displaystyle {\text{yield}}(k)}$ сообщение, сайт ${\displaystyle P_{j}}$ буду:
  • Отправить ${\displaystyle {\text{grant}}(j)}$ сообщение к запросу в верхней части собственной очереди запросов. Обратите внимание, что запросы вверху имеют наивысший приоритет.
  • Место ${\displaystyle P_{k}}$ в свою очередь запросов.
• При получении ${\displaystyle {\text{release}}(i)}$ сообщение, сайт ${\displaystyle P_{j}}$ буду:
  • Удалить ${\displaystyle P_{i}}$ из очереди запросов.
  • Отправить ${\displaystyle {\text{grant}}(j)}$ сообщение к запросу в верхней части очереди запросов.

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

• Сайт ${\displaystyle P_{i}}$ входит в критическую секцию при получении ${\displaystyle {\text{grant}}}$ сообщение со всех сайтов в ${\displaystyle R_{i}}$.
• При выходе из критической секции ${\displaystyle P_{i}}$ отправляет ${\displaystyle {\text{release}}(i)}$ сообщение для всех сайтов в ${\displaystyle R_{i}}$.

Набор кворума (${\displaystyle R_{x}}$):
Кворумный набор должен соответствовать следующим свойствам:

1. ${\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}$
2. ${\displaystyle \forall i\,[P_{i}\in R_{i}]}$
3. ${\displaystyle \forall i\,[|R_{i}|=K]}$
4. Сайт ${\displaystyle P_{i}}$ содержится точно в ${\displaystyle K}$ наборы запросов

Следовательно:

• ${\displaystyle |R_{i}|\geq {\sqrt {N-1}}}$

Спектакль

• Количество сетевых сообщений; ${\displaystyle 3{\sqrt {N}}}$ к ${\displaystyle 6{\sqrt {N}}}$
• Задержка синхронизации: 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.