Алгоритм Рэймонда

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

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

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

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

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

• Алгоритм Рикарта-Агравалы
• Алгоритм пекарни Лампорта
• Распределенный алгоритм взаимного исключения Лэмпорта
• Алгоритм Маекавы
• Алгоритм Сузуки-Касами
• Алгоритм Наими-Трехеля