В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 5

Участие процесса P в выборах заканчивается.В любой момент процесс может получить сообщение «ВЫБОРЫ» от одного из коллег сменьшим номером. В этом случае он посылает ответ «OK», чтобы сообщить, что он жив иберет проведение выборов на себя, а затем начинает выборы (если к этому моменту он ужеих не вел).

Следовательно, все процессы прекратят выборы, кроме одного - новогокоординатора. Он извещает всех о своей победе и вступлении в должность сообщением«КООРДИНАТОР».Если процесс выключился из работы, а затем захотел восстановить свое участие, то онпроводит выборы (отсюда и название алгоритма).Круговой алгоритм.Алгоритм основан на использовании кольца (физического или логического). Каждыйпроцесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствиекоординатора, он посылает следующему за ним процессу сообщение «ВЫБОРЫ» со своимномером. Если следующий процесс не отвечает, то сообщение посылается процессу,следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающийпроцесс добавляет в список работающих свой номер и переправляет сообщение дальше покругу.

Когда процесс обнаружит в списке свой собственный номер (круг пройден), онменяет тип сообщения на «КООРДИНАТОР» и оно проходит по кругу, извещая всех о спискеработающих и координаторе (процессе с наибольшим номером в списке). Послепрохождения круга сообщение удаляется.4.3Взаимное исключение.Ниже приводятся 5 различных алгоритмов.Централизованный алгоритм.Все процессы запрашивают у координатора разрешение на вход в критическую секцию иждут этого разрешения. Координатор обслуживает запросы в порядке поступления.Получив разрешение процесс входит в критическую секцию. При выходе из нее он20сообщает об этом координатору. Количество сообщений на одно прохождениекритической секции - 3.Недостатки алгоритмаобычные недостаткикоординатора или его перегрузка сообщениями).централизованного алгоритма (крахДецентрализованный алгоритм на основе временных меток.Алгоритм носит имяпредложил Lamport.Ricart-Agrawalaиявляетсяулучшением алгоритма, которыйТребуется глобальное упорядочение всех событий в системе по времени.Вход в критическую секциюКогда процесс желает войти в критическую секцию, он посылает всем процессамсообщение-запрос, содержащее имя критической секции, номер процесса и текущее время.После посылки запроса процесс ждет, пока все дадут ему разрешение.

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

Побеждает тот, чья меткаменьше. Если чужой запрос победил, то процесс посылает сообщение «OK». Если учужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается.Выход из критической секцииПосле выхода из секции он посылает сообщение «OK» всем процессам, запросы от которыхон запомнил, а затем стирает все запомненные запросы.Количество сообщений на одно прохождение секции - 2(n-1), где n - число процессов.Кроме того, одна критическая точка заменилась на n точек (если какой-то процессперестанет функционировать, то отсутствие разрешения от него всех остановит).И, наконец, если в централизованном алгоритме есть опасность перегрузки координатора,то в этом алгоритме перегрузка любого процесса приведет к тем же последствиям.Некоторые улучшения алгоритма (например, ждать разрешения не от всех, а от большинства)требуют наличия неделимых широковещательных рассылок сообщений.Следующие три алгоритма – маркерные.

Их основное отличие от двух первых заключается втом, что процессы получают разрешение на вход в критическую секцию только при наличиимаркера. В каждом алгоритме используется свой метод получения маркера.Алгоритм с круговым маркером.Все процессы составляют логическое кольцо, когда каждый знает, кто следует за ним. Покольцу циркулирует маркер, дающий право на вход в критическую секцию. Получивмаркер (посредствомсообщения точка-точка) процесс либо входит в критическуюсекцию (если он ждал разрешения) либо переправляет маркер дальше. После выхода изкритической секции маркер переправляется дальше, повторный вход в секцию при том жемаркере не разрешается.21Алгоритм широковещательный маркерный (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) Если маркерная очередь запросов не пуста, то из нее удаляется первый элемент, амаркер посылается соответствующему процессу (запрос которого был первым вочереди).Алгоритм древовидный маркерный (Raymond).Все процессы представлены в виде сбалансированного двоичного дерева.

Каждый процессимеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель внаправлении владельца маркера.Вход в критическую секциюЕсли есть маркер, то процесс выполняет КС.Если нет маркера, то процесс:1) помещает свой запрос в очередь запросов2) посылает сообщение «ЗАПРОС» в направлении владельца маркера и ждет сообщений.Поведение процесса при приеме сообщенийПроцесс, не находящийся внутри КС должен реагировать на сообщения двух видов «МАРКЕР» и «ЗАПРОС».А) Пришло сообщение «МАРКЕР»М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможносебе);М2. Поменять значение указателя в сторону маркера;М3.

Исключить запрос из очереди;М4. Если в очереди остались запросы, то послать сообщение «ЗАПРОС» в сторону маркера.Б) Пришло сообщение «ЗАПРОС».1. Поместить запрос в очередь2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если естьмаркер) - перейти на пункт М1.22Выход из критической секцииЕсли очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пунктуМ1.Измерение производительности.Введем следующие три метрики.1) MS/CS - количество операций приема сообщений, требуемое для одного прохождениякритической секции.2) TR - время ответа, время от появления запроса до получения разрешения на вход.3) SD - синхронизационная задержка, время от выхода из критической секции одногопроцесса до входа в нее следующего процесса (другого!).При оценке производительности интересны две ситуации:низкая загрузка (LL), при которой вероятность запроса входа в занятую критическуюсекцию очень мала;высокая загрузка (HL), при которой всегда есть запросы на вход в занятую секцию.Для некоторых метрик интересно оценить наилучшее и наихудшее значение (которые частодостигаютсяпринизкойиливысокойзагрузки).Сравнение алгоритмов.При оценке времен исходим из коммуникационной среды, в которой время одного сообщения(Т) равно времени широковещательного сообщения.Название алгоритмаЦентрализованныйTRSDMS/CSMS/CS(LL)(HL)2T2T33NTT2(N-1)2(N-1)Круговой маркерныйДревовидный маркерныйДецентрализованный свременными меткамиШироковещательныймаркерныйВсе алгоритмы не устойчивы к крахам процессов (децентрализованные даже болеечувствительны к ним, чем централизованный).

Они в таком виде не годятся дляотказоустойчивых систем.4.4Координация процессов1) Сообщения точка-точка (если известно, кто потребитель).2) Если неизвестно, кто потребитель, то:сообщения широковещательные;сообщения в ответ на запрос.3) Если неизвестно, кто потребляет и кто производит, то:сообщения и запросы через координатора:широковещательный запрос.23Лекция 75 Распределенные файловые системыДве главные цели.Сетевая прозрачность.Самая важная цель - обеспечить те же самые возможности доступа к файлам, распределеннымпо сети ЭВМ, которые обеспечиваются в системах разделения времени на централизованныхЭВМ.Высокая доступность.Другая важная цель - обеспечение высокой доступности.

Ошибки систем или осуществлениеопераций копирования и сопровождения не должны приводить к недоступности файлов.Понятие файлового сервиса и файлового сервера.Файловый сервис - это то, что файловая система предоставляет своим клиентам, т.е.интерфейс с файловой системой.Файловый сервер - это процесс, который реализует файловый сервис.Пользователь не должен знать, сколько файловых серверов имеется и где они расположены.Так, как файловый сервер обычно является обычным пользовательским процессом, то всистеме могут быть различные файловые серверы, предоставляющие различный сервис(например, UNIX файл сервис и MS-DOS файл сервис).5.1Архитектура распределенных файловых системРаспределенная файловая система обычно имеет два существенно отличающихся компонента- непосредственно файловый сервер и сервер директорий.5.1.1Интерфейс файлового сервераДля любой файловой системы первый фундаментальный вопрос - что такое файл.

Вомногих системах, таких как UNIX и MS-DOS, файл - не интерпретируемая последовательностьбайтов. На многих централизованных ЭВМ (IBM/370) файл представляется какпоследовательность записей, которую можно специфицировать ее номером или содержимымнекоторого поля (ключом). Так, как большинство распределенных систем базируются наиспользовании среды UNIX и MS-DOS, то они используют первый вариант понятия файла.Файл может иметь атрибуты (информация о файле, не являющаяся его частью). Типичныеатрибуты - владелец, размер, дата создания и права доступа.Важный аспект файловой модели - могут ли файлы модифицироваться после создания.Обычно могут, но есть системы с неизменяемыми файлами.

Такие файлы освобождаютразработчиков от многих проблем при кэшировании и размножении.Защита обеспечивается теми же механизмами, что и в однопроцессорных ЭВМ мандатами и списками прав доступа. Мандат - своего рода билет, выданный пользователю длякаждого файла с указанием прав доступа.