Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

4.4. Итоги 271

каждому процессу в распределенной системе. Процесс предлагает точку доступа

в ответ на предоставление ему адреса этой точки доступа. Очевидно, что этот

подход имеет ограниченную масштабируемость.

Второй подход состоит в пересылке указателей. Каждый раз при перемеще-

нии сущности в другое место она оставляет за собой указатель, информирующий

о том, куда она переместилась. Локализация сущности требует обхода цепочки

пересылаемых указателей. Чтобы устранить длинную цепочку указателей, важно

уменьшить длину цепи после перемещения.

Третий подход состоит в создании базы сущности. Каждый раз при переме-

щении сущности в другое место она уведомляет об этом свою базу. При локали-

зации сущности первым делом о текущей локализации запрашивается ее база.

Четвертый подход состоит в построении иерархического дерева поиска. Сеть

разбивается на неперекрывающиеся области (домены). Домены могут группиро-

ваться в домены верхнего уровня (неперекрывающиеся) и т. д. Существует один

домен верхнего уровня, охватывающий всю сеть. Всякий домен на любом уровне

имеет ассоциированный с ним направляющий узел. Если сущность находится в

домене

Z),

направляющий узел в домене следующего уровня содержит указатель

на D. Направляющие узлы самого нижнего уровня содержат адреса сущностей.

Направляющий узел самого верхнего уровня содержит сведения обо всех сущно-

стях.

Сущности, локализация которых больше не нужна, могут быть удалены. Важ-

ная цель использования имен в распределенных системах

—

создание ссылок на

сущности так, чтобы сущности, на которые нет ссылок, удалялись автоматиче-

ски.

Такая сборка мусора требует подсчета ссылок или трассировки.

В случае подсчета ссылок сущность просто считает количество созданных на

нее ссылок. Когда счетчик достигнет нуля, сущность можно удалять. В отличие

от подсчета ссылок можно также поддерживать список ссылок на процессы, ссы-

лающиеся на сущность. Список ссылок более устойчив, чем счетчик ссылок, но

имеет проблемы с масштабированием.

В методах трассировки все сущности прямо или косвенно ссылаются на за-

данный набор корневых сущностей, которые помечаются как доступные. Недос-

тупные сущности удаляются. Распределенная трассировка трудна, поскольку тре-

буется проверить все сущности в системе. Решения разнообразны, но в основном

они основаны на традиционных сборщиках мусора, характерных для однопро-

цессорных систем.

Вопросы и задания

Приведите пример ситуации, в которой для реального доступа к сущности Е

ее адрес разрешается в другой адрес.

Зависит или нет от локализации URL-адрес http://www.acme.org/index.html?

Как насчет адреса http.V/www.acme.nl/index.html?

Приведите несколько примеров правильных идентификаторов.

Как найти точку монтирования в большинстве UNIX-систем?

272 Глава 4. Именование

Jade

—

это распределенная файловая система, использующая отдельные про-

странства имен для каждого пользователя

[371].

Другими словами, каждый

пользователь имеет собственное закрытое пространство имен. Могут ли име-

на из подобных пространств имен при разделении ресурсов совместно исполь-

зоваться несколькими пользователями?

6. Рассмотрим DNS. Для ссылки на узел

Л^

в поддомене, реализованном в дру-

гой нежели текущий домен зоне, должен быть определен сервер имен для этой

зоны. Всегда ли необходимо включать запись о ресурсах для адреса этого сер-

вера или иногда достаточно указать только его доменное имя?

Может ли идентификатор содержать информацию о сущности, которую он

идентифицирует?

8. Опишите эффективную реализацию глобально уникальных идентификаторов.

9. Приведите пример того, как должен работать механизм свертывания в URL.

10.

Объясните разницу между жесткой и мягкой ссылкой в UNIX-системах.

11.

Высокоуровневые серверы имен в DNS (то есть серверы имен, реализующие уз-

лы пространства имен DNS, близкие к корню) обычно не поддерживают рекур-

сивного разрешения имен. Можно ли достичь значительного повышения произ-

водительности, если они будут поддерживать рекурсивное разрешение имен?

12.

Опишите, как можно использовать DNS для реализации ориентированного

на наличие базы способа локализации мобильных хостов.

13.

Существует особая форма локализации сущности, называемая индивидуаль-

ной рассылкой (anycasting), в которой служба определяется по IP-адре-

су

[345].

Посылка запроса на адрес индивидуальной рассылки приводит к по-

лучению ответа от сервера, который реализует службу, определяемую по

адресу индивидуальной рассылки. Опишите реализацию службы индивиду-

альной рассылки, основанную на иерархической службе локализации, описан-

ной в пункте 4.2.4.

14.

Где корень, если считать, что двухзвенный подход, основанный на наличии

базы, является специализацией иерархической службы локализации?

15.

Предположим, известно, что конкретная мобильная сущность практически ни-

когда не выйдет за пределы домена D, а если это и случится, то быстро вер-

нется обратно. Как можно использовать эту информацию для ускорения опе-

рации поиска в иерархической службе локализации?

16.

Какое максимальное число локализующих записей необходимо обновить в

иерархической службе локализации глубины k при изменении местонахожде-

ния сущности?

17.

Рассмотрим сущность, перемещающуюся из места А в место В с посещением

нескольких промежуточных мест, в которых эта сущность находится относи-

тельно недолго. По прибытии в В она на время затихает. Изменение адреса

в иерархической службе локализации может потребовать относительно долго-

го времени, поэтому в ходе посещения промежуточных мест такого изменения

следует избегать. Как можно обнаружить сущность в промежуточном месте?

4.4. Итоги 273

18.

Как при передаче удаленной ссылки из процесса Р1 в Р2 при распределенном

подсчете ссылок увеличить счетчик Р1 независимо от Р2?

19.

Поясните, почему взвешенный подсчет ссылок эффективнее простого подсче-

та ссылок. Считайте связь надежной.

20.

Возможна ли при подсчете поколений ссылок такая ситуация, когда объект

будет сочтен мусором и уничтожен, поскольку невозможно определить, к ка-

кому поколению относится этот объект, хотя на него еще имеются ссылки?

21.

Возможно ли при подсчете поколений ссылок, чтобы значение

G[i]

оказалось

меньше нуля?

22.

При работе со списком ссылок, если после посылки команды ping процессу Р

не был получен ответ, процесс удаляется из списка ссылок на объект. Будет

ли правильным удалить этот процесс?

23.

Опишите очень простой способ определения момента достижения шага ста-

билизации при сборке мусора путем трассировки по

[255].

Глава 5

Синхронизация

5.1.

Синхронизация часов

5.2. Логические часы

5.3.Глобальное состояние

5.4. Алгоритмы голосования

5.5. Взаимное исключение

5.6. Распределенные транзакции

5.7. Итоги

В предыдущих главах мы рассматривали процессы и связь между процессами.

Хотя связь и очень важна, это еще не все. Не менее важны вопросы взаимодейст-

вия и синхронизации процессов друг с другом. Взаимодействие частично обеспе-

чивается именованием, которое позволяет процессам как минимум совместно ис-

пользовать ресурсы и вообще сущности.

В этой главе мы в основном сосредоточимся на том, как процессы синхрони-

зируются между собой. Так, например, важно, что несколько процессов не спо-

собны одновременно получать доступ к совместно используемым ресурсам, та-

ким как принтеры, а должны взаимодействовать, позволяя друг другу временно

получать эксклюзивный доступ к этому ресурсу. Другой пример. Несколько про-

цессов могут время от времени нуждаться в соглашениях о порядке прохожде-

ния сообщений, о том, например, что сообщение m1

от

процесса Р будет отправ-

лено раньше, чем сообщение т2 от процесса Q.

Как оказывается, синхронизация в распределенных системах часто значи-

тельно сложнее, чем синхронизация в однопроцессорных или мультипроцессор-

ных системах. Проблемы и решения, которые обсуждаются в этой главе, являются

по своей природе глобальными и случаются во множестве различных ситуаций

в распределенных системах.

Мы начнем с обсуждения синхронизации, основанной на реальном времени,

продолжим обсуждение синхронизацией, у которой всего один относительный

параметр упорядочивания, не считая упорядочивания по абсолютному времени.

Мы обсудим также понятие распределенного глобального состояния и то, как

это состояние записывается в процессе синхронизации.

5.1.

Синхронизация часов 275

Во многих случаях важно, чтобы группа процессов назначила один из процес-

сов координатором. Это обычно происходит в соответствии с алгоритмом голо-

сования. Мы рассмотрим различные алгоритмы голосования в отдельном разделе.

Две отдельные темы, касающиеся синхронизации,

—

это взаимные исключе-

ния в распределенных системах и распределенные транзакции. Распределенные

взаимные исключения позволяют совместно использовать ресурсы, предотвратив

возможность одновременного доступа нескольких процессов. Распределенные

транзакции делают нечто похожее, но посредством совершенствования механиз-

ма контроля за параллельным выполнением. Взаимные исключения и транзак-

ции будут обсуждаться в отдельных разделах.

Существуют распределенные алгоритмы на любой «вкус и цвет» для распре-

деленных систем самых разных типов. Множество примеров (и дополнительной

информации) можно найти в [17, 421, 497]. Более формальный подход к изо-

билию существующих алгоритмов проводится в

[277].

5.1.

Синхронизация часов

в централизованных системах время определяется однозначно. Если процессу

необходимо время, он организует системный вызов, и ядро выдает ему ответ. Ес-

ли процесс Л запрашивает время, а немного позже то же самое делает процесс

J3,

значение, которое получит 5, будет больше (или, возможно, равно) значению, по-

лученному А. Оно не может быть меньше. В распределенных системах достиже-

ние договоренности о времени не столь тривиально.

Для того чтобы понять, к чему могут привести проблемы определения гло-

бального времени, достаточно одного примера с программой make операционной

системы UNIX. Обычно в UNIX большие программы разбиваются на несколько

файлов исходного текста, и внесение изменений в один из этих файлов требует

повторной компиляции не всех, а только одного из этих файлов. Такой подход

значительно повышает производительность работы программистов. Например,

если программа содержит 100 файлов, а исправлен был только один, достаточно

перекомпилировать только этот файл.

Обычная методика применения программы make проста. Когда программист

заканчивает свою работу, изменив все файлы с текстом программы, он запускает

программу make, которая проверяет время последней модификации всех файлов

с исходным текстом и всех объектных файлов программы. Если файл с исход-

ным текстом input.c имеет время последней модификации 2151, а соответствую-

щий ему объектный файл input.o

—

2150, make считает, что input.c со времени соз-

дания input.o был изменен, и перекомпилирует его. С другой стороны, если

output.c имеет время последней модификации 2144, а output.o

—

2145, компиля-

ция не требуется. Таким образом, программа make проверяет все файлы с исход-

ным текстом в поисках тех из них, которые нуждаются в повторной компиляции,

вызывая при необходимости компилятор.

Представим теперь, что произойдет, если в распределенной системе отсутст-

вует глобальное соглашение о времени. Предположим, что output.o, как и ранее.

276 Глава 5. Синхронизация

имеет отметку времени изменения 2144, а output.c после создания был модифи-

цирован, но получил отметку времени 2143, потому что часы на машине, где он

находится, немного запаздывают, как это показано на рис. 5.1. Тогда программа

make не станет вызывать компилятор. В результате исполняемый файл програм-

мы будет содержать смесь объектных файлов из старых и новых исходных фай-

лов.

При исполнении это легко может привести к ошибкам, и программист сой-

дет с ума, пытаясь понять, что в его коде не так.

Компьютер, 2144 2145 2146 2147 < Время по локальным

на котором ф I , I часам

выполняется ^s.

компиляция ^ Создан файл output.o

Компьютер, 2142 2143 2144 2145 < Время по локальным

на котором 1 Ф 1 1 часам

выполняется ^\

редактирование Создан файл output.c

Рис. 5.1. Когда каждая из машин имеет собственные часы, событие, происшедшее позже

другого, может быть отнесено к более раннему времени

Поскольку время лежит в основе человеческого мышления, а эффект от отсут-

ствия синхронизации может быть, как мы сейчас показали, столь печален, изуче-

ние синхронизации можно начать с простого вопроса: Можно ли синхронизиро-

вать все часы в распределенной системе?

5.1.1.

Физические часы

Почти все компьютеры имеют встроенные периодические процессы для подсчета

времени. Несмотря на постоянное использование для этих устройств названия

«часы», они не являются часами в обычном смысле этого слова. Пожалуй, более

правильным словом было бы таймер (timer). Таймер компьютера

—

это обычно

особым образом обработанный кристалл кварца. Находясь под напряжением,

этот кристалл колеблется с постоянной частотой, которая зависит от свойств крис-

талла, таких как способ разрезания и величина напряжения. С каждым кристал-

лом ассоциированы два регистра

— счетчик (counter) и регистр

хранения

(holding

Каждое колебание кристалла уменьшает счетчик на единицу. Когда зна-

чение счетчика достигает нуля, генерируется прерывание и счетчик перезагружа-

ется из регистра хранения. Таким образом, можно запрограммировать таймер ге-

нерировать прерывания 60 раз в секунду или с любой другой желаемой частотой.

Каждое прерывание вызывается одним тиком таймера

(clock

tick).

Когда система загружается в первый раз, она обычно просит пользователя вве-

сти дату и время, которые пересчитываются в число тиков, начиная с определен-

ной стартовой даты, и сохраняются в памяти. Многие компьютеры имеют специ-

альную микросхему CMOS RAM с питанием от аккумулятора, в результате в них

нет необходимости вводить время при каждой загрузке. После каждого тика тай-

мера процедура обработки прерывания добавляет единицу к хранящемуся в па-

мяти времени. Таким образом, часы (программные) сохраняют верное время.

5.1.

Синхронизация часов 277

Для единственного компьютера и единственных часов маленькая неточность

этих часов не вызовет проблемы. Поскольку все процессы в машине используют

одни и те же часы, они будут внутренне непротиворечивы. Так, например, если

файл input.c имеет отметку времени

2151,

а файл input.o

—

2150, make перекомпи-

лирует этот файл, даже если часы отстают на два деления и истинное время со-

ставляет соответственно 2153 и 2152. Все это, разумеется, относится к относи-

тельному времени.

В том случае, если мы перейдем к рассмотрению нескольких компьютеров,

каждый из которых имеет собственные часы, картина изменится. Несмотря на то

что частота каждого из кристаллов обычно весьма стабильна, невозможно гаран-

тировать, что кристаллы на различных компьютерах будут иметь абсолютно оди-

наковую частоту. На практике, когда в систему входит п компьютеров, все п кри-

сталлов работают с несколько отличаюш;ейся частотой, что ведет к постепенной

потере синхронизации и выдаче часами при обраш^ении к ним различных значе-

ний. Эта разница в показаниях часов называется

рассигисронизацией

часов

{clock

skew).

В результате рассинхронизации часов программы, которые ожидают, что

время, ассоциируюпдееся с файлом, объектом или сообщением, корректно и не

зависит от машины, на которой оно определялось (то есть часы которой исполь-

зовались), могут работать неправильно. Мы продемонстрировали это чуть выше

на примере программы make.

В некоторых системах (это так называемые системы реального времени) точ-

ность часов необходима. Для таких систем нужно использовать внешние фи-

зические часы, причем для эффективности и защищенности желательно иметь

несколько физических часов. Это вызывает две проблемы. Во-первых, как син-

хронизировать их с часами реального мира? Во-вторых, как синхронизировать

эти часы друг с другом?

Перед тем как ответить на эти вопросы, давайте немного отступим от нашей

темы, чтобы понять, как на самом деле измеряют время. Это вовсе не так просто,

как можно было бы подумать. С тех пор как в XVH веке были изобретены механи-

ческие часы, время стало определяться по астрономическим наблюдениям. Каждый

день солнце встает на востоке, поднимается на максимальную высоту и заходит

на западе. Момент подъема солнца на максимально возможную высоту называ-

ется

солнечным переходом

(transit of

sun).

Это событие происходит около полуд-

ня.

Интервал между двумя последовательными солнечными переходами называ-

ется солнечным днем {solar day). День делится на 24 часа, каждый из которых

содержит 3600 с.

Солнечная секунда {solar second)

определяется как 1/86 400 сол-

нечного дня. Геометрические построения, необходимые для расчета солнечного

дня, приведены на рис. 5.2.

В сороковых годах двадцатого веки было установлено, что период обращения

земли непостоянен. Земля замедляется из-за приливного трения и вязкости ат-

мосферы. На основе изучения колец роста древних кораллов геологи полагают,

что 300 миллионов лет назад в году было около 400 дней. Продолжительность

года (время одного оборота вокруг солнца) при этом не изменилась, сутки про-

сто стали длиннее. Вдобавок к этому медленному изменению существуют крат-

кие вариации продолжительности суток, связанные, вероятно, с завихрениями

278 Глава 5. Синхронизация

глубоко в земном ядре, состоящем из расплавленного железа. Эти открытия по-

требовали от астрономов расчета ситуации для множества дней с усреднением

результатов перед делением их на 86

400.

Получившееся значение было названо

средней солнечной

секундой

{mean solar

second).

Орбита Земли

Солнечный переход

отмечается в момент

прохода Солнцем

наивысшей

за день точки

Земля в день

при солнечном переходе

Земля в день 1

при солнечном переходе

В момент солнечного

перехода через п дней

Земля повернется менее

чем на 360°

Направление

на удаленную галактику

Направление

на удаленную галактику

Рис. 5.2. Расчет среднего солнечного дня

После изобретения в 1948 году атомных часов появилась возможность еще

более точного измерения времени, независимо от вращения и колебаний земли,

путем подсчета переходов атома цезия-133. Физики переняли работу по хране-

нию времени у астрономов и определили секунду как время, за которое атом це-

зия-133 совершит ровно 9 192 631 770 переходов. Выбор числа 9 192 631 770 сделал

атомную секунду равной средней солнечной секунде в год ее расчета. В настоя-

щее время около 50 лабораторий по всему миру имеют часы на цезии-133. Пе-

риодически каждая лаборатория сообщает в международное бюро мер и весов

в Париже, сколько времени на их часах. Международное бюро усредняет их ре-

зультаты и выдает

глобальное

время по

атомным часам

{International Atomic

Time,

TAI).

TAI

—

это среднее время тиков часов на цезии-133, прошедшее с полуночи

1 января 1958 года (начала времен) и деленное на 9 192 631 770.

Хотя время ТА! весьма стабильно и доступно каждому, кто в состоянии пре-

одолеть проблемы, связанные с покупкой цезиевых часов, имеется серьезная проб-

лема: 86 400 с TAI в настоящее время приблизительно на 3 мс меньше среднего

солнечного дня (потому что средний солнечный день все время удлиняется). Ис-

пользуя TAI для хранения времени, надо понимать, что постепенно полдень бу-

дет наступать все раньше и раньше, пока, наконец, от утра почти ничего не оста-

нется. Это станет заметно населению, и мы столкнемся с ситуацией вроде той,

что была в 1582 году, когда Папа Григорий ХП1 объявил, что 10 дней календаря

пропускаются. Это событие привело к уличным бунтам, поскольку домовладель-

цы требовали у работников плату, а банкиры

—

процент за полный месяц, в то

5.1.

Синхронизация часов 279

время как работодатели отказывались платить работникам за те 10 дней, что они

не работали. Но это были лишь небольшие столкновения. Протестантские стра-

ны принципиально отвергали любые папские декреты, не переходя на григори-

анский календарь еще 170 лет.

Международное бюро решило эту проблему, используя потерянные секунды

{leap seconds)

всякий раз, когда разница между временем TAI и солнечным вре-

менем возрастает до 800 мс (рис. 5.3). Эта коррекция позволила перейти к системе,

основанной на постоянных секундах TAI, в которой, однако, соблюдается соот-

ветствие с периодичностью очевидно видимого движения солнца. Она называет-

ся универсальным согласованным временем {Universal Coordinated Time, UTC).

UTC

—

это основа всей системы хранения времени в наши дни. Оно, по существу,

заменило старый стандарт

—

среднее время по Гринвичу

{Greenwich

mean time),

которое основывалось на астрономических наблюдениях и расчетах.

О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

^^^^f^^^

I—I—\—I—1—1—I—I—ЬЧ—I

I I I I I I I I

I—\—I—I—\—I—I

TAI

Солнечные

12345 6 789 11 12 1314 15 16 17 18 19 2122 23 24 25

I—\ 1 Н \ 1 1 \—bed

1—h-HH

1 1 \—1^1 I I—I 1

секунды

•-ed

1—H—I

1 1 \—hyH

Потерянные секунды,

введенные во время UTC

для его синхронизации со временем ТА!

Рис. 5.3. Секунды TAI в отличие от солнечных секунд имеют постоянную длительность,

поэтому

для

синхронизации времени UTC и времени TAI

используют потерянные секунды

Большинство электрических компаний положили в основу измерения времени

для своих 60-герцевых или 50-герцевых часов систему UTC, а когда междуна-

родное бюро объявляет потерянную секунду, компании, производящие электро-

энергию, меняют частоту на 61 или 51 Гц для 60 или 50 с, чтобы чуть подвести

часы в той зоне, где они работают. Поскольку для компьютера 1 с

—

это замет-

ный интервал, операционная система, которой нужно знать точное время за не-

сколько лет, может обрабатывать объявленные потерянные секунды с помощью

специального программного обеспечения (если только она не использует для оп-

ределения времени линию питания, что обычно слишком неточно). Общее число

потерянных секунд, введенных во время UTC, к настоящему времени составляет

примерно 30.

Для предоставления времени UTC тем, кому необходимо точное время, на-

циональный институт стандартного времени (National Institute of Standard Time,

NIST) имеет коротковолновую радиостанцию с позывными WWV из форта Кол-

линз (Fort Collins), штат Колорадо. Радиостанция WWV широковещательно

рассылает короткий импульс в начале каждой секунды UTC. Точность самой ра-

диостанции WWV составляет около ±1 мс, но из-за различных атмосферных

флуктуации длина сигнала может меняться, так что на практике точность

составляет не более ±10 мс. В Англии станция MSF, работающая из Регби

(Rugby), район Варвикшир (Warwickshire), предоставляет похожую службу. Су-

ществуют также станции и в некоторых других странах.

280 Глава 5. Синхронизация

Некоторые спутники Земли также предоставляют службы UTC. Рабочий

спутник геостационарного окружения (Geostationary Environment Operational Sa-

tellite) может предоставлять время UTC с точностью до 0,5 мс, а некоторые дру-

гие

—

и с более высокой точностью.

Использование как коротковолновых радиосигналов, так и спутниковых

служб требует точных сведений об относительном положении отправителя и по-

лучателя с целью компенсации задержки распространения сигнала. Радиоприем-

ники для WWV, GEOS и других источников UTC имеются в продаже.

5.1.2. Алгоритмы синхронизации часов

Если одна машина имеет приемник WWV, нашей задачей является поддержание

синхронизации с ней всех остальных машин. Если приемников WWV нет ни на

одной из машин, то каждая из них отсчитывает свое собственное время, и нашей

задачей будет по возможности синхронизировать их между собой. Для проведе-

ния синхронизации было предложено множество алгоритмов [ИЗ, 129,

240].

Их

обзор имеется в

[370].

Все алгоритмы имеют одну базовую модель системы, которую мы сейчас рас-

смотрим. Считается, что каждая машина имеет таймер, который инициирует пре-

рывание Н раз в секунду. Когда этот таймер срабатывает, обработчик прерываний

добавляет единицу к программным часам, которые сохраняют число тиков (пре-

рываний), начиная с какого-либо момента в прошлом, о котором была предвари-

тельная договоренность. Будем считать, что мы можем вызвать значение этих ча-

сов С. Конкретнее, когда время UTC равно t, значение часов машины р

—

Cp(t).

В идеальном мире мы можем считать, что

Cp(t)

= t для всех р и всех t. Другими

словами, dC/dt

—

точно единица.

Реальные таймеры не генерируют прерывания точно Н раз в секунду. Теоре-

тически таймер с Я= 60 должен генерировать 216 000 тиков в час. На практике

относительная ошибка, допустимая в современных микросхемах таймеров, состав-

ляет порядка 10"^. Это означает, что конкретная машина может выдать значение

в диапазоне от 215 998 до 216 002 тиков в час. Уточним. Пусть имеется констан-

та р:

\-p<dC/dt< l+p.

В этих пределах таймер может считаться работоспособным. Константа р оп-

ределяется производителем и известна под названием максимальной скорости

дрейфа (maximum drift rate). Отстающие, правильные и спешащие часы иллюст-

рирует рис. 5.4.

Если двое часов уходят от UTC в разные стороны за время

А^

после синхро-

низации, разница между их показаниями может быть не более чем 2р-А^. Если

разработчики операционной системы хотят гарантировать, что никакая пара ча-

сов не сможет разойтись более чем на 5, синхронизация часов должна произво-

диться не реже, чем каждые 5/2р с. Различные алгоритмы отличаются точностью

определения момента проведения повторной синхронизации.