Los algoritmos de sincronización horaria se utilizan ampliamente.
Por ejemplo, en los sistemas Unix, el comando Make solo se usa para compilar archivos de código recién modificados. El comando Make utiliza el reloj del cliente en ejecución para determinar qué archivos se han modificado. Sin embargo, si el código se coloca en el servidor de archivos y la hora en que el host ejecuta el comando make es diferente a la del servidor de archivos, es posible que el comando make no funcione correctamente.
Por ejemplo, cuando se juega Dota, varios clientes necesitan un reloj sincronizado para mantener la imagen de todos consistente. Por ejemplo, la hora del servidor de sincronización de la computadora PC puede lograr una precisión de sincronización muy alta.
Algoritmo de sincronización horaria
El algoritmo de sincronización horaria tiene las siguientes soluciones:
algoritmo de cristian
El trasfondo de la aplicación del algoritmo de Cristian es principalmente cuando un proceso P es como un servidor S solicitando tiempo:
1. P envía un paquete de solicitud a S para solicitar la hora.
2. Después de que S recibe el paquete de solicitud de P, agrega la hora actual de S al paquete y luego lo envía de regreso.
3. Después de que P recibe el paquete de datos, establece la hora actual en T+RTT/2.
RTT representa un tiempo de ida y vuelta, que es el tiempo desde que P envía hasta que recibe un paquete de datos. El algoritmo supone que enviar y recibir paquetes requiere la misma cantidad de tiempo en la red. Y también se supone que el tiempo de S es insignificante al procesar la solicitud. Según los supuestos anteriores, el algoritmo se puede mejorar de la siguiente manera:
Envíe varios paquetes de solicitud de P a S y luego tome el RTT más pequeño como el RTT dividido por dos y agréguelo al tiempo incluido en este paquete.
Análisis de precisión del algoritmo: suponga que min es el tiempo más corto de S a P y T es el tiempo incluido en el RTT definido anteriormente. Entonces, el rango de tiempo de ajuste de P debe ser [T+min, T+RTT-min]. De esta manera, el rango de desviación de tiempo está dentro de RTT-2min. La precisión del algoritmo mejorado debe ser RTT/2 min.
algoritmo algoritmo de Berkeley
El entorno de uso del algoritmo de Berkeley es diferente del algoritmo de Cristian. El algoritmo de Cristian se utiliza cuando un cliente solicita la hora correcta a un servidor. El algoritmo de Berkeley es un algoritmo para sincronizar relojes entre varios clientes. El algoritmo específico es el siguiente:
1. Primero seleccione un nodo de un anillo como Maestro mediante el Cambio y el Algoritmo de Robert.
2. Un Maestro utiliza el algoritmo de Cristian para solicitar la hora de cada nodo.
3. El Maestro evalúa la desviación de tiempo de cada nodo registrando el RTT promedio y eliminando los RTT con grandes desviaciones.
4. El Maestro envía la desviación horaria de cada nodo a cada nodo, permitiendo que los nodos se corrijan solos.
Una vez que el cliente recibe la hora, en términos generales, no ajustará la hora actual. Porque esto provocará algunos errores inexplicables en el programa. Porque en muchos algoritmos, es una suposición básica que el tiempo no se ajustará hacia atrás. Por ejemplo, haz el comando.
Hay una solución: dejar que el reloj corra más lento. Tómese un tiempo para adaptarse a la hora correcta.
Además, es necesario analizar el algoritmo Change y el algoritmo de Robert. Este algoritmo es el mismo que el algoritmo de sincronización horaria y es necesario al jugar a Dota. Cuando se inicializa dota, los relojes de cada jugador deben sincronizarse. Después de estar desconectado, se debe utilizar un algoritmo específico para encontrar un nuevo host:
El cambio y el algoritmo de Robert.
El algoritmo de cambio y de Robert supone que cada proceso tiene un UID y que puede haber un canal de comunicación sin dirección en una red en forma de anillo. El algoritmo es el siguiente:
1. Primero, cada nodo del anillo se identifica como no participante.
2. Cuando un proceso descubre que el host está fuera de línea, primero se identifica como participante y luego envía un paquete seleccionado por el host que contiene su propio UID al vecino.
3. Cuando el paquete de datos llega al vecino, primero lo compara con su propio UID. Si su propio UID es mayor que este UID, se identifica como participante, modifica el UID en el paquete de datos y también lo envía en el. datos en el sentido de las agujas del reloj.
4. Cuando un proceso recibe un paquete de datos y descubre que el UID en el paquete de datos es el mismo que su propio UID, inicia la segunda fase del algoritmo:
5. Este proceso se identifica como no participante y envía información sobre el host seleccionado al vecino, incluida información UID.
6. Este ciclo continúa hasta que el proceso regresa al Proceso seleccionado como host. Todo el proceso finaliza.
Este es un algoritmo para seleccionar un host en un sistema distribuido. Por supuesto, en circunstancias específicas, puede cambiar las condiciones de selección, como elegir el que tiene la velocidad de red más rápida o la CPU más rápida como host. Al mismo tiempo, este algoritmo también puede evitar la situación en la que varios procesos descubren que el host está fuera de línea al mismo tiempo y varios procesos buscan el host al mismo tiempo.
El pseudocódigo de este algoritmo se puede describir de la siguiente manera:
Inicio : M:= i:
Enviar <i> al vecino;
Al recibir el mensaje <j>;
Si M<j entonces M:=j;
Enviar <j> al vecino;
Elseif M=j entonces líder;
Endif;
Para obtener un análisis de complejidad detallado, modelos matemáticos y tablas estadísticas de este algoritmo, consulte este documento:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
Este artículo solo analiza varios algoritmos de sincronización horaria en sistemas centralizados y no analiza los algoritmos de sincronización de transmisión de referencia y protocolo de tiempo de red en sistemas distribuidos. Estudiaré NTP cuando tenga tiempo en el futuro.