La sincronización distribuida de relojes trata de solucionar los problemas surgidos por la necesidad de comunicar distintos computadores que trabajan en una tarea conjunta.
Estos problemas ocurren debido a que cada computador posee relojes independientes cuya arquitectura, por muy precisa que sea, hace imposible que tenga tiempos idénticos.
Dicha sincronización se ha logrado mediante el estudio de diversas técnicas y métodos (Algoritmo de Cristian, Algoritmo de Berkeley, etcétera)
Introducción La sincronización de relojes en un sistema distribuido se utiliza para forzar un orden parcial o total en la ejecución de procesos y eventos del sistema.
Los computadores poseen dos tipos de relojes, hardware y software: el primero es capaz de generar una señal periódica, el segundo simula el comportamiento de un reloj normal a partir del de hardware.
Surge la necesidad de sincronizar estos relojes debido a lo que se conoce como sesgo y deriva del reloj, que provocan que dos relojes en un mismo momento tengan tiempos distintos.
Clasificación de relojes en un sistema Distribuido
Relojes Físicos: miden el tiempo real. Lógicos: dan un marco de referencia de los eventos y del orden en el que ocurren.
Dentro de los relojes físicos se pueden subdividir en:
Externos: los relojes se sincronizan con una fuente de tiempo externa fiable.
Internos: los relojes no se sincronizan con una fuente de tiempo externa.
Dentro de los relojes lógicos se dividen en:
Local: cada proceso internamente maneja su propio reloj local el cual ayuda a sincronizar eventos.
Tipos de relojes
Reloj hardware Toda computadora ha de tener un reloj hardware.
Algunos sistemas operativos como MS-DOS, OS/2 o Windows presuponen que el reloj de hardware muestra la hora local (MS-DOS, Windows, OS/2).
Existen dos tipos comunes:
Relojes enlazados con energía Están enlazados a una línea de 110 o 220 voltios y producen una interrupción en cada ciclo de voltaje. Son los que tienen una arquitectura y funcionamiento más simple, antiguamente eran los que dominaban el mercado, no obstante, ahora se han visto relegados por los relojes programables, los cuales son más precisos.
Relojes programables o RTCs (Reloj en tiempo real) Es más preciso y seguro ya que suele ser alimentado por una batería, la cual asegura el funcionamiento del reloj, aunque la computadora no tenga suministro eléctrico durante meses e incluso años.
Consta de estos elementos:
Oscilador de cristal: Una pieza de cristal de cuarzo bien cortada y montada bajo tensión, la cual oscila generando una señal periódica de mucha precisión. Registro Contador: El contador se alimenta cada vez que oscila la señal de cuarzo, esto provoca que el contador cuente de forma descendente hasta 0, generando en dicho momento una interrupción de CPU. Registro constante o contenedor: Se usa para cargar el registro contador.
Tiene dos modos de operación:
Una instancia (un disparo) : Cuando el reloj se inicializa el registro contador copia el valor del registro contenedor. Se decrementa el registro contador en cada oscilación del cristal de cuarzo hasta que llega a cero, en ese momento, genera una interrupción y se detiene hasta que el software lo inicialice de nuevo. Onda cuadrada: Comienza igual que el modo anterior, no obstante, después de llegar a cero y generar la correspondiente interrupción, el registro contenedor se copia de manera automática en el registro contador. Es decir, el programa se repite en bucle.
Reloj software Simula el funcionamiento de un reloj normal a partir del reloj hardware del computador.
El reloj hardware realmente lo único que hace es generar interrupciones a intervalos conocidos y bien marcados de tiempo, todo lo demás que se relacione con el tiempo en el computador debe ser realizado por el reloj software.
Podemos resumir de una forma muy general las funciones principales del reloj software:
Contener la hora y fecha actuales, coordinada con el huso horario que indiquemos. Controla el tiempo de ejecución de los procesos. Mantiene un registro de uso de la CPU, se tiene noción de cuándo se inicia un proceso y cuando se detiene, cuánto tiempo pasa detenido, si se reanuda, etcétera. Proporciona cronómetros o temporizadores guardianes al sistema, también llamados watchdogs (Perro guardián (electrónica)) . Maneja y supervisa estadísticas, gracias a los registros mencionados previamente.
El reloj software establece una fecha de origen (En el caso de Linux esa fecha es el 1 de enero de 1970 a las 00:00), toma la fecha y hora actual y calcula el número de ticks desde dicha fecha origen hasta la fecha actual, con cada tick incrementa el número de estos y se recalcula la fecha actual a partir de la de origen.
En Linux, durante el inicio el kernel, obtiene la fecha y hora actual a partir del reloj hardware, una vez hace esto, el kernel mantiene su fecha y hora independiente del reloj hardware.
Sesgo y tasas de derivas de reloj La deriva de reloj o drift (Deriva de reloj) representa el tiempo que un reloj se desvía respecto a la hora real, es decir, aunque un reloj marque exactamente la hora real en un momento determinado, es imposible que marque infinitamente dicho tiempo de manera perfecta, siempre se desvía (en mayor o menor medida).
Cada tipo de reloj tiene una tasa de deriva, por ejemplo, un reloj normal se desvía como media, aproximadamente un segundo cada 12 días, un reloj de precisión se desvía sobre un segundo cada cuatro meses o tres años y un reloj atómico se desvía en torno a 1 segundo cada miles de millones de años.
Dentro de un mismo tipo, cada reloj tiene una tasa de deriva propia.Supongamos que una misma marca crea dos relojes aparentemente iguales, los pone a funcionar ahora mismo y ambos marcan la misma hora. Pasado un tiempo dichos relojes (debido a que es prácticamente imposible crear dos relojes exactamente iguales) tendrán cada uno un tiempo diferente para un instante determinado, esta diferencia de tiempo se llama sesgo de reloj (skew) (Sesgo de reloj).
Por tanto, el sesgo de reloj da como consecuencia que una misma señal de reloj de origen llega a los distintos componentes en diferentes momentos, es decir, se crea una diferencia entre la lectura de los dos relojes en un instante concreto.
En un sistema distribuido lo ideal sería que el clock skew sea cero. No obstante, hay varios factores que causan diferencias en las distintas señales de reloj.
Podemos diferenciar dos tipos de sesgo de reloj según como se rija el reloj de referencia:
El sesgo positivo ocurre cuando el registro emisor recibe el tic del reloj antes que el registro receptor. El sesgo negativo es el caso contrario, el registro de recepción obtiene la marca del reloj antes que el registro emisor.
Este es el principal problema que nos lleva a la necesidad de tener que sincronizar los relojes de las distintas computadoras.
Por ejemplo imaginemos que el computador uno marca un día a las 21:11:11 (h:m:s) y el computador dos marca las 21:11:10 (Lo normal es que el sesgo sea bastante inferior a los nanosegundos, pero se usa este ejemplo para explicarlo de una forma más entendible).
C1 enviaría un mensaje a C2, por ejemplo, a las 21:11:11 según R1 (reloj de C1), el mensaje tarda en enviarse solo medio segundo, este mensaje llegaría a C2 según R2 (reloj de C2) medio segundo antes de que se enviara según R1. Esto llevado a supuestos más complejos puede dar lugar a grandes problemas.
Sincronización de relojes Ambos tipos de relojes tienen una importancia fundamental en la tarea de sincronización distribuida debido a que al contrario que los sistemas centralizados (Computación centralizada) que tienen un reloj único accesible para todas computadoras, en los sistemas distribuidos el orden en que transcurren los eventos se logra mediante diversos mecanismos que usan los relojes de cada computadora, siempre respetando el orden cronológico de los sucesos.
Cabe mencionar que para el correcto funcionamiento del sistema son necesarios algoritmos de exclusión mutua(Exclusión mutua en sistemas distribuidos), que aseguran el acceso a una sección crítica(Sección crítica) para respetar la integridad de los archivos. Algunos de dichos algoritmos necesitan del uso de relojes lógicos.
Diferenciaremos entre:
Sincronización externa: Todos los relojes se sincronizan con una referencia única mediante un servidor de UTC (Tiempo Universal Coordinado). Sincronización interna: Sincronización entre varios relojes sin importar la hora correcta.
Algoritmos de sincronización Para lograr la sincronización de relojes en sistemas distribuidos existen varios algoritmos y protocolos. Los algoritmos de sincronización son herramientas utilizadas para garantizar la consistencia y la integridad de los datos en sistemas distribuidos y en redes de datos. Los algoritmos de sincronización funcionan mediante la actualización de los datos en tiempo real en todos los nodos con los que cuenta el sistema. Para lograr esto, los algoritmos de sincronización utilizan diferentes técnicas, como el uso de marcas de tiempo, relojes lógicos y vectores de tiempo de ordenamiento. En general, estos algoritmos aseguran que los datos se mantengan actualizados y se sincronicen correctamente entre los nodos del sistema, lo que es esencial para el correcto funcionamiento de los sistemas distribuidos (con los cuales está estrechamente relacionado).
Cristian(Algoritmo de Cristian): Usa sincronización externa e interna. Es un algoritmo centralizado en un servidor de tiempo UTC, que manda el tiempo a un receptor de nuestro sistema que se denominará receptor de UTC, el resto de clientes se sincronizarán con dicho equipo.
Los clientes mandarán peticiones periódicas al receptor UTC pidiéndole el tiempo UTC, y este le responderá lo más rápido posible. Obviamente, el cliente solo sincroniza si el tiempo UTC de respuesta es mayor que el de la petición.
Problemas:
Si el servidor falla. Una solución sería tener más servidores. No existe control sobre fraudes o malfuncionamiento por parte del servidor. Escalabilidad.
Desventajas:
El algoritmo de Cristian tiene una limitación importante debido a la presencia de un solo servidor. Para solucionar este problema, Cristian propuso el uso de múltiples servidores de tiempo que estén sincronizados entre sí. En este caso, el cliente envía una solicitud de tiempo a todos los servidores disponibles y utiliza la respuesta más rápida que recibe.
Cabe destacar que el algoritmo de Cristian no considera la posibilidad de que el servidor falle o actúe de manera fraudulenta, lo que puede llevar a una sincronización incorrecta del reloj del cliente
Berkeley(Algoritmo de Berkeley): Sincronización interna, no dispone de señal UTC. Es un algoritmo centralizado en un servidor maestro elegido por todas las computadoras conectadas. El servidor periódicamente muestrea el tiempo de las computadoras y con esa información estima un tiempo que es comunicado al resto de las máquinas para su sincronización.
Problemas:
Si el servidor falla. Una solución sería elegir a un nuevo maestro. Escalabilidad.
Algoritmo de tiempos lógicos de Lamport (Tiempos lógicos de Lamport): Sincronización interna, no dispone de la señal UTC. Este algoritmo recibe su nombre del matemático y científico Leslie Lamport. Se basa en la siguiente metáfora (Algoritmo de la panadería de Lamport) :En una panadería los clientes van entrando y cogen un número único que referencia al número de llegada para que los dependientes los atiendan. Lo fundamental es que el dependiente solo atiende a una persona al mismo tiempo.
Pone énfasis en la relación “sucede antes que”, si dos eventos han ocurrido en el mismo proceso, el proceso sabe cual ha sido su orden, aparte es fundamental la idea de que el envío de un mensaje ocurre antes que su recepción. Asocian una marca de tiempo para su funcionamiento
Protocolos de sincronización