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

       

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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


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 выполняет  критическую  секцию, если  имеет  (или когда получит) маркер.



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

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)

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

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


Содержание раздела