Алгоритм Token Ring

Совершенно другой подход к достижению взаимного исключения в распределенных системах иллюстрируется рисунком 3.7. Все процессы системы образуют логическое кольцо, т.е. каждый процесс знает номер своей позиции в кольце, а также номер ближайшего к нему следующего процесса. Когда кольцо инициализируется, процессу 0 передается так называемый токен. Токен циркулирует по кольцу. Он переходит от процесса n к процессу n+1 путем передачи сообщения по типу "точка-точка". Когда процесс получает токен от своего соседа, он анализирует, не требуется ли ему самому войти в критическую секцию. Если да, то процесс входит в критическую секцию. После того, как процесс выйдет из критической секции, он передает токен дальше по кольцу. Если же процесс, принявший токен от своего соседа, не заинтересован во вхождении в критическую секцию, то он сразу отправляет токен в кольцо. Следовательно, если ни один из процессов не желает входить в критическую секцию, то в этом случае токен просто циркулирует по кольцу с высокой скоростью.

Сравним эти три алгоритма взаимного исключения. Централизованный алгоритм является наиболее простым и наиболее эффективным. При его использовании требуется только три сообщения для того, чтобы процесс вошел и покинул критическую секцию: запрос и сообщение-разрешение для входа и сообщение об освобождении ресурса при выходе. При использовании распределенного алгоритма для одного использования критической секции требуется послать (n-1) сообщений-запросов (где n - число процессов) - по одному на каждый процесс и получить (n-1) сообщений-разрешений, то есть всего необходимо 2(n-1) сообщений. В алгоритме Token Ring число сообщений переменно: от 1 в случае, если каждый процесс входил в критическую секцию, до бесконечно большого числа, при циркуляции токена по кольцу, в котором ни один процесс не входил в критическую секцию.

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

Рис. 3.7. Средства взаимного исключения в распределенных системах
а - неупорядоченная группа процессов в сети;
б - логическое кольцо, образованное программным обеспечением

 

 

1. Взаимоблокировки в распределенных системах и их обнаружение и предотвращение.

Распределенные взаимоблокировки возникают тогда, когда размещенные на разных узлах сети процессы ожидают событий, которые не могут произойти. Бывают 3-х видов:

1. Взаимоблокировка ресурсов

2. Взаимоблокировка связи

3. Фантомные взаимоблокировки. Возникают при использовании стороннего узла для выявления взаимоблокировок из-за задержек на линиях связи

 

В качестве средства предотвращающего взаимоблокировки применяется слияние одного из процессов в зависимости от выбранной стратегии.

Для обработки взаимоблокировок используются:

1) Централизованное обнаружение. Один из узлов сети осуществляет мониторинг. Он оповещается обо всех случаях освобождения и занятиях ресурсов и проверяет систему на наличие замкнутых циклов.

2) Иерархическое обнаружение блокировок. Узлы сист. Иерархически организуются. Каждый узел собирает информацию о всех своих потомках

3) Распределенное обнаружение. Наличие взаимоблокировок определяет каждый процесс в системах, опрашивая все остальные узлы

 

1. Неделимые транзакции. Процессы и нити (потоки) в распределенных системах.