Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 74
Текст из файла (страница 74)
Один из наиболее часто используемых алгоритмов в Интернете — этопротокол сетевого времени {Network Time Protocol, NTP), описанный в [293]. NTPизвестен тем, что позволяет обеспечить точность (глобальную) 1-50 мс. Такаяточность достигается путем использования усовершенствованных алгоритмовсинхронизации часов, дальнейшие их усовершенствования описаны в [294].Множественные внешние источники точного времениДля систем, которым необходима особо точная синхронизация по UTC, можнопредложить использование нескольких приемников WWV, GEOS или других источников иТС. Однако из-за врожденной неточности самих источников времении флуктуации на пути сигнала лучшее, что могут сделать операционные системы, — это установить интервал, в который попадает UTC. В основном различныеисточники точного времени будут порождать различные диапазоны, и машины,к которым они присоединены, должны прийти к какому-то общему соглашению.Чтобы достичь этого соглашения, каждый процессор с источником UTC может периодически делать широковещательную рассылку своих данных, например, точно в начале каждой минуты по UTC.
Ни один процессор не получитпакеты значений времени мгновенно. Что еще более печально, задержка междупосылкой и приемом будет зависеть от длины кабеля и числа маршрутизаторов,через которые должен будет пройти пакет. Эти значения различны для каждойпары (источник UTC, процессор). Будут также играть свою роль и другие факторы, такие как задержка по причине коллизий, когда несколько машин попытаются послать что-то по Ethernet в один и тот же момент.
Более того, если процессорзанят обработкой предыдущего пакета, он, возможно, не сумеет просмотреть пакет значений времени за оговоренное число миллисекунд, что внесет дополнительную неясность.5.1.3. Использование синхронизированных часовЗа прошедшие несколько лет стали легкодоступными необходимая аппаратураи программное обеспечение, предназначенные для синхронизации часов в глобальном масштабе (то есть во всем Интернете). Благодаря этим новым технологиямможно синхронизировать миллионы часов с точностью до нескольких миллисекунд по иТС.
Стали появляться новые алгоритмы, использующие эти синхронизированные часы. Один из примеров касается того, как добиться доставки серверу не более одного сообщения, даже в случае сбоев [269]. Традиционный подходсостоит в том, что каждому сообщению приписывается уникальный номер сообщения, а каждый сервер сохраняет все номера сообщений, которые он принял,чтобы можно было отличить новое сообщение от повторной посылки. Проблемаэтого алгоритма состоит в том, что при сбое и перезагрузке сервера он теряет эту5.2. Логические часы285таблицу номеров сообщений. Неясно также, сколько времени хранить эти номерасообщений.С использованием времени традиционный алгоритм модифицируется следующим образом.
Итак, каждое сообщение имеет идентификатор связи (выбранный отправителем) и метку времени. Для каждого соединения сервер заноситв таблицу последнюю полученную метку времени. Если какое-либо входящее сообщение имеет отметку времени меньшую, чем отметка, сохраненная в таблицедля этого соединения, сообщение считается дубликатом и не рассматривается.Чтобы можно было удалить старую метку времени, каждый сервер постоянноподдерживает глобальную переменную G, определяемую следующим образом:G = CurrentTime - MaxLifetime - MaxClockSkew.Здесь MaxLifetime — максимальное время жизни сообщения, а MaxClockSkewуказывает на то, как далеко от времени UTC могут уйти часы. Любая метка времени старше G может быть легко удалена из таблицы, поскольку все сообщениястарше С уже прошли.
Если входящее сообщение имеет неизвестный идентификатор связи, оно будет принято, если его метка времени более ранняя, чем G,и отвергнуто, если она более поздняя, чем С, поскольку всякое более позднее сообщение — это, несомненно, дубликат. В действительности G — это сумма номеров всех старых сообщений. Каждые AT текущее время сбрасывается на диск.В случае сбоя и последующей перезагрузки сервера он загружает значение Gиз файла, сохраненного на диске, и увеличивает его в ходе периода обновления, AT.Любое входящее сообщение с отметкой времени старше G — это дубликат.
В результате каждое сообщение, которое могло быть принято до сбоя, теперь отвергается. Некоторые новые сообщения могут быть отвергнуты ошибочно, но присоблюдении всех условий алгоритм поддерживает семантику «не более одногосообщения».Вдобавок к этому алгоритму в [269] также описано, как можно использоватьсинхронизированные часы для достижения непротиворечивости кэша, как использовать посылки тайм-аута для аутентификации распределенных систем и какобработать обязательства по атомарным транзакциям. Мы обсудим некоторые изэтих алгоритмов в следующих пунктах.
По мере улучшения синхронизации таймеров для них, несомненно, будут найдены и другие приложения.5.2. Логические часыВо многих случаях необходимо, чтобы все машины договорились об использовании одного и того же времени. Не столь уж и важно, чтобы это время совпадалос истинным временем, которое каждый час объявляют по радио. Для работы программы make, например, достаточно, чтобы все машины считали, что сейчас 10:00,даже если на самом деле сейчас 10:02. Так, для некоторого класса алгоритмов подобная внутренняя непротиворечивость имеет гораздо большее значение, чем то,насколько их время близко к реальному. Для таких алгоритмов принято говоритьо логических часах {logical clocks).286Глава 5.
СинхронизацияВ своей классической статье (см. [249]) Лампорт (Lamport) показал, что хотясинхронизация часов возможна, она не обязательно должна быть абсолютной.Если два процесса не взаимодействуют, нет необходимости в том, чтобы их часыбыли синхронизированы, поскольку отсутствие синхронизации останется незамеченным и не создаст проблем. Кроме того, он указал, что обычно имеет значениене точное время выполнения процессов, а его порядок. В примере с программойmake, который мы приводили в предыдущем разделе, нас интересовало, чтобыфайл input.c был более старым или более новым, чем input.o, а не абсолютное время их создания.В этом пункте мы обсудим алгоритм Лампорта, предназначенный для синхронизации логических часов.
Кроме того, мы рассмотрим расширение методаЛампорта, векторные отметки времени. Лампорт сделал дополнения к своей работе в [251].5 . 2 . 1 . Отметки времени ЛампортаДля синхронизации логических часов Лампорт определил отношение под названием «происходит раньше». Выражение а-^Ь читается как «а происходит раньше Ь»и означает, что все процессы согласны с тем, что первым происходит событие а,а позже — событие Ь, Отношение «происходит раньше» непосредственно исполняется в двух случаях.4- Если а и й — события, происходящие в одном и том же процессе, и а происходит раньше, чем й, то отношение а-^Ь истинно."¥ Если а — это событие отсылки сообщения одним процессом, а й — событиеполучения того же сообщения другим процессом, то отношение а-^Ь также истинно. Сообщение не может быть получено до отсылки или дажев тот же самый момент, когда оно было послано, поскольку для пересылкинеобходимо конечное ненулевое время.Отношение «происходит раньше» — это транзитивное отношение, то естьв случае, если а->Ь и Ь-^с, выполняется условие а-^с.
Если два события, х и г/,происходят в разных процессах, которые не обмениваются сообщениями (ни непосредственно, ни через третий процесс), то отношение х-^у не истинно, впрочем, как и у-^х. Такие события называются параллельпыми {concurrent). В данном случае это означает только то, что никто не может (или не хочет) знать отом, где и какое из этих событий произошло.Нам нужен способ измерения времени каждого события, который позволилбы поставить в соответствие каждому событию а отметку времени С(<2), котораяподошла бы всем процессам. Эти отметки времени должны быть такими, чтобыпри <2->6 соблюдалось соотношение С(а)<С(Ь).
Перефразируя условие, котороемы ранее установили, если аи b — два события одного процесса и а происходитраньше, чем 6, то С(а)<С(Ь). Например, если а — это посылка сообщения однимпроцессом, Sib — прием этого сообщения другим процессом, то С(а) и С(Ь) должны быть назначены так, чтобы значения С(а) и С(Ь) соответствовали отношениюС(а)<С(Ь). Кроме того, время по часам. С, всегда идет вперед (увеличивается).5.2. Логические часы287а назад — никогда (не уменьшается).
Коррекция времени должна производитьсятолько путем добавления к нему положительного значения, а не его вычитанием.Давайте теперь рассмотрим алгоритм Лампорта, применяемый для присвоения времен событиям. Обсудим три процесса, описанные на рис. 5.7, а. Процессы запущены на различных машинах, каждая из которых имеет собственные часы и скорость работы. Как можно увидеть по рисунку, когда часы процесса Опоставят отметку времени 6, в процессе 1 они покажут 8, а в процессе 2 — 10. Каждые часы идут с постоянной скоростью, но эти скорости различны из-за разницы в кристаллах.Го"Го~~о"Т"0^6 -->,,^А8106 --^^А8101216201216201824 -..В^301824 --..В3024324024324030405030405036480^-^ 6036480^^60^^^^^.^70425670426148648048D...---69805472907072906080100|7680100^ ^ ^Рис. 5.7.
Три процесса, каждый с собственными часами, которые ходят с разнойскоростью (а). Подстройка часов по алгоритму Лампорта (б)В момент 6 процесс О посылает сообщение А процессу 1. Сколько времени этосообщение проведет в пути, зависит от того, каким часам мы верим. В любомслучае, когда оно придет в процесс 1, его часы будут показывать 16. Если сообщение будет содержать время отправки, 6, процесс 1 сочтет, что на пересылкуушло 10 тиков. Это значение вполне разумно. В соответствии с этими рассуждениями сообщение В от процесса 1 процессу 2 будет доставлено за 16 тиков, этовновь разумное значение.Перейдем к самой забавной части наших рассуждений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
