3-4-MPI-Sync (В.А. Крюков, В.А. Бахтин - Распределенные системы), страница 3
Описание файла
Файл "3-4-MPI-Sync" внутри архива находится в папке "В.А. Крюков, В.А. Бахтин - Распределенные системы". Документ из архива "В.А. Крюков, В.А. Бахтин - Распределенные системы", который расположен в категории "". Всё это находится в предмете "распределённые системы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "3-4-MPI-Sync"
Текст 3 страницы из документа "3-4-MPI-Sync"
Алгоритм основан на использовании кольца (физического или логического). Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение «ВЫБОРЫ» со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на «КООРДИНАТОР» и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.
-
Взаимное исключение.
Ниже приводятся 5 различных алгоритмов.
Централизованный алгоритм.
Все процессы запрашивают у координатора разрешение на вход в критическую секцию и ждут этого разрешения. Координатор обслуживает запросы в порядке поступления. Получив разрешение процесс входит в критическую секцию. При выходе из нее он сообщает об этом координатору. Количество сообщений на одно прохождение критической секции - 3.
Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями).
Децентрализованный алгоритм на основе временных меток.
Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предложил Lamport.
Требуется глобальное упорядочение всех событий в системе по времени.
Вход в критическую секцию
Когда процесс желает войти в критическую секцию, он посылает всем процессам сообщение-запрос, содержащее имя критической секции, номер процесса и текущее время.
После посылки запроса процесс ждет, пока все дадут ему разрешение. После получения от всех разрешения, он входит в критическую секцию.
Поведение процесса при приеме запроса
Когда процесс получает сообщение-запрос, в зависимости от своего состояния по отношению к указанной критической секции он действует одним из следующих способов.
-
Если получатель не находится внутри критической секции и не запрашивал разрешение на вход в нее, то он посылает отправителю сообщение «OK».
-
Если получатель находится внутри критической секции, то он не отвечает, а запоминает запрос.
-
Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее, то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чья метка меньше. Если чужой запрос победил, то процесс посылает сообщение «OK». Если у чужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается.
Выход из критической секции
После выхода из секции он посылает сообщение «OK» всем процессам, запросы от которых он запомнил, а затем стирает все запомненные запросы.
Количество сообщений на одно прохождение секции - 2(n-1), где n - число процессов.
Кроме того, одна критическая точка заменилась на n точек (если какой-то процесс перестанет функционировать, то отсутствие разрешения от него всех остановит).
И, наконец, если в централизованном алгоритме есть опасность перегрузки координатора, то в этом алгоритме перегрузка любого процесса приведет к тем же последствиям.
Некоторые улучшения алгоритма (например, ждать разрешения не от всех, а от большинства) требуют наличия неделимых широковещательных рассылок сообщений.
Следующие три алгоритма – маркерные. Их основное отличие от двух первых заключается в том, что процессы получают разрешение на вход в критическую секцию только при наличии маркера. В каждом алгоритме используется свой метод получения маркера.
Алгоритм с круговым маркером.
Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним. По кольцу циркулирует маркер, дающий право на вход в критическую секцию. Получив маркер (посредством сообщения точка-точка) процесс либо входит в критическую секцию (если он ждал разрешения) либо переправляет маркер дальше. После выхода из критической секции маркер переправляется дальше, повторный вход в секцию при том же маркере не разрешается.
Алгоритм широковещательный маркерный (Suzuki-Kasami).
Маркер содержит:
-
очередь запросов;
-
массив LN[1...N] с номерами последних удовлетворенных запросов.
Вход в критическую секцию
-
Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то он увеличивает порядковый номер своих запросов RNk[k] и посылает широковещательно сообщение «ЗАПРОС», содержащее номер процесса (k) и номер запроса (Sn = RNk[k]).
-
Процесс Pk выполняет критическую секцию, если имеет (или когда получит) маркер.
Поведение процесса при приеме запроса
-
Когда процесс Pj получит сообщение-запрос от процесса Pk, он устанавливает RNj[k]=max(RNj[k],Sn). Если Pj имеет свободный маркер, то он его посылает Pk только в том случае, когда RNj[k]==LN[k]+1 (запрос не старый).
Выход из критической секции процесса Pk.
-
Устанавливает LN[k] в маркере равным RNk[k].
-
Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляет его идентификатор в маркерную очередь запросов (если там его еще нет).
-
Если маркерная очередь запросов не пуста, то из нее удаляется первый элемент, а маркер посылается соответствующему процессу (запрос которого был первым в очереди).
Алгоритм древовидный маркерный (Raymond).
Все процессы представлены в виде сбалансированного двоичного дерева. Каждый процесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель в направлении владельца маркера.
Вход в критическую секцию
Если есть маркер, то процесс выполняет КС.
Если нет маркера, то процесс:
-
помещает свой запрос в очередь запросов
-
посылает сообщение «ЗАПРОС» в направлении владельца маркера и ждет сообщений.
Поведение процесса при приеме сообщений
Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -«МАРКЕР» и «ЗАПРОС».
А) Пришло сообщение «МАРКЕР»
М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе);
М2. Поменять значение указателя в сторону маркера;
М3. Исключить запрос из очереди;
М4. Если в очереди остались запросы, то послать сообщение «ЗАПРОС» в сторону маркера.
Б) Пришло сообщение «ЗАПРОС».
-
Поместить запрос в очередь
-
Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.
Выход из критической секции
Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту М1.
Измерение производительности.
Введем следующие три метрики.
-
MS/CS - количество операций приема сообщений, требуемое для одного прохождения критической секции.
-
TR - время ответа, время от появления запроса до получения разрешения на вход.
-
SD - синхронизационная задержка, время от выхода из критической секции одного процесса до входа в нее следующего процесса (другого!).
При оценке производительности интересны две ситуации:
-
низкая загрузка (LL), при которой вероятность запроса входа в занятую критическую секцию очень мала;
-
высокая загрузка (HL), при которой всегда есть запросы на вход в занятую секцию.
Для некоторых метрик интересно оценить наилучшее и наихудшее значение (которые часто достигаются при низкой или высокой загрузке).
Сравнение алгоритмов.
При оценке времен исходим из коммуникационной среды, в которой время одного сообщения (Т) равно времени широковещательного сообщения.
Название алгоритма | TR | SD | MS/CS (LL) | MS/CS (HL) |
Централизованный | 2T | 2T | 3 | 3 |
Круговой маркерный | ||||
Древовидный маркерный | ||||
Децентрализованный с временными метками | NT | T | 2(N-1) | 2(N-1) |
Широковещательный маркерный |
Все алгоритмы не устойчивы к крахам процессов (децентрализованные даже более чувствительны к ним, чем централизованный). Они в таком виде не годятся для отказоустойчивых систем.
4.4 Координация процессов
-
Сообщения точка-точка (если известно, кто потребитель).
-
Если неизвестно, кто потребитель, то:
-
сообщения широковещательные;
-
сообщения в ответ на запрос.
-
Если неизвестно, кто потребляет и кто производит, то:
-
сообщения и запросы через координатора:
-
широковещательный запрос.