sistemas distribuidos
Post on 30-Dec-2015
94 Views
Preview:
DESCRIPTION
TRANSCRIPT
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 duplicadosPuede 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
p Servidor de tiempo, S
mt
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
TiTi - 3
Servidor B
Servidor A
Tiempo
m m'
Tiempo
Ti - 2 Ti - 1
Mensajes intercambiados entre dos pares NTP
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/2o 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 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 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
Eventos ocurridos en tres procesos
p1
p2
p3
a b
c d
e f
m1
m2
Tiempofísico
Marcas temporales lógicas - Ejemplo
Marcas temporales de Lamport para los 3 eventos
a b
c d
e f
m1
m2
21
3 4
51
p1
p2
p3
Tiempofísico
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 proceso único para un determinado rol
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 requerimiento es satisfecho al salir de la CS el token es devuelto al servidor
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 y también un punto crítico de falla
Algoritmo de Ricart-Agrawala (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 contestarSi no
Contestar inmediatamente a pi
Al liberar el testigoestado = LIBERADO;Responder a todas las peticiones encoladas.
Sincronización multicast
P1P1 P3P3
P2P2
<41, p1><41, p1>
<41, p1><41, p1>
<34, p2><34, p2><34, p2><34, p2>
respuestarespuestarespuestarespuesta
respuestarespuesta
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 central
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 coordinador: con identidad del nuevo coordinador
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
P2P1 P3 P4respuestarespuestarespuestarespuesta
elecciónelecciónelecciónelección
P2P1 P3 P4respuestarespuesta
elecciónelecciónelecciónelección
P2P1 P3 P4
P2P1 P3 P4
coordinadorcoordinador
P2P1 P3 P4respuestarespuestarespuestarespuesta
elecciónelecciónelecciónelección
P2P1 P3 P4respuestarespuesta
elecciónelecciónelecciónelección
P2P1 P3 P4
P2P1 P3 P4
coordinadorcoordinador
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 retransmite 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 no- participante 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 anilloEl mensaje de elección contiene 24 pero el proceso 28 loreemplazará 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
top related