Поиск по сайту:

Древовидный алгоритм Раймонда


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

Древовидный алгоритм Раймонда

Определение

Алгоритм следует методу, согласно которому внутри критической секции разрешены только потоки с токенами. Каждый узел сети может иметь максимум один родительский узел, отвечающий за генерацию токенов.

Узловой алгоритм

В древовидной структуре каждый узел может иметь только один родительский или корневой узел, к которому отправляются все запросы от других узлов. Родительский узел следует механизму «первым пришел — первым обслужен» (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) бит.

Недостаток алгоритма Раймонда

  • Голод  Алгоритм Рэймонда вызывает голодание. Истощение — это состояние, которое может возникнуть в параллельной системе, когда процессу или потоку постоянно отказывают в ресурсах, необходимых для выполнения. Это может произойти, когда алгоритм планирования последовательно отдает приоритет другим процессам или потокам над голодающим процессом, заставляя его бесконечно ждать ресурсов. Отсутствие питания может привести к снижению производительности системы и даже к тому, что система перестанет отвечать на запросы.

  • Жадная стратегия - Алгоритм Рэймонда приводит к голоданию. Истощение — это состояние, которое может возникнуть в параллельной системе, когда процессу или потоку постоянно отказывают в ресурсах, необходимых для выполнения. Это может произойти, когда алгоритм планирования последовательно отдает приоритет другим процессам или потокам над голодающим процессом, заставляя его бесконечно ждать ресурсов. Отсутствие питания может привести к снижению производительности системы и даже к тому, что система перестанет отвечать на запросы.

Заключение

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

Статьи по данной тематике: