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

1Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)Оглавление12Характеристики сетевых систем, определяющие принципы управления ................................................... 1Вопросы согласование времени в распределенных системах ......................................................................22.1 Физическое земное время.......................................................................................................................

22.2 Время в сетевых системах ...................................................................................................................... 32.3 Логическое время и порядок событий....................................................................................................32.4 Алгоритмы синхронизации часов в распределенных системах............................................................. 42.4.1Алгоритмы с использованием приемника UTC. ...........................................................................42.4.2Алгоритмы без использования приемника UTC ...........................................................................52.5 Алгоритмы крупномасштабной синхронизации ....................................................................................

53 Взаимное исключение в распределенной системе ....................................................................................... 63.1 Задача взаимного исключения(рис. 2.3).................................................................................................63.2 Взаимное исключение в сетевых системах ............................................................................................ 63.2.1Централизованный алгоритм.........................................................................................................73.2.2Маркерное кольцо ......................................................................................................................... 73.2.3Распределенный алгоритм.............................................................................................................73.2.4Достоинства и недостатки трех алгоритмов .................................................................................84 Распределенная взаимоблокировка ..............................................................................................................94.1 Взаимоблокировка, связанная с распределением ресурсов ...................................................................94.1.1Условия возникновения...............................................................................................................

104.1.2Фиктивная взаимоблокировка ..................................................................................................... 104.2 Предотвращение взаимоблокировок ....................................................................................................

114.3 Избежание взаимоблокировок.............................................................................................................. 134.4 Выявление взаимоблокировок.............................................................................................................. 141 Характеристики сетевых систем, определяющиепринципы управления1.Параллельность.осуществляютраспределенныеПрограммныевычисления,компоненты,должныкоторыевыполнятьсяодновременно на разных узлах сети.2.Независимыеотказы.Программныеиаппаратныекомпоненты, осуществляющие распределенные вычисления, и сеть,которая их соединяет, могут отказывать независимо друг от друга.3.Коммуникационныезадержки.Нараспространениерезультата некоторого события от одной точки вычислительной системыдо другой требуется определенное время.4.Отсутствие глобального времени.

Предполагается, что укаждого компонента системы имеются собственные часы, которые могутпоказывать разное время. Их аппаратное обеспечение не обязательно имеетв точности одинаковую частоту во всех компьютерах системы. Такоерасхождение зазывается сдвигом частоты (clock drift).5.Несогласованное состояние.

Параллельность, отказы икоммуникационные задержки являются причиной того, что состояниеСетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)распределенных вычислений в системе не согласовано.22 Вопросы согласование времени в распределенныхсистемах2.1 Физическое земное времяЗемное время установлено по соглашению.

Универсального времени несуществует.Распределенная система находится на Земле, и поэтому можноиспользовать некоторое согласованное понятие земного времени.Стандартное земное время основывается на вращении земли, измеряемомднями и годами, но его точное значение в настоящее время определяется спомощью особых цезиевых часов.Это время называют (хотя и неверно) всеобщим скоординированнымвременем (Universal Coordinated Time, UTC).Можно подключить к компьютеру устройство, получающее UTCсигналы либо со спутника, либо от радиостанции.Примерами спутниковых служб являютсяГЛОНАСС(глобальная навигационная спутниковая система)GPS (Global Positioning System)и GEOS (Geostationary Operational Environment Satellite).Точность значений времени, получаемых от этих служб, зависит отатмосферных условий и обычно составляет 10 мс для радиовещания и от О,1мс (GEOS) до 1 мс (GPS) для спутниковой связи.Невозможно оборудовать приемниками времени все компьютеры, но те изних, которые снабжены такими устройствами, могут служить серверами длядругих.Предполагается, что каждый компьютер содержит программируемыймодуль таймера на основе кварцевого осциллятора.

Он программируется навыдачу прерываний через определенные промежутки времени( обычно 10 мс).Точность этих устройств составляет около 1/106 мс (одна секунда за 11,6дня).Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)Она зависит от температуры, из-за чего возможен сдвиг частоты.32.2 Время в сетевых системахИнформация о времени в сетевых приложениях может использоваться вследующих целях.1. Распределение ресурсов.

Довольно типичны следующие правила:«если запросы ресурсов, осуществляемые двумя транзакциями, но для обеихтранзакций ресурсов недостаточно, побеждает транзакция с более раннейотметкой времени».2. Банковские системы. Программа начисления процентов работаетпосле полуночи. Она отмечает все транзакции, выполненные до полуночи,как относящиеся к предыдущему дню.3.

Средапрограммирования(враспределенныхпроектах).Перекомпиляции подлежат только те файлы, которые были отредактированыпосле последней компиляции проекта.4. Управление биржевыми операциями. Доступ к определеннойсекретной информации должен быть закрыт до начала транзакции покупкиили продажи акций, либо стоимость приобретенных акций необходимозафиксировать на момент начала транзакции.Следует заметить, что для процесса может иметь значение не тольковремя наступления некоторого события, но и порядок событий.Сучетомсдвигачастотыикоммуникационныхзадержеквраспределенной системе сложно правильно организовать или отследитьпорядок событий.2.3 Логическое время и порядок событийНа рис. 3.1 показаны три узла распределенной системы с временнойдиаграммой выполняющихся на них процессов.

События одного процессапоследовательны.4Сетевое ПО. Лекция 3(2014 г.)(Управление в сетевых системах)Сначала рассмотрим поведение данной системы безотносительнофизического времени. Процесс X взаимодействует с процессом Y (например,направив ему сообщение).Можно утверждать, что отправка сообщения процессом X происходит доего получения процессом Y.Затем процесс Y взаимодействует с процессом Z.Взаимодействие процессов требует упорядоченности событий в системе.У каждого процесса имеются локальные часы, показания которых могутрасходиться.Для записи времени событий в каждом отдельном процессе можноиспользовать локальные часыПредположим, что процесс X включает в отправляемое процессу Yсообщение отметку времени отправка (т, tx).Когда процесс Y получает это сообщение получение( т, tx) егособственные часы показывают ty (рис. 3.1).Если ty > tx, все в порядке,но если ty < tx, имеет место нарушение порядка событий.Процесс Y может установить на своих часах время tx +1 и все будет впорядке, хотя системное время будет все больше и больше расходиться среальным.Главное, что порядок событий в системе будет соблюдаться.2.4 Алгоритмы синхронизации часов в распределенныхсистемах2.4.1 Алгоритмы с использованием приемника UTC.Предположим, что некоторый компьютер содержит приемник UTC ифункционирует как сервер времени.Остальные компьютеры (клиенты) периодически опрашивают этотсервер(период зависит от требуемой точности), чтобы узнать текущее время, исервер отправляет им ответы.5Сетевое ПО.