Сетевое ПО Лекция 3 (Электронные лекции), страница 2

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

Их нельзя перевести назад, чтобы не нарушитьпоследовательность событий, но можно замедлить.У приведенного алгоритма есть одно слабое место — единственныйсервер времени.Для надежности можно включить в систему несколько серверов,опрашивать их все и использовать первый ответ.2.4.2 Алгоритмы без использования приемника UTCВ случае, когда ни один из компьютеров не имеет приемника, участникисобытий могут пользоваться некоторым средним значением времени, сверяяпоказания своих часов.Один из компьютеров может исполнять роль координатора, спрашиваявремя у остальных, вычисляя среднее значение и рассылая его по сети, чтобы всекомпьютеры подстроили свои часы.Время на этом координирующем компьютере может периодическиустанавливаться оператором вручную.2.5 Алгоритмы крупномасштабной синхронизацииОписанные выше алгоритмы основаны на взаимодействии всех участниковс сервером, и поэтому они неприменимы для систем с большим количествомучастников.Одним из самых наглядных примеров крупномасштабной системыявляется Интернет, где синхронизация времени с точностью до нескольких6Сетевое ПО.

Лекция 3(2014 г.)(Управление в сетевых системах)десятков миллисекунд достигается при помощи протокола NTP (Network TimeProtocol — сетевой протокол времени).Как он действует, показано на рис. 3.2.Классическим способом управления большим числом объектов являетсясоздание их иерархии. Для протокола NTP выбрана трехуровневая иерархия. Наверхнем уровне располагается некоторое количество первичных серверов сприемникам UTC.Каждый из них отвечает за передачу полученного времени вниз кподдеревьям.Навторомуровнерасположенагруппасерверов,взаимодействующих с первичными серверами UTC.

Они передают времясвязанным с ним серверам третьего уровня.3 Взаимное исключение в распределенной системе3.1 Задача взаимного исключенияНеобходимо согласовать работу параллельных процессов прииспользовании некоторого критического ресурса таким образом, чтобыудовлетворить следующим требованиям:1.Одновременно внутри критического интервала должнонаходиться не более одного процесса;2.Освобождениекритическогоресурсаивыходизкритического интервала должны быть произведены процессом,использующим критический ресурс, за конечное время.Реализация задачи взаимного исключения в централизованныхсистемах(рис.

3.4 а,б)3.2 Взаимное исключение в сетевых системахРассмотрим систему, в которой п процессов выполняются на ппроцессорах без общей памяти.Необходиморазработатьалгоритмреализациикритическихинтервалов для каждого из процессов.В любом таком алгоритме должны учитыватьсявозможность независимых отказов компонентовраспределенной системы,отсутствие единого времени7Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)Триподходыалгоритма,кзадержки при взаимодействии компонентов.демонстрирующихреализациивзаимногонаиболееисключенияраспространенныедлянесколькихраспределенных процессов.3.2.1 Централизованный алгоритмДанный способ синхронизации сходен с методом управления доступомк централизованному ресурсу посредством координирующего сервера.Его идея заключается в том, что один из процессов выбирается на ролькоординатораПеред входом в критический интервал каждый процесс направляеткоординатору запрос, тот проверяет, находится ли какой-нибудь процесс вкритическом интервале, если да, то запрос ставится в очередь к ресурсу.Когда процесс выходит из своего критического интервала, онотправляет координатору соответствующее сообщение получив которое,координатор выбирает из очереди следующий процесс (или возможно,другой процесс в соответствии с определенной в системе политикой) иотправляет ему сообщение с разрешением входа в критический интервал.По выходе из него тот снова уведомляет координатора и т.

д.3.2.2 Маркерное кольцоПроцессы организованы в виртуальное кольцо, по которому онипередают друг другу маркер — сообщение, служащее разрешением длявхода в критический интервал. Получив его, процесс либо входит вкритический интервал, если ему это нужно, либо передает его дальше.3.2.3 Распределенный алгоритмЕго задача заключается в реализации принципа «первым вошел —первым обслужен». Когда процесс желает войти в критический интервал, онотправляет всем процессам, включая и самого себя, сообщение с запросом.Сообщения упорядочиваются по отметкам времени, а если две отметкиравны, то по идентификаторам процессов.8Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)Получив сообщение с запросом, процесс может ответить немедленноили отложить отправку ответа.

Если процесс:находится в критическом интервале, он откладываетотправку ответа;не собирается входить в критический интервал, ответотправляется немедленно;намерен войти в критический интервал, но еще этого несделал, он сравнивает отметки времени своего собственного ипоступившего запросов, и если запрос другого процесса был отправленраньше, ответ будет отправлен немедленно, в противном случаеотправка ответа откладывается.Процесс, получивший ответы от всех остальных процессов, можетвойти в критический интервал. После выхода из нее он отвечает на запросы,отправка ответов на которые была отложена.3.2.4 Достоинства и недостатки трех алгоритмовЦентрализованный алгоритм прост и реализует принцип «первымвошел — первым обслужен».

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

Эту проблему можно решить путем подтверждениязапросов.Алгоритм на основе маркерного кольца достаточно эффективен,однако имеет один недостаток: маркер продолжает циркулировать по кольцу,когда ни одному процессу не требуется войти в критический интервал.Кроме того, в этом алгоритме не учитывается порядок запросов на вход вкритический интервал, а также возможна потеря маркера, которую труднообнаружить. Для выявления вышедших из строя компонентов необходимоиспользование подтверждающих сообщений.9Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)В распределенном алгоритме точками отказа и узкими местамистановятся не один, а все узлы.

К тому же, хотя в нем учитывается порядокзапросов, при его использовании передается слишком много сообщений. Каки в предыдущем случае для выявления вышедших из строя компонентовнеобходимы подтверждающие сообщения.4 Распределенная взаимоблокировкаВзаимоблокировка-постоянноеблокированиенекоторогомножества процессов, которые либо конкурируют, пытаясь получитьдоступ к системным ресурсам, либо обмениваются информацией друг сдругом.Это определение справедливо как для централизованной, так и дляраспределенной системы.Проблема взаимоблокировки, как и проблема взаимоисключения, враспределенной системе является более сложной, чем в системе с общейпамятью.Причинами этого усложнения является то, что ни один узел необладает точными сведениями о текущем состоянии всей системы, а такжето, что передача сообщения от одного процесса другому сопровождаетсянепредсказуемой по длительности временной задержкой.Рассматриваются два вида распределенных взаимоблокировок: возникающие в связи с распределением ресурсов возникающие при обмене сообщениями.4.1 Взаимоблокировка, связанная с распределением ресурсовВзаимоблокировка, связанная с ресурсами, возникает тогда, когдапроцесс пытается получить доступ к ресурсам, например объектам данных избазы данных или ресурсам ввода-вывода, которые находятся на сервере.При этом образуется группа процессов, каждый из которых запрашиваетресурс, которым обладает другой процесс из этой группы.10Сетевое ПО.

Лекция 3(2014 г.)(Управление в сетевых системах)4.1.1 Условия возникновенияВзаимоблокировка в распределении ресурсов возникает только присоблюдении всех перечисленных условий:• Взаимоисключение. Одновременно использовать ресурс можеттолько один процесс.• Удержание и ожидание. Процесс может удерживать выделенныересурсы во время ожидания других ресурсов.• Отсутствиеперераспределения.Ресурснеможетбытьпринудительно отобран у удерживающего его процесса.• Циклическое ожидание(Круговое распределение ресурса).Существует замкнутая цепь процессов, каждый из которых удерживаеткак минимум один ресурс, необходимый процессу, следующему в цепипосле него(рис.

3.5).Цель алгоритма обработки взаимоблокировок - либо предотвратитьобразование циклического ожидания, либо обнаружить, что оно возникло илиможет возникнуть.В распределенной системе ресурсы распределены по разным узлам.Доступ к ресурсам регулируется управляющими процессами на этих узлах.Любой отдельный управляющий процесс не обладает полными исвежими сведениями о глобальном состоянии системы и должен приниматьрешение, основываясь на локальной информации.Таким образом, в распределенной системе требуется новыйалгоритм защиты от взаимоблокировок.4.1.2 Фиктивная взаимоблокировкаОдной из сложностей, возникающих при управлении распределеннымивзаимоблокировками,являетсяявлениефиктивной(phantom deadlock).Пример такой взаимоблокировки (рис. 3.6).взаимоблокировки11Сетевое ПО.

Лекция 3(2014 г.)(Управление в сетевых системах)Запись P1→P2→Р3 означает, что процесс P1 приостановлен в ожиданииресурса, которым владеет процесс Р2, а процесс Р2 приостановлен в ожиданииресурса, которым владеет процесс Р3.Пусть вначале процесс Р3 обладает ресурсом R3, a процесс P1 —ресурсом R1.Предположим,чтопроцессР3сначалагенерируетсообщение,освобождающее ресурс R3, а затем — сообщение с запросом ресурса R1.Еслипроцессвыявлениясообщение(освобождениересурса),цикловасначалазатемполучитвторое(запроспервоересурса),возникнет цепочка, изображенная на рис.

3.6 аВ противном случае будет зарегистрирована взаимоблокировка (рис.3.6 б).На самом деле никакой взаимоблокировки не возникает; будетзарегистрирована ложная взаимоблокировка, вызванная отсутствиеминформации о глобальном состоянии системы.4.2 Предотвращение взаимоблокировокВ распределенной среде можно использовать два метода предотвращениявзаимоблокировок1.Возникновения циклического ожидания можно избежать,линейно упорядочив типы ресурсов. Если процессу выделены ресурсы типаR, то он может последовательно запрашивать только те ресурсы, номер типакоторых следует после R.Основной недостаток этого метода состоит в том, что не всегда ресурсыможно запрашивать в том порядке, в котором они используются, поэтомуресурсы могут удерживаться процессом дольше, чем необходимо.2.Условий удержания и ожидания можно избежать, потребовав,чтобы процесс запрашивал все необходимые ресурсы одновременно, иблокируя процесс до тех пор, пока такой запрос не сможет быть полностьювыполнен в один момент времени.12Сетевое ПО.