Операционные системы распределенных вычислительных систем


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


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

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

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

 

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

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

 

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

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

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

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

 

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

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

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

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

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

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

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




Начало  Назад  Вперед



Книжный магазин