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

Конструкции из металла демонтаж по заказу Новосибирске и пригороде.

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


 

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

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

 

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

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

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

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

 

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

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

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

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

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

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

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

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

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


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

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

 

Название алгоритма

TR

SD

MS/CS

(LL)

MS/CS

(HL)

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

2T

2T

3

3

Круговой маркерный

 

 

 

 

Древовидный маркерный

 

 

 

 

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

NT

T

2(N-1)

2(N-1)

Широковещательный  маркерный

 

 

 

 

 

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




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



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