Алгоритм Раймондса - Википедия - Raymonds algorithm

Алгоритм Раймонда алгоритм на основе блокировки для взаимное исключение на распределенная система. Он навязывает логическую структуру ( K-арное дерево ) на распределенных ресурсах. Как определено, каждый узел имеет только одного родителя, которому выполняются все запросы на получение токена.

Алгоритм

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

  1. У каждого узла есть только один родитель, которому пересылаются полученные запросы.
  2. Каждый узел поддерживает ФИФО очередь запросов каждый раз, когда он видит токен;
  3. Если какой-либо узел пересылает привилегию другому узлу и имеет непустую очередь, он пересылает сообщение запроса по

Алгоритм

  1. Если узел я (не владеющий токеном) желает получить токен, чтобы войти в его критическая секция, он отправляет запрос своему родительскому узлу j.
    • Если узел j FIFO пуст, узел j сдвиги я в свою очередь FIFO; j затем отправляет запрос своему родителю, k, что он желает жетон
    • Если узел j Очередь FIFO нет пустой, он просто сдвигается я в очередь
  2. Когда узел k имеет токен и получает запрос от j он отправляет токен j и устанавливает j как его родитель
  3. Когда узел j получает токен от k, он пересылает токен в я и я удаляется из очереди j
    • Если очередь j не пуст после пересылки токена на я, j должен направить запрос я чтобы вернуть токен

Примечание: Если j хочет запросить токен, и его очередь нет пусто, затем он помещается в свою очередь. Узел j будет использовать токен для входа в свой критический раздел если он находится в начале очереди при получении токена.

Сложность

Алгоритм Раймонда гарантированно будет O (журнал n) на запись критического раздела, если процессоры организованы в K-арый дерево. Кроме того, каждый процессор должен хранить не более O (журнал n) бит, потому что он должен отслеживать О (1) соседи.[1]

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

  1. ^ Р. Чоу, Т. Джонсон; Распределенные операционные системы и алгоритмы; Аддисон-Уэсли, 1997.

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