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

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

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

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

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

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

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

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

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

Проблемы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Децентрализованный алгоритм на основе временных меток.

Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предлжил Lamport.

Требуется глобальное упорядочение всех событий в системе по времени.

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

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

После посылки запроса процесс ждет, пока все дадут ему разрешение. После получения от всех разрешения, он входит в критическую секцию.

Поведение процесса при приеме запроса

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

1. Если получатель не находится внутри критической секции и не запрашивал разрешение на вход в нее, то он посылает отправителю сообщение «OK».

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

1. Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее, то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чья метка меньше. Если чужой запрос победил, то процесс посылает сообщение «OK». Если у чужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается.

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

После выхода из секции он посылает сообщение «OK» всем процессам, запросы от которых он запомнил, а затем стирает все запомненные запросы.

Количество сообщений на одно прохождение секции - 2(n-1), где n - число процессов.

Кроме того, одна критическая точка заменилась на n точек (если какой-то процесс перестанет функционировать, то отсутствие разрешения от него всех остановит).

И, наконец, если в централизованном алгоритме есть опасность перегрузки координатора, то в этом алгоритме перегрузка любого процесса приведет к тем же последствиям.

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

Алгоритм широковещательный маркерный (Suzuki-Kasami).

Маркер содержит:

• очередь запросов;

• массив LN[1...N] с номерами последних удовлетворенных запросов.

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

1. Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то он увеличивает порядковый номер своих запросов RNk[k] и посылает широковещательно сообщение «ЗАПРОС», содержащее номер процесса (k) и номер запроса (Sn = RNk[k]).

1. Процесс Pk выполняет критическую секцию, если имеет (или когда получит) маркер.

Поведение процесса при приеме запроса

1. Когда процесс Pj получит сообщение-запрос от процесса Pk, он устанавливает RNj[k]=max(RNj[k],Sn). Если Pj имеет свободный маркер, то он его посылает Pk только в том случае, когда RNj[k]==LN[k]+1 (запрос не старый).

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

1. Устанавливает LN[k] в маркере равным RNk[k].

1. Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляет его идентификатор в маркерную очередь запросов.

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

Измерение производительности.

Введем следующие три метрики.

1. MS/CS - количество операций приема сообщений, требуемое для одного прохождения критической секции.

1. TR - время ответа, время от появления запроса до получения разрешения на вход.

1. SD - синхронизационная задержка, время от выхода из критической секции одного процесса до входа в нее следующего процесса (другого!).

При оценке производительности интересны две ситуации:

• низкая загрузка (LL), при которой вероятность запроса входа в занятую критическую секцию очень мала;

• высокая загрузка (HL), при которой всегда есть запросы на вход в занятую секцию.

Для некоторых метрик интересно оценить наилучшее и наихудшее значение (которые часто достигаются при низкой или высокой загрузки).

Сравнение алгоритмов.

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

Название алгоритма	TR	SD	MS/CS (LL)	MS/CS (HL)
Централизованный	2T	2T	3	3
Круговой маркерный
Древовидный маркерный
Децентрализованный с временными метками	NT	T	2(N-1)	2(N-1)
Широковещательный маркерный

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

4.4 Координация процессов

1. Сообщения точка-точка (если известно, кто потребитель).

1. Если неизвестно, кто потребитель, то:

1. сообщения широковещательные;

1. сообщения в ответ на запрос.

1. Если неизвестно, кто потребляет и кто производит, то:

1. сообщения и запросы через координатора:

1. широковещательный запрос.