Алгоритм древовидный маркерный (Raymond)

Алгоритм с круговым маркером

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

Взаимное исключение

Круговой алгоритм.

Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на "КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.

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

Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями).

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

Проблемы:

1. Если маркер потеряется, то его надо регенерировать. Обнаружить потерю тяжело (время прихода неизвестно).

2. Если какой-то процесс перестанет функционировать, то алгоритм не работает. Однако восстановление проще, чем в других случаях. Наличие квитанций позволит обнаружить такой процесс в момент передачи маркера (если поломка произошла вне критического интервала). Переставший функционировать процесс должен быть исключен из логического кольца, для этого придется каждому знать текущую конфигурацию кольца.

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

Вход в критическую секцию:

1 Если есть маркер, то процесс выполняет КС.

2 Если нет маркера, то процесс:

2.1. помещает свой запрос в очередь запросов

2.2. посылает сообщение "ЗАПРОС" в направлении владельца маркера и ждет сообщений.

Поведение процесса при приеме сообщений:

Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -"МАРКЕР" и "ЗАПРОС".

А) Пришло сообщение "МАРКЕР"

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

2. Поменять значение указателя в сторону маркера;

3. Исключить запрос из очереди;

4. Если в очереди остались запросы, то послать сообщение "ЗАПРОС" в сторону маркера.

Б) Пришло сообщение "ЗАПРОС".

Поместить запрос в очередь

Если нет маркера, то послать сообщение "ЗАПРОС" в сторону маркера, иначе (если есть маркер) - перейти на пункт 1.

Выход из критической секции.

Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту 1.

Дата добавления: 2015-04-25