Взаимное исключение в распределенной системе. Централизованный алгоритм, алгоритм Лампорта, алгоритм Рикарта и Агравалы

By Денис Чащин  

Описание

При разработке распределенной системы часто надо организовать доступ к какому-нибудь ресурсу, так, чтобы в один момент времени ресурсом пользовалось ограниченное количество процессов. Рассмотрим некоторые алгоритмы, реализующие разделение доступа к этому ресурсу (его так же называют «Критическая секция«)

Централизованный алгоритм

  1. Центральные управляющий узел( координатор) ведет очередь запросов на вход
  2. Процесс, желающий войти в критическую секцию посылает ему сообщение-запрос и ждет пока не получит сообщение-разрешение, что может войти
  3. После выхода из критической секции, сообщяет координатору что критическая секция свободна

При использовании такого алгоритма приходится посылать 3N-3 сообщений, где N — количество входов в критическую секцию.

Алгоритм Лампорта

Работает только в случае FIFO (первый вошел-первый вышел) очереди передачи сообщений.

Каждый поток поддерживает очередь запросов на вход. Приоритет — временная метка (часы + номер потока). Если поток хочет войти в критическую секцию, то делает следующие действия:

  1. Добавляет свой запрос в очередь
  2. Посылает всем потокам запрос
  3. Ждет ответ
  4. Получив все ответы, ждет когда станет первым в своей очереди
  5. Входит
  6. Выйдя из критической секции, всем посылает сообщение, что вышел(release).

Находясь вне критической секции:

  1. При получении запроса от другого потока, добавляем его в свою очередь и посылаем ответ
  2. При получении  release, запрос удаляется из очереди.

Этот алгоритм требует так же 3N-3 сообщений

 

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

Итак, следующий алгоритм.

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

  1. Процесс P_i хочет войти в критическую секцию — шлет запрос со своим временем
  2. P_k получает запрос от P_i и
    • Если он не посылал запрос, то отсылает отклик
    • Если посылал запрос, то сравнивает временные метки, и если его метка позже, то отвечает ( при равенстве сравнивает номера процессов)
    • Иначе P_k ждет
  3. Когда все отклики получены, то процесс может войти в критическую секцию
  4. При выходе отсылаем задерженные отклики.

Этот алгоритм требует всего 2N-2 сообщений, правда отказ любого узла может привести к зависанию всей системы.
Предыдущая статья из серии «О параллельном программировании»


Post a Comment

Your email is never shared. Required fields are marked *

*
*