Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 73
Текст из файла (страница 73)
Это означает, что конкретная машина может выдать значениев диапазоне от 215 998 до 216 002 тиков в час. Уточним. Пусть имеется константа р:\-p<dC/dt< l+p.В этих пределах таймер может считаться работоспособным. Константа р определяется производителем и известна под названием максимальной скоростидрейфа (maximum drift rate). Отстающие, правильные и спешащие часы иллюстрирует рис. 5.4.Если двое часов уходят от UTC в разные стороны за время А^ после синхронизации, разница между их показаниями может быть не более чем 2р-А^. Еслиразработчики операционной системы хотят гарантировать, что никакая пара часов не сможет разойтись более чем на 5, синхронизация часов должна производиться не реже, чем каждые 5/2р с.
Различные алгоритмы отличаются точностьюопределения момента проведения повторной синхронизации.5 . 1 . Синхронизация часов281Время по часам, сВремя UTC, tРис. 5.4. Соотношение между временем по часам и временем UTCпри различной частоте тиковАлгоритм КристианаДавайте начнем с алгоритма, хорошо подходящего для систем, в которых одна измашин имеет приемник WWV, а наша задача состоит в синхронизации всех остальных машин по ней. Назовем машину с приемником WWV сервером времени{time server). Наш алгоритм [113] основан на работах Кристиана (Cristian) и болееранних.
Периодически, гарантировано не реже, чем каждые 5/2р с, каждая машинапосылает серверу времени сообщение, запрашивая текущее время. Эта машинатак быстро, как это возможно, отвечает сообщением, содержащим ее текущее время, Сутсу как показано на рис. 5.5.То и Ti отсчитываются по одним и тем же часамКлиентСервервремениВремя обработки прерывания, IВремя-Рис. 5.5. Получение текущего времени с сервера времениВ качестве первого приближения, когда отправитель получает ответ, он может просто выставить свои часы в значение Сите- Однако такой алгоритм имеетдве проблемы: главную и второстепенную. Главная проблема состоит в том, чтовремя никогда не течет назад.
Если часы отправителя спешат. Сите может оказаться меньше текущего значения С у отправителя. Простая подстановка Ситеспособна вызвать серьезные проблемы, связанные с тем, что объектные файлы,скомпилированные после того, как было изменено время, помечены временемболее ранним, чем модифицированные исходные тексты, которые поправлялисьдо изменения времени.282Глава 5. СинхронизацияИзменения могут вноситься постепенно. Один из способов таков. Предположим, что таймер настроен так, что он генерирует 100 прерываний в секунду.В нормальном состоянии каждое прерывание будет добавлять ко времени по 10 мс.При запаздывании часов процедура прерывания будет добавлять каждый развсего по 9 мс.
Соответственно, часы должны быть исправлены так, чтобы добавлять при каждом прерывании И мс вместо того, чтобы переключать все времяодновременно.Менее серьезная проблема состоит в том, что перенос ответного сообщения ссервера времени отправителю требует ненулевого времени.
Хуже всего, что этазадержка может быть весьма велика и зависеть от загрузки сети. По Кристиану,метод решения проблемы состоит в измерении этой величины. Отправителю достаточно просто аккуратно записать интервал между посылкой запроса и приходом ответа. То и другое время (начальное Го и конечное Т\), измеряется по одним и тем же часам, а значит, интервал будет относительно точно измерен даже втом случае, если часы отправителя имеют некоторое расхождение с UTC.В отсутствии какой-либо дополнительной информации наилучшим приближением времени прохождения сообщения будет (Т\~ То)/2. После получения ответа, чтобы получить приблизительное текущее время сервера, значение, содержащееся в сообщении, следует увеличить на это число. Если теоретическоеминимальное время прохождения известно, следует рассчитать другие параметры времени.Эта оценка может быть улучшена, если приблизительно известно, скольковремени сервер времени обрабатывает прерывание и работает с пришедшим сообщением.
Обозначим время обработки прерывания /. Тогда величина интервала времени между TQHTU затраченного на прохождение сообщения, будет равнаT\~TQ- I, и лучшей оценкой времени на прохождение сообщения в одну сторонубудет половина этой величины. Существуют системы, в которых сообщение из Ав В постоянно движется по одному маршруту, а из В в Л — по другому. Они будут иметь другое время прохождения, но мы здесь не будем рассматривать этислучаи.Для повышения точности Кристиан предложил производить не одно измерение, а серию. Все измерения, в которых разность Т\-То превосходит некотороепороговое значение, отбрасываются как ставшие жертвами перегруженной сети,а потому недостоверные.
Оценка делается по оставшимся замерам, которые могут быть усреднены для получения наилучшего значения. С другой стороны, сообщение, пришедшее быстрее всех, можно рассматривать как самое точное, поскольку оно предположительно попало в момент наименьшего трафика и потомунаиболее точно отражает чистое время прохождения.Алгоритм БерклиВ алгоритме Кристиана сервер времени пассивен. Прочие машины периодическизапрашивают у него время. Все, что он делает, — это отвечает на запросы. В операционной системе UNIX разработки университета Беркли (Berkeley) принятпрямо противоположный подход [188].
Здесь сервер времени (а на самом деле демон времени) активен, он время от времени опрашивает каждую из машин, какое5.1. Синхронизация часов283время на ее часах. На основании ответов он вычисляет среднее время и предлагает всем машинам установить их часы на новое время или замедлить часы, пока небудет достигнуто необходимое уменьшение значения времени на сильно ушедших вперед часах.
Этот метод применим для систем, не имеющих машин с приемником WWV. Время демона может периодически выставляться вручную оператором. Это продемонстрировано на рис. 5.6.Демон времени3:003:000,+253:000 Q2:503:253:05\ 11 /1+51^-20]ШШ ШШ2:503:252:503:25Рис. 5.6. Демон времени запрашивает у всех остальных машин значения их часов (а).Ответы машин (б). Демон времени сообщает всем, как следует подвести их часы (е)В 3:00 демон времени сообщает всем машинам свое время и запрашивает этимашины об их времени (рис. 5.6, а). Затем демон времени получает ответ о том,насколько спешат или отстают часы машин от часов демона (рис. 5.6, б).
Знаяэти числа, демон времени вычисляет среднее и сообщает каждой из машин, какей следует подвести свои часы (рис. 5.6, в).Усредняющие алгоритмыОба ранее описанных алгоритма сильно централизованы с неизбежно вытекающими отсюда недостатками. Известны также и децентрализованные алгоритмы.Один из классов алгоритмов децентрализованной синхронизации часов работаетна основе деления времени на синхронизационные интервалы фиксированнойпродолжительности. В этом случае z-й интервал начинается в момент времениГо + iR и продолжается до Го + (/ + 1)72, где Го — заранее согласованный прошедший момент, а i? — параметр системы. В начале каждого интервала каждая машина производит широковещательную рассылку значения текущего времени на своих часах.
Поскольку часы на различных машинах идут с немного различнойскоростью, эти широковещательные рассылки будут сделаны не одновременно.После рассылки машиной своего времени она запускает локальный таймери начинает собирать все остальные широковещательные пакеты в течение некоторого интервала 5. Когда будут собраны все широковещательные пакеты, запускается алгоритм вычисления по ним нового времени. Простейший алгоритм состоит в усреднении значений всех остальных машин. Незначительные его вариациизаключаются, во-первых, в отбрасывании т самых больших и т самых маленьких значений и усреднении оставшихся. Отбрасывание крайних значений можнорассматривать как самозащиту от т неправильных часов, посылающих ерунду.284Глава 5. СинхронизацияДругая вариация состоит в том, чтобы попытаться скорректировать каждоеиз сообщений, добавляя к ним оценку времени прохождения от источника. Этаоценка может быть сделана на основе знания топологии сети или измерениемвремени прохождения эха.Дополнительные алгоритмы синхронизации часов рассматриваются в [274,369, 429].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
