Sincronización de Relojes en Sistemas Distribuidos: Fundamentos y Algoritmos

Sincronización de Procesos

La manera en que los procesos cooperan y se sincronizan entre sí está muy relacionada. La cooperación es soportada mediante la asignación de nombres. Es crucial asegurar que varios procesos no accedan al mismo recurso en el mismo instante, evitando así problemas de concurrencia.

Sincronización del Reloj

En sistemas centralizados, cuando un proceso quiere saber la hora, realiza una llamada al sistema y el núcleo responde. Si un proceso A pregunta la hora, y después un proceso B pregunta la hora, obtendrá un valor mayor o igual. Sin embargo, en un Sistema Distribuido (SD), lograr un acuerdo con respecto al tiempo no es una tarea trivial.

Relojes Físicos

Las computadoras tienen un circuito para medir el tiempo. Más que relojes, son cronómetros basados en un cristal de cuarzo mecanizado con precisión.

• Cuando se les aplica tensión, los cristales de cuarzo oscilan a una frecuencia bien definida, la cual depende del tipo de cristal, la forma de su corte y la cantidad de tensión.
• Hay dos registros asociados a cada cristal: un contador y un registro mantenedor. Cada oscilación del cristal disminuye el contador. Cuando este llega a 0, se genera una interrupción y el contador se reinicia a partir del registro mantenedor. Esto permite programar un cronómetro para generar una interrupción 60 veces por segundo, o a cualquier otra secuencia deseada. Cada interrupción se llama marca de reloj.
• Cuando un sistema se inicia, generalmente solicita al usuario la fecha y la hora, las cuales se convierten en el número de marcas posteriores a una fecha de inicio conocida y se almacenan en memoria.
• Con solo una computadora y un solo reloj, no importa mucho si el reloj está desfasado por una pequeña cantidad. Debido a que todos los procesos de la máquina usan el mismo reloj, serán internamente consistentes.

El problema surge cuando aparecen varias CPU. Aunque la frecuencia con la que oscilan los cristales es bastante estable, es casi imposible garantizar que los cristales de las diferentes computadoras funcionen exactamente con la misma frecuencia. Cuando un sistema tiene n computadoras, los n cristales funcionarán a velocidades ligeramente diferentes, lo que ocasiona que los relojes (software) se salgan gradualmente de sincronía y arrojen valores diferentes cuando se leen.

Relojes Lógicos

Lamport (1978) mostró que la sincronización de relojes es posible, pero no absoluta. Si dos procesos no interactúan, no tienen por qué sincronizar sus relojes. Lo importante no es que todos los relojes coincidan en el tiempo absoluto, sino que coincidan en el orden de los eventos. En el ejemplo de make, lo que cuenta es que input.c es más antiguo o más reciente que input.o, y no sus tiempos absolutos de creación.

Relojes Lógicos de Lamport

Para sincronizar relojes, Lamport definió la relación llamada Ocurrencia Anterior.

• La expresión a -> b se lee “a ocurre antes que b”.
• Significa que todos los procesos coinciden en que ocurre el primer evento a y, después, ocurre b.