Операционные системы распределенных вычислительных систем
Алгоритм древовидный маркерный (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) |
|
Широковещательный маркерный |
