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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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