Sistemas Distribuidos
Tiempo y
coordinación
Tiempo y coordinación
 Sincronización de relojes físicos
 Tiempo universal coordinado (UTC)
 Compensación de derivas
 Sincronización de relojes en SD
 Tiempo lógico y relojes lógicos
 Diagramas de tiempo
 Coordinación distribuida
 Exclusión mutua distribuida
 Elección
Introducción
 El tiempo es un tema interesante e importante en
los sistemas distribuidos (SD) y es deseable poder medirlo
con exactitud. Para ello se necesita sincronizar los relojes de
los componentes del sistema.
La sincronización es necesaria para:
 mantener la consistencia de los datos
 chequear la autenticidad de requerimientos a los servers
 eliminar updates duplicados
Puede ser:
 sincronización interna: por conocer con cierto grado
de precisión la diferencia de tiempo entre los relojes de dos
computadoras
 sincronización externa: mediante una fuente
autorizada de tiempo
La noción de tiempo físico es también un problema en SD
Sincronización de relojes
físicos
 Los relojes físicos de las computadoras están
limitados por su resolución
 Normalmente estos relojes sufren de deriva (drift)
 Para compensar estas divergencias las
computadoras se puede sincronizar con un servicio
de tiempo, por ej.: UTC - Coordinated Universal
Time
 Existen distintos algoritmos para sincronizar
Red
UTC
 Relojes atómicos
 Un segundo es el tiempo durante el cual un
átomo de Cesio 133 hace 9.192.631.770
transiciones
 Sin embargo fue definido originalmente en
términos de la rotación de la tierra
 UTC
 Estándar internacional basado en el tiempo
atómico pero donde se añaden o sacan segundos
“bisiesto” (leap)
 Se transmiten por señales de radio con una
exactitud de 0.1-10 ms.
Compensación de la deriva
en los relojes
 Si el reloj de la computadora atrasa con respecto
al servicio de tiempo
 se adelanta
 se pierden algunos ticks pero
no hay problema
 Al revés, es decir, si adelanta
 no se puede atrasarlo. La solución es
lentificar el reloj hasta normalizarlo
 no en hardware sino en software
Método de Cristian para
sincronizar relojes (1989)
mr
mt
p
Servidor de tiempo, S
 Si el tiempo retornado por S en el mensaje mt es t,
p pondría su reloj en t + Tround/2
 El tiempo del reloj S cuando el mensaje mt arriba es
[t + min, t + Tround - min], el ancho del rango es
Tround - 2 min y la exactitud es ±(Tround/2 - min)
Discusión del algoritmo de
Cristian
 El servidor de tiempo puede fallar
 Un grupo de servidores de tiempo sincronizados
 cada uno con un receptor para las señales de
tiempo del UTC
 un cliente puede multicast sus requerimientos
a todos los servidores y usar la primera respuesta
que reciba
 puede haber un servidor de tiempo que
funcione mal o que sea un impostor
Algoritmo de Berkeley
(1989)
 Una computadora coordinadora actua como
master
y periódicamente encuesta a sus slaves cuyos
relojes están siendo sincronizados
 El master estima sus tiempos locales observando
el tiempo de round-trip (similar a la técnica de
Cristian) y promediando los valores obtenidos
 El master considera un promedio tolerante a fallos
 Si el master llegase a fallar se elige otro para que
ocupe su puesto de coordinador
Network time protocol
(NTP)
 NTP distribuye información del tiempo para proveer:
 un servicio para sincronizar clientes en Internet
 un servicio seguro que sobreviva a caidas
 una resincronización frecuente para disminuir la
deriva de los relojes de los clientes
 protección contra interferencias
 El servicio NTP es provisto por varios servidores y
está basado en UDP
 servidores primarios, secundarios y servidores
de otros niveles (estratos)
Subred de sincronización en
NTP
1
2
3
2
3
3
Nota: Las flechas indican control de la sincronización, los números indican
estratos.
Sincronización en NTP
 Los servidores NTP se sincronizan entre sí de tres
modos:
 multicast
 usado en LANs de alta velocidad
 los servidores transmiten periódicamente sus
tiempos
 bajas exactitudes, aunque eficiente
 procedure-call
 similar a la operación del algoritmo de
Cristian
 simétrico
 usado por master servers (el más seguro)
 pares de servers intercambian información
Intercambio de mensajes
Servidor B
Ti - 2
Ti - 1
Tiempo
m
Servidor A
Ti - 3
m'
Ti
Mensajes intercambiados entre dos pares NTP
Tiempo
Intercambio de mensajes
 Estimación del retardo y offset en el protocolo NTP:
 a = Ti-2 - Ti-3
 b = Ti –Ti-1
 di = a + b (retardo, medida de la exactitud de
la estima del offset)
 oi = (a-b)/2 (estima del offset)
 oi- di/2o oi+ di/2 (o, offset verdadero)
Pares <oi, di> se le aplica un “filtro de dispersión”
Dispersión alta=datos relativamente inseguros
Tiempo y relojes lógicos
 El orden de los eventos
 si 2 eventos ocurren en el mismo proceso,
ocurren en el orden en que se los observa
 el evento de enviar un mensaje entre procesos
ocurre antes que el evento de recibirlo
 La relación sucedió antes (Lamport), indicada por

y
 HB1: Si  proceso p: x p y, luego x  y.
 HB2: P/cualquier mensaje m,
send(m)  rcv(m),
 HB3: Si x, y y z son eventos tales que: x  y
y  z, luego x  z.
Marcas temporales lógicas
 Reloj lógico (LC): Un contador por software
monotónicamente creciente
 Cp un reloj lógico para el proceso p, Cp(a): marca
lógica de un evento a en p, Cp(b): marca lógica
de un evento b
 LC1: evento ocurrido en proceso p, Cp := Cp + 1
LC2: a) p envía un mensaje m a q con valor
t = Cp
b) Cq := max(Cq,t) y aplica LC1 a rcv(m)
 Si a  b entonces C(a) < C(b), no a la inversa!
 Relojes totalmente ordenados
Marcas temporales lógicas Ejemplo
p1
a
b
m1
Tiempo
físico
p2
c
d
m2
p3
e
f
Eventos ocurridos en tres procesos
Marcas temporales lógicas Ejemplo
p1
1
2
a
b
p2
p3
m1
3
4
c
d
Tiempo
físico
m2
1
5
e
f
Marcas temporales de Lamport para los 3 eventos
Relojes totalmente
ordenados
 Los relojes lógicos sólo imponen un orden parcial
 Para un orden total uso (Ca, pa)
 (Ca, pa)< (Cb, pb)
si y sólo si Ca< Cb o (Ca = Cb y pa< pb)
Coordinación distribuida
 Los procesos distribuidos necesitan coordinar
sus
actividades
 Algunos servidores no tienen mecanismos de
sincronización incorporado
 En ciertos casos se utilizan mecanismos de
excusión mutua distribuida para obtener
seguridad, propiedades de ordenamiento y
“vivacidad” (problema de la sección crítica, CS)
 Algoritmos de elección: Métodos para elegir un
Exclusión mutua distribuida
 Los requerimientos básicos para este mecanismo:
 ME1 (seguridad): Como máximo se puede
ejecutar un proceso a la vez en la CS
 ME2 (vivacidad): Un proceso que requiera
entrar
a la CS eventualmente puede ser admitido
(ME2 implica que la implementación es libre de
deadlock)
 ME3 (ordenamiento): La entrada a la CS sería
admitida en un orden “sucedió-antes”
Soluciones
 Algoritmo del servidor central (un único servidor
otorga acceso a la CS)
 Algoritmo distribuido usando relojes lógicos
(algoritmo de Ricart y Agrawal, multicast a todos los
otros procesos)
 Algoritmo basado en anillo (los procesos se
disponen en un anillo lógico)
 el token circulante permite entrar a la CS
Algoritmo del server central
Algoritmo del server central
 El protocolo para ejecutar una CS:
 enter() (*entrar al bloque de CS si es
necesario*)
 ………. (*acceder a recursos compartidos en
CS*)
 exit()
(*dejar CS -ahora pueden entrar otros
procesos*)
 Conceptualmente, la respuesta del server es un
token para entrar en la CS
 si ningún proceso tiene el token el servidor lo
otorga
 si el token lo tiene otro proceso, el
Algoritmo del server central
 Se alcanzan las condiciones de seguridad y
vivacidad
 Ordenamiento
 se alcanza en casos normales
 cuando el servidor falla debe elegirse uno
nuevo,
en este caso, el ordenamiento de requerimientos
de ingresos será distinto a menos que se tomen
precauciones
 Problemas
 El server es un cuello de botella de la
performance
Algoritmo de RicartAgrawala (1981)
 Un algoritmo distribuído que usa relojes lógicos
 Basado en un acuerdo distribuído en lugar de un
servidor central
 Los procesos que quieren entrar a la CS multicast un
mensaje de requerimiento y pueden entrar sólo cuando
todos los otros procesos han respondido al mismo
 Cada proceso tiene un reloj lógico
 Forma de los mensajes para pedir el token: <T, pi>
 Cada proceso tiene un estado
 LIBERADO: deja el token
 PIDIENDO: desea el token
 OBTENIDO: posee el token
Algoritmo de Ricart-Agrawala
 Al iniciar:
estado := LIBERADO;
 Para obtener el testigo:
estado := PIDIENDO;
T := timestamp de la petición;
Difundir petición al resto de procesos;
Esperar hasta (num. de respuestas = n - 1);
estado := OBTENIDO;
 Al recibir una petición <Ti, pi> en el proceso pj (i  j)
Si (estado = OBTENIDO) o (estado = PIDIENDO y (T, pj) < (Ti, pi))
Encolar la petición de pi sin contestar
Si no
Contestar inmediatamente a pi
 Al liberar el testigo
estado = LIBERADO;
Responder a todas las peticiones encoladas.
Sincronización multicast
<41, p1>
respuesta
P1
P3
respuesta
respuesta
<34, p2>
<34, p2>
<41, p1>
P2
Sincronización multicast
 Obtener el token toma 2(n-1) mensajes
 (n-1) para multicast el requerimiento seguido
de (n-1) respuestas
 refinado tal que se requieren n mensajes
 más costoso que el algoritmo del server
central
 Una falla en un proceso hace el progreso
imposible
 No hay mejora en el cuello de botella en la
performance con respecto al algoritmo del servidor
Algoritmo basado en anillo
 La exclusión mutua es conferida obteniendo un token
pasado de un proceso a otro forma de anillo y en una
sola dirección
 la topología en anillo no tiene nada que ver con
conexiones físicas
 Si un proceso que no requiere entrar a la CS recibe el
token lo pasa hacia delante a su vecino
 Si un proceso requiere el token espera hasta que lo
recibe y entonces lo retiene
 Al salir de la CS envía el token a su vecino
 Toma de 1 a (n-1) mensajes obtener el token
Algoritmo basado en anillo
Algoritmo basado en anillo
 Si un proceso falla
 no se progresa más allá de él, hasta que se
aplica una reconfiguración
 los mensajes son enviados a lo largo del anillo
aún cuando ningún proceso requiera el token
 Si el proceso que mantiene el token falla
 se requiere una elección para elegir otro entre
los sobrevivientes, regenerar el token y
retransmitirlo
 asegurarse que el proceso falló realmente
(puede llegar a haber dos token)
Discusión
 Ninguno de los tres algoritmos parece un ejemplo
práctico muy prometedor para los SD
 ninguno soluciona el tema de fallas en los
procesos o las máquinas
 El del server central requiere el menor número de
mensajes aunque el server puede ser un cuello de
botella
 En general, es preferible que el server maneje
recursos para proveer exclusión mutua a los
clientes que accedan al mismo
Elecciones
 Una elección es un procedimiento realizado
para
elegir un proceso cuando el coordinador falla
 Objetivo: Elección única
Algoritmo del matón (bully) Silberschatz (1993)
 Se supone comunicación fiable, pero los procesos
pueden fallar
 Se intenta seleccionar al miembro sobreviviente con
mayor identificador
 Un proceso comienza la elección cuando nota que el
que el supervisor falla
 Todos los miembros del grupo conocen la identidad
y
dirección del resto
 Hay 3 tipos de mensajes:
 elección: se envía para anunciar elección
 respuesta: enviado en respuesta al anterior
Algoritmo del matón
 La elección comienza cuando un proceso envía un mensaje de elección a
los miembros con mayor identificador que él
 El proceso espera un mensaje de respuesta
 Si no llega ninguno, el proceso se considera elegido y envía un
mensaje de coordinador a los que tienen identificador menor
 Si llega al menos un mensaje de respuesta el proceso espera un
mensaje de coordinador
 Si no llega ninguno, comienza una nueva elección
 Si un proceso recibe un mensaje de coordinador toma al proceso que lo
envía como coordinador electo
 Si un proceso recibe un mensaje de elección devuelve un mensaje de
respuesta y comienza una nueva elección (si no lo había hecho ya)
 Cuando un proceso es restaurado después de una caída
 Si tiene el identificador mayor se considera el coordinador electo y
envía un mensaje de coordinación al resto
 Si no, comienza una elección
Algoritmo del matón
elección
P1
P2
respuesta
elección
P3
respuesta
elección
P1
P2
P4
P3
elección
P4
respuesta
P1
P2
P3
P4
P2
P3
P4
coordinador
P1
Algoritmo del matón
 Cuando un proceso falla recomienza la elección
 este proceso comienza la elección
 si tiene el identificador más alto decide ser el
coordinador y lo anuncia a los otros procesos
 esto ocurre aún cuando el coordinador funcione
(el “matón”)
 En el mejor caso: (n-2) mensajes
 el proceso con el 2º id más alto notifica la falla, se
elije él mismo coordinador y envía (n-2) mensajes
 Peor caso: O(n2) mensajes
 el proceso con más bajo id notifica la falla
Algoritmo basado en anillo Chang y Roberts (1979)
 Apropiado para una colección de procesos
dispuestos
en un anillo lógico
 Objetivo: elegir como coordinador el proceso con el
id más alto
 Se supone que:
 los procesos no conocen, a priori, la identidad de
los otros y sólo saben comunicarse con el vecino
 Todos los procesos están funcionales y
alcanzables durante la elección
 Tanenbaum (1992) da una variante en la cual los
procesos pueden fallar
Algoritmo basado en anillo
 Inicialmente todos los procesos están marcados como
no-participantes
 El proceso que inicia la elección envía un mensaje de elección
con su identificador a su vecino
 Cuando un proceso recibe un mensaje de elección
 Compara el identificador del mensaje con el suyo
 Si el suyo es menor
 Lo retransmite a su vecino
 Si el suyo es mayor
 Sustituye su identificador en el mensaje y lo retransmi
 Si son iguales
 Se considera coordinador electo y envía un mensaje de
coordinador
Algoritmo basado en anillo
 Cuando un proceso que no es el coordinador recibe
un
mensaje de elegido se marca el mismo como noparticipante y pasa el mensaje a su vecino
 La razón para el marcado de un proceso como
participante o no-participante
 los mensajes que se emiten cuando otro proceso
comienza una elección al mismo tiempo, son
extinguidos, siempre antes que el “ganador” de la
elección sea anunciado
 Peor caso: (3n-1) mensajes
 el vecino anti-horario tiene el id más alto
Algoritmo basado en anillo
El mensaje de elección contiene 24 pero el proceso 28 lo
reemplazará con su id cuando el mensaje lo alcance
Discusión
 Problemática de los algoritmos anteriores:
 se basan en timeouts: Retrasos de transmisión
pueden causar la elección de múltiples lideres
 la perdida de conexión entre dos grupos de
procesadores puede aislar permanentemente los
procesadores
Descargar

Servicios de Reloj - Departamento de Sistemas e Informática