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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ü массив с номерами последних удовлетворенных запросов.

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

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

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

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

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

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

1) Устанавливает в маркере равным .

2) Для каждого , для которого , он добавляет его идентификатор в маркерную очередь запросов.

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

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

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

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

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

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

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

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

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

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

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