Sincronización distribuida de relojes

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

Protocolo NTP (Network Time Protocol): Sincronización externa, uso de la señal UTC. Es un protocolo de Internet que usando UDP (Protocolo de datagramas de usuario) en su capa de transporte sincroniza los relojes de las diferentes máquinas. Se basa en una jerarquía de servidores divididos por estratos en los que el nodo raíz recibe la señal UTC  y los nodos hoja son las estaciones de usuario. Consigue su sincronización mediante el envío de marcas de tiempo entre los servidores. El objetivo de NTP es proporcionar un sistema fiable.

La estructura jerárquica de servidores divididos por estratos es conocida como subred de sincronización

• En el nivel más alto se encuentran los relojes UTC, que corresponden al estrato 0.
• Los servidores primarios ocupan el estrato 1 y actúan como la raíz de la subred.
• Los servidores secundarios se ubican en el estrato 2 y se sincronizan con los servidores primarios.
• Los servidores del estrato 3 se sincronizan con los servidores del estrato 2.
• Este patrón se repite hasta llegar al estrato n.
• Los servidores de nivel más bajo, también conocidos como hojas, se ejecutan en las estaciones de trabajo de los usuarios.

Tanto El algoritmo Cristian como el de Berkeley tienen problemas de escalabilidad, NTP lo soluciona.

Protocolo SNTP(Simple Network Time Protocol): Sincronización externa, uso de la señal UTC. Es una versión más simple de NTP, utilizada sobre todo cuando se requiere menos complejidad computacional entre las estaciones de red, ya que no requiere almacenar información de otros envíos para sus algoritmos de control, por tanto también es menos fiable que NTP .

Depuración Distribuida

La ejecución de un sistema distribuido se puede depurar por las transiciones entre estados globales consistentes, es decir, mediante la evaluación del predicado. Un predicado de estado global es una función que pasa del conjunto de estados globales de los procesos en el sistema a verdadero, falso.

Características de un predicado

• Estabilidad: el valor del predicado no cambia con los nuevos sucesos (por ejemplo, en el caso de interbloqueo o terminación)
• Seguridad: el predicado tiene valor falso para cualquier estado alcanzable desde S₀
• Veracidad: el predicado tiene valor verdadero para algún estado alcanzable desde S₀

Monitorización

La monitorización para realizar la depuración de un sistema distribuido requiere registrar la ejecución del sistema a lo largo del tiempo y así registrar su estado global, para poder hacer evaluaciones de predicados.

El algoritmo de instantánea de Chandy y Lamport recoge el estado de una forma distribuida y el algoritmo de Marzullo y Neiger es centralizado.

Los procesos observados envían sus estados a un proceso llamado monitor, que ensambla estados globalmente consistentes de los que recibe, el monitor registra los mensajes de estado en colas de proceso.

Evaluación de predicados

El objetivo de la monitorización es determinar si un predicado φ es “posiblemente” o “sin duda alguna” verdadero en un determinado punto de la ejecución, los estados globales consistentes son los únicos que el monitor registra porque solo en estos se puede evaluar el predicado con certeza.

Red de estados globales

Mediante la monitorización podemos construir una red de estados globales consistentes.

Sij=estado global tras i eventos en el proceso 1 y j eventos en el proceso 2.

Es importante definir que una linealización es una ruta entre estados.

Se definirá los siguientes casos para un predicado en función de las linealizaciones:

• Posiblemente φ: Significa que hay un estado consistente S a través del cual pasa una linealización tal que φ(S) = Verdadero​

• Sin duda alguna φ: Significa que para todas las linealizaciones que pasan por un conjunto de estados consistente S* se cumple que para todo S en S*, φ(S)=Verdadero.​

Por ejemplo, imaginemos un sistema de 2 procesos donde queremos controlar el predicado: |X₁- X₂| > 50.

En la figura 1, vemos el ejemplo y analizamos el predicado en los cortes que se presentan, en el cual podemos ver que en el corte C1 es verdadero cuando aplicamos la condición |X₁- X₂| > 50.

En la figura 2, vemos la construcción de la red de estados globales a partir de la figura1, que se corresponde con cada estado en las variables (X₁,X₂) y la red luego de realizar las evaluaciones de predicado, es sobre esta red donde se evalúa “posiblemente” y “sin duda alguna”. En el ejemplo, vemos que en el estado S₂₀ se cumple que “sin duda alguna” hay un problema de consistencia porque este estado es verdadero para todas las linealizaciones que pasan por él.

Bibliografía

• G.Colouris, J.Dollimore, T.Kindberg and G.Blair: Distributed Systems Concepts and Design.

Enlaces externos

[1] [2] [3][4]

• Datos: Q56324133