PDF de programación - L11 - Sincronizacion en los Sistemas Distribuidos

Lección 11

Sincronización en los
Sistemas Distribuidos

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Índice

• Introducción
• Relojes lógicos
• Relojes físicos

– Definición de segundo
– Sincronización de relojes

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Introducción

• Algunos algoritmos dependen de alguna forma

del paso del tiempo para su funcionamiento:
– Pueden requerir la hora exacta. Ej., para incluirla en

forma de timestamp en los mensajes

– O pueden necesitar sólo conocer en qué orden
ocurrieron ciertos eventos. Ej, la utilidad make

• Problema
Problema
Problema
En un sistema distribuido no hay un reloj único,
En un sistema distribuido no hay un reloj único,
sino uno en cada máquina y los relojes de los
sino uno en cada máquina y los relojes de los
computadores no son exactos.
computadores no son exactos.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Introducción: Funcionamiento del reloj

• En un computador la hora se mantiene gracias a un

oscilador de cuarzo.
– Cada oscilación genera un 1 seguido de un 0.
– Un circuito cuenta cuántos “unos” se han generado.
– Cuando la cuenta alcance un valor prefijado, se generará una

interrupción.

– Cada vez que el sistema operativo recibe una interrupción, avanza

un contador.

– Este contador permite calcular el tiempo transcurrido desde el

arranque, y por tanto la hora.

Problema
Problema
La frecuencia de oscilación del cuarzo puede ser ligeramente
La frecuencia de oscilación del cuarzo puede ser ligeramente
diferente entre máquinas, causando que el reloj adelante o
diferente entre máquinas, causando que el reloj adelante o
atrase.
atrase.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Reloj lógico

• Observar que:

– Si el cuarzo no oscila a la frecuencia correcta, la hora que el

computador “cree” que es es falsa

– Pero incluso en ese caso, existe una consistencia lógica entre

las horas que el computador genera, ya que

Si dos eventos a y b ocurren cuando el contador vale
Si dos eventos a y b ocurren cuando el contador vale
respectivamente Na y Nb, siendo Na mayor que Nb, esto
respectivamente Na y Nb, siendo Na mayor que Nb, esto
implica que el evento a ocurrió después que b. Es decir:
implica que el evento a ocurrió después que b. Es decir:

Na > Nb
Na > Nb

⇒ ta > tb
⇒ ta > tb

• En cambio, si a y b son eventos en diferentes

máquinas, la implicación anterior no es
necesariamente cierta

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Ejemplo

Observar
Observar
En los eventos e y f, se da que
En los eventos e y f, se da que
te < tf y sin embargo Ne > Nf
te < tf y sin embargo Ne > Nf

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Observación [Lamport]

• La hora real, ta, a la que ocurre un evento a es

desconocida. Sólo podemos conocer lo que marca el
reloj de esa máquina en ese instante, Na

Definición
Definición
La relación a fi
La relación a fi
antes que el evento b”, por tanto ta < tb
antes que el evento b”, por tanto ta < tb

b significa “El evento a ocurrió
b significa “El evento a ocurrió

• Sin conocer ta ni tb

¿Cuándo podremos afirmar que a fi
– 1. Cuando a y b ocurren en la misma máquina y Na < Nb
– 2. Cuando a representa el envío de un mensaje y b su

b?

recepción (aunque sea en diferentes máquinas)

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Idea [Lamport]

• ¿Será posible asignar a cada evento e un número C(e)

que cumpla

• Es decir:

C(a) < C(b) ⇒ a fi

b

?

– Si a ocurre antes que b en la misma máquina, debe

cumplir C(a) < C(b).

• Esto lo cumple el contador de interrupciones de la máquina

con tal de que no se le haga retroceder

– Si a es el envío de un mensaje y b es su recepción,

debe cumplirse C(a) < C(b)

• Para que esto se cumpliera debería incluirse C(a) en el

mensaje, y actualizar el reloj en b.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Algoritmo de Lamport

• Se usa como C(a) de un evento a el valor del

contador de interrupciones de la máquina en que
ocurre el evento.

• Al enviar un mensaje, se incluye en el mismo el

contador de interrupciones en el momento del
envío, C(a).

• Al recibir un mensaje, se compara el contador de
interrupciones local, C(b), con el valor que viene
en el mensaje, C(a)
– Si C(a) < C(b) no hay contradicción lógica.

No se hace nada.

– Si C(a) ‡

‡ C(b) se adelanta el contador local,

haciendo C(b) = C(a) + 1

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

‡
‡
Algoritmo de Lamport

• Observaciones:

– Este algoritmo garantiza además que, si

b y b fi

c, entonces a fi

a fi

c

– Pueden existir pares de eventos a, b

tales que no sea posible afirmar a fi
b,
ni tampoco b fi
a. Se dice en este caso
que a y b son concurrentes, y se denota
por a||b.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Ejemplo (algoritmo de Lamport)

• Supongamos tres máquinas, X, Y y Z cuyos osciladores tienen
diferentes frecuencias de modo que mientras en Z se producen
10 interrupciones, en Y se producen 8 y en X sólo 6.

• La máquina X envía un mensaje a Y , poco después, ésta envía

un mensaje a Z. Más tarde Z responde a Y y seguidamente Y
responde a X.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Ejemplo (algoritmo de Lamport)

Cuando se detecta una contradicción al recibir un mensaje se
adelanta el reloj en el receptor

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Relojes físicos

• Denominaremos reloj físico a uno que marca la hora

exacta, y no una mera ordenación de eventos como
en el caso de los relojes lógicos.

• La definición de “hora exacta” es más compleja de lo

que parece a simple vista.
– El segundo estaba definido como 1/86400 del día
– Pero resulta que la longitud del día sufre pequeñas

variaciones, quizás por alteraciones del núcleo de la tierra

– Se define el segundo solar medio, como 1/86400 del día
promedio tras medir la longitud de un gran número de días

– La rotación de la tierra sobre si misma se va ralentizando con
el tiempo, aunque no el giro alrededor del sol. La definición de
segundo solar por tanto no es constante. . .

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Definición moderna de segundo

• En lugar de las vueltas de la tierra, se cuentan las transiciones de

un átomo de cesio-133

• Un reloj atómico de cesio puede contar con precisión cuántas

transiciones hace un átomo de cesio-133 (resulta que las hace
con una frecuencia de F = 9 192 631 770 Hz.)

• Se define el TAI (International Atomic Time), como el número de

transiciones que ha hecho un átomo de cesio-133 desde el 1 de
Enero de 1958, dividido entre 9 192 631 770.

Le Bureau International
de l’Heure (BIH) en Paris
recibe información de
relojes de cesio, y
calcula el TAI.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

La hora UTC

• Medir el tiempo usando TAI presenta un problema:
– El “segundo de cesio” (TAI) es constante de un año a otro
– El “segundo solar” en cambio va creciendo con el tiempo,

debido a la ralentización de la rotación terrestre.

• Estas dos medidas, por tanto, se desincronizan.

– Cada vez que la diferencia entre los “segundos TAI” y los

“segundos solares” se hace mayor de 800ms, el BIH inserta
un “segundo bisiesto”, de modo que queden sincronizados de
nuevo.

• El contador de segundos (incluyendo bisiestos)

suministrado por el BIH, se denomina UTC (Universal
Coordinated Time), y es la referencia mundial de
“hora exacta”.

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Cómo obtener el valor de UTC

Mediante WWV
Mediante WWV
Es una emisora de radio de onda corta que emite un
Es una emisora de radio de onda corta que emite un
pulso cada vez que transcurre un segundo UTC.
pulso cada vez que transcurre un segundo UTC.

• Un computador puede equiparse con un
• Un computador puede equiparse con un

receptor WWV
receptor WWV

Mediante GPS
Mediante GPS
El sistema de localización global (GPS) basado en
El sistema de localización global (GPS) basado en
satélites, también suministra el valor de UTC con
satélites, también suministra el valor de UTC con
precisión de 10ms
precisión de 10ms

• Un computador puede equiparse con un
• Un computador puede equiparse con un

receptor GPS
receptor GPS

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Sincronización de relojes

• Caso más simple: una de las máquinas tiene un

receptor WWV o GPS, y las demás se deben sincronizar
con ella.

• Idea básica: Cada cierto tiempo, las restantes

máquinas piden la hora a la que tiene el receptor, y
usan la respuesta para poner en hora sus relojes.

Problemas
Problemas
• ¿Cada cuánto le preguntan la hora?
• ¿Cada cuánto le preguntan la hora?
• ¿Cómo se tiene en cuenta el retardo de la red?
• ¿Cómo se tiene en cuenta el retardo de la red?
• ¿Cómo poner en hora el reloj local una vez
• ¿Cómo poner en hora el reloj local una vez
recibida la respuesta? (Téngase en cuenta que no
recibida la respuesta? (Téngase en cuenta que no
puede retroceder)
puede retroceder)

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Frecuencia de sincronización

• Llamemos C(t) a la hora que tiene una máquina cuando la

hora real es t.
– Si su reloj fuera perfecto, cumpliría C(t) = t todo el tiempo, es

decir, dC/dt = 1

– Mientras el reloj adelante, dC/dt >1
– Mientras el reloj atrase, dC/dt < 1

• El fabricante de un reloj debe garantizar que dC/dt no se

aleja de 1 sin control, sino dentro de unos límites

r–= 1

dC

dt

siendo ρ el ratio máximo de deriva del reloj (dato del
fabricante)

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Frecuencia de sincronización

• Variación de la hora local con respecto a la

hora real

Universidad de Oviedo / Dpto. de Informática

ATC-Distribuidas

Frecuencia de sincronización

• Cuando h