Древовидный алгоритм Раймонда
Древовидный алгоритм Раймонда используется для защиты распределенных систем от возникновения разделов методом блокировки. Распределенные системы — это сети с большим количеством узлов, в которых осуществляется поток сообщений от одного узла к другому. Когда процесс заблокирован или находится в критической секции, внутрь можно разрешить только один поток или процесс, а другие потоки будут находиться в состоянии ожидания. Поскольку в распределенных системах задействовано много узлов, их можно уменьшить с помощью связующих деревьев.
Древовидный алгоритм Раймонда
Определение
Алгоритм следует методу, согласно которому внутри критической секции разрешены только потоки с токенами. Каждый узел сети может иметь максимум один родительский узел, отвечающий за генерацию токенов.
Узловой алгоритм
В древовидной структуре каждый узел может иметь только один родительский или корневой узел, к которому отправляются все запросы от других узлов. Родительский узел следует механизму «первым пришел — первым обслужен» (FIFO) для ответа на запросы от дочерних узлов при каждом получении токена.
Взаимное исключение
В этом алгоритме используется токен, чтобы гарантировать взаимное исключение. В этом подходе каждый сайт организован в виде направленного дерева, ребра которого направлены в сторону сайта, на котором хранится токен. Если у сайта есть токен, он может получить доступ к важной части. Это гарантирует, что только один сайт одновременно может получить доступ к важной области, в то время как всем остальным придется ждать освобождения токена.
Механизм алгоритма дерева Раймонда
Узел, попадающий в критическую секцию, считается имеющим токен. Давайте возьмем узел A в качестве родительского узла, а дочерними узлами будут B, C и D.
-
Узел попадает в критическую секцию на основании запроса.
Когда очередь родительского сайта равна нулю, дочерний узел перемещается в очередь «первым пришел — первым вышел», и на основе запроса назначается токен.
Когда родительский узел не пуст или очередь заполнена, он помещает запрошенный дочерний узел в очередь.
Когда любой дочерний узел с токеном получает другой токен, он перемещает токен на дочерний узел, который нуждается в токенах.
Свойства алгоритма на основе дерева Раймонда
Некоторые из основных свойств алгоритма:
Он обеспечивает свойство взаимного исключения с помощью токена. Если у сайта есть токен, он может получить доступ к важной части.
Все сайты расположены в виде направленного дерева, края которого обращены к сайту, на котором находится токен.
У каждого узла есть только один родительский узел, который получает запросы и пересылает их.
Каждый раз, когда узел встречает токен, он сохраняет очередь запросов FIFO.
Пример алгоритма
Алгоритм реализуется в распределенной системе с использованием следующей древовидной структуры:
В приведенном выше примере сайт A является основным узлом, на котором хранится токен. Сайты ниже узла A — это сайты B и C, которые считаются дочерними узлами. Эти сайты требуют, чтобы сайт A вошел в критическую секцию. Сайт C снова разделен на два подразделения как узлы D и E.
Как и вышеописанный шаг, узел C является основным узлом с двумя подузлами, такими как D и E. Эти узлы отправляют запрос родительскому узлу в зависимости от его требований. Поскольку запрос, созданный узлами B и C, уже присутствует, текущий запрос будет помещен в очередь.
На основании токена, полученного от первичного узла к вторичному, сайты попадают в критическую секцию.
Временная сложность алгоритма
Критическая секция распределенной системы обеспечивает временную сложность O(log n). Обязательно, чтобы каждый узел процесса содержал не менее O(log n) бит.
Недостаток алгоритма Раймонда
Голод − Алгоритм Рэймонда вызывает голодание. Истощение — это состояние, которое может возникнуть в параллельной системе, когда процессу или потоку постоянно отказывают в ресурсах, необходимых для выполнения. Это может произойти, когда алгоритм планирования последовательно отдает приоритет другим процессам или потокам над голодающим процессом, заставляя его бесконечно ждать ресурсов. Отсутствие питания может привести к снижению производительности системы и даже к тому, что система перестанет отвечать на запросы.
Жадная стратегия - Алгоритм Рэймонда приводит к голоданию. Истощение — это состояние, которое может возникнуть в параллельной системе, когда процессу или потоку постоянно отказывают в ресурсах, необходимых для выполнения. Это может произойти, когда алгоритм планирования последовательно отдает приоритет другим процессам или потокам над голодающим процессом, заставляя его бесконечно ждать ресурсов. Отсутствие питания может привести к снижению производительности системы и даже к тому, что система перестанет отвечать на запросы.
Заключение
Алгоритм используется на основе запросов, отправленных дочерними узлами родительскому узлу. За процедурой следует запрос родительского узла, выполнение узлов в соответствии с очередями после освобождения узла из критической секции, при этом узлы можно выбирать между пустыми или непустыми.