Алгоритм Рикара – Агравалы

Алгоритм Рикара -Агравалы — это алгоритм взаимного исключения в распределенной системе . Этот алгоритм является расширением и оптимизацией алгоритма распределенного взаимного исключения Лампорта , устраняя необходимость $ack$ сообщения. ^{[ 1 ]} Его разработали учёные-компьютерщики Гленн Рикарт и Ашок Агравала .

Алгоритм

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

Сайт — это любое вычислительное устройство, на котором работает алгоритм Рикарта-Агравалы.
Запрашивающий сайт — это сайт, который запрашивает вход в критический раздел.
Принимающим сайтом является любой другой сайт, который получает запрос от запрашивающего сайта.

Алгоритм

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

Отправляет сообщение всем сайтам. Это сообщение включает в себя имя сайта и текущую временную метку системы в соответствии с ее логическими часами ( которые предполагается синхронизированными с другими сайтами ).

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

При получении сообщения-запроса немедленная отправка ответного сообщения с отметкой времени тогда и только тогда, когда:

принимающий процесс в данный момент не заинтересован в критическом разделе ИЛИ
процесс получения имеет более низкий приоритет ( обычно это означает наличие более поздней временной метки)

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

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

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

Производительность

Максимальное количество сетевых сообщений: $2*(N-1)$
Задержки синхронизации: задержка распространения одного сообщения.

Общие оптимизации

Однажды сайт $P_{i}$ получил $reply$ сообщение с сайта $P_{j}$ , сайт $P_{i}$ может войти в критическую секцию несколько раз без получения разрешения от $P_{j}$ при последующих попытках до момента, когда $P_{i}$ отправил $reply$ сообщение для $P_{j}$ . Это называется оптимизацией Рукайроля-Карвалью или алгоритмом Рукайроля-Карвальо.

Проблемы

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

См. также

Ссылки

^ Рикарт, Гленн; Агравала, Ашок К. (1 января 1981 г.). «Оптимальный алгоритм взаимного исключения в компьютерных сетях» . Коммуникации АКМ . 24 (1): 9–17. дои : 10.1145/358527.358537 . S2CID 1779615 .

Маэкава М., Олдехофт А., Олдехофт Р. (1987). Операционные системы: расширенная концепция. Benjamin/Cummings Publishing Company, Inc.

[1] Рикарт, Гленн; Агравала, Ашок К. (1 января 1981 г.). «Оптимальный алгоритм взаимного исключения в компьютерных сетях» . Коммуникации АКМ . 24 (1): 9–17. дои : 10.1145/358527.358537 . S2CID 1779615 .

[ 1 ]