Алгоритм Маекавы

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

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

Запрашиваемый сайт :

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

Место получения :

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

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

• Сайт переходит в критическую секцию при получении сообщения от всех сайтов в .${\displaystyle P_{i}}$${\displaystyle {\text{грант}}}$${\displaystyle R_{i}}$
• При выходе из критической секции отправляет сообщение всем сайтам в .${\displaystyle P_{i}}$${\displaystyle {\text{выпуск}}(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 К}$

Поэтому:

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

• Количество сетевых сообщений ;${\displaystyle 3{\sqrt {N}}}$${\displaystyle 6{\sqrt {N}}}$
• Задержка синхронизации: 2 задержки распространения сообщения
• Алгоритм может заблокироваться без установленной защиты. ^{[1] [2]}

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

• М. Маекава, «Алгоритм √N для взаимного исключения в децентрализованных системах», ACM

Труды по компьютерным системам, т. 3, № 2, стр. 145–159, 1985.

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