Алгоритмы синхронизации времени широко используются.
Например, в системах Unix команда Make используется только для компиляции вновь измененных файлов кода. Команда Make использует часы работающего клиента, чтобы определить, какие файлы были изменены. Однако если код размещен на файловом сервере и время хоста, выполняющего команду make, отличается от времени файлового сервера, команда make может работать некорректно.
Например, при игре в Доту нескольким клиентам нужны синхронизированные часы, чтобы картинка у всех была единообразной. , Например, время сервера синхронизации компьютера ПК может обеспечить очень высокую точность синхронизации.
Алгоритм синхронизации времени
Алгоритм синхронизации времени имеет следующие решения:
Алгоритм Кристиана
Область применения алгоритма Кристиана в основном заключается в том, что процесс P подобен серверу S, запрашивающему время:
1. P отправляет пакет запроса S, чтобы запросить время.
2. После того, как S получает пакет запроса P, он добавляет к пакету текущее время S и затем отправляет его обратно.
3. После того, как P получает пакет данных, он устанавливает текущее время на T+RTT/2.
RTT представляет собой время прохождения туда и обратно, которое представляет собой время от отправки P до получения пакета данных. Алгоритм предполагает, что отправка и получение пакетов в сети занимают одинаковое количество времени. А еще предполагается, что время S при обработке запросов незначительно. На основании вышеизложенных предположений алгоритм можно усовершенствовать следующим образом:
Отправьте несколько пакетов запроса от P к S, а затем возьмите наименьшее значение RTT, разделенное на два, и прибавьте его ко времени, включенному в этот пакет.
Анализ точности алгоритма: предположим, что min — это кратчайшее время от S до P, а T — это время, включенное в RTT, определенное выше. Тогда диапазон времени установки P должен составлять [T+min, T+RTT-min]. Таким образом, диапазон отклонения времени находится в пределах RTT-2мин. Точность улучшенного алгоритма должна составлять RTT/2 мин.
алгоритм алгоритм Беркли
Среда использования алгоритма Беркли отличается от алгоритма Кристиана. Алгоритм Кристиана используется, когда клиент запрашивает у сервера точное время. Алгоритм Беркли — это алгоритм синхронизации часов между несколькими клиентами. Конкретный алгоритм следующий:
1. Сначала выберите узел кольца в качестве главного с помощью алгоритма изменения и Роберта.
2. Мастер использует алгоритм Кристиана для запроса времени каждого узла.
3. Мастер оценивает отклонение времени каждого узла, записывая среднее значение RTT и исключая RTT с большими отклонениями.
4. Мастер отправляет отклонение времени каждого узла каждому узлу, позволяя узлам корректировать себя.
После того, как клиент получит время, он, вообще говоря, не будет корректировать текущее время назад. Потому что это вызовет какие-то необъяснимые ошибки в программе. Потому что во многих алгоритмах основным предположением является то, что время не будет возвращено обратно. Например, выполните команду.
Решение есть: просто дайте часам идти медленнее. Потратьте некоторое время, чтобы привыкнуть к правильному времени.
Кроме того, необходимо обсудить алгоритм Change и алгоритм Роберта. Этот алгоритм аналогичен алгоритму синхронизации времени и необходим при игре в Доту. При инициализации доты необходимо синхронизировать часы каждого игрока. После отключения от сети для поиска нового хоста необходимо использовать определенный алгоритм:
Изменение и алгоритм Роберта
Алгоритм Чейна и Роберта предполагает, что каждый процесс имеет UID и что в кольцеобразной сети может существовать беснаправленный канал связи. Алгоритм следующий:
1. Во-первых, каждый узел в кольце идентифицирует себя как неучаствующий.
2. Когда процесс обнаруживает, что хост находится в автономном режиме, он сначала идентифицирует себя как участник, а затем отправляет выбранный хостом пакет, содержащий его собственный UID, соседу.
3. Когда пакет данных достигает соседа, он сначала сравнивает его со своим собственным UID. Если его собственный UID больше этого UID, он идентифицирует себя как участник, изменяет UID в пакете данных, а также отправляет его в пакете данных. данные по часовой стрелке.
4. Когда процесс получает пакет данных и обнаруживает, что UID в пакете данных совпадает с его собственным UID, он запускает вторую фазу алгоритма:
5. Этот процесс идентифицирует себя как неучаствующий и отправляет информацию о выбранном хосте соседу, включая информацию UID.
6. Этот цикл продолжается до тех пор, пока процесс не вернется к процессу, выбранному в качестве хоста. Весь процесс завершается.
Это алгоритм выбора хоста в распределенной системе. Конечно, при определенных обстоятельствах вы можете изменить условия выбора, например, выбрав в качестве хоста тот, у которого самая высокая скорость сети или самый быстрый процессор. В то же время этот алгоритм также позволяет избежать ситуации, когда несколько процессов одновременно обнаруживают, что хост находится в автономном режиме, и несколько процессов одновременно ищут хост.
Псевдокод этого алгоритма можно описать следующим образом:
Начало : М:= я:
Отправить <i> соседу;
При получении сообщения <j>;
Если M<j, то M:=j;
Отправить <j> соседу;
Иначе, если M=j, то лидер;
Эндиф;
Подробный анализ сложности, математические модели и статистические таблицы этого алгоритма можно найти в этой статье:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
В этой статье анализируются только несколько алгоритмов синхронизации времени в централизованной системе и не анализируются алгоритмы синхронизации протокола сетевого времени и эталонной широковещательной передачи в распределенных системах. Я буду изучать NTP, когда у меня будет время в будущем.