1 Comunicación en Grupos
2 Bibliografía Sistemas Operativos DistribuidosA. S. Tanenbaum, Prentice Hall, 1995 Distributed Systems Sape Mullender ,Editor. Addison Wesley –ACM Press 1994 Capítulos 11,12 y 13 Sistemas Distribuidos. Conceptos y Diseño G. Coulouris, J. Dollimore, T. Kindberg, Addison Wesley, 2001 Exploiting Replication. Chapter 15 in Distributed Systems, Thomas Joseph and Kenneth Birman. June Sape J. Mullender, ed., Addison-Wesley/ACM Press Series (1989).
3 Grupo o no Grupo ??? Gossip Process Group [Collouris et. al.]“ Our methodology is based on the PROCESS GROUP paradigm that has been suitably to partitionable systems “ BabaoGlu et. al. Process Group , ISIS [Birman 93]
4 Introducción “Group Communication”La finalidad de introducir el concepto de grupos es permitir que los procesos que trabajen con conjuntos de procesos como un única abstracción . Así un proceso puede enviar a un grupo de servidores “without having to know how many there are or where they are.”
5 Comunicación en grupo La comunicación es entre un grupo de procesosCuando un emisor envía, el mensaje lo reciben todos los miembros de un grupo Los grupos se entienden como dinámicos, se pueden crear y destruir grupos. Un proceso puede ser miembro de varios grupos, se puede unir a uno y dejar otro Algunas redes permiten diferentes tipos de broadcasting, lo que facilita la implementación de comunicación en grupo
6 Aspectos de diseño Los grupos pueden ser:abiertos: no-miembros pueden enviar al grupo cerrados: solo los miembros pueden enviar al grupo Los miembros del grupo pueden ser iguales ( peer) , o bien existe un miembro coordinador o líder De existir, los envíos se hacen al coordinador, que decide a qué miembro reenviar Membresía: se requiere cierto método para la creación y eliminación de grupos, así como permitir a los procesos que se unen o dejen grupos ( mecanismo distribuido vs. Servidor de grupos )
7 Aspectos de diseño: Membresíaun miembro crash -> deja de pertenecer al grupo. Los demás miembros deben descubrir en forma experimental que ya no pertenece . La salida o entrada a un grupo debe sincronizarse con el envió de mensajes ( Ex. Cuando se une al grupo debe RX todos los mensajes, como solucionar : cuando se une enviar un mensaje a todos , Hola! ) Si hay muchos procesos que fallan y el grupo no funciona. Se necesita protocolo de reconstrucción del grupo . Algún proceso toma la iniciativa , que pasa si mas de uno lo hace ?
8 Aspectos de diseño (cont.)Direccionamiento al grupo: como especifico un G para que un p le envie un mensaje ? Atomicidad: cuando se envía un mensaje a un grupo, llega a todos los miembros o no llega a ninguno ( propiedad all-or-nothing ) La atomicidad es una propiedad deseable ( facilita la programación de los Sistemas Distribuidos )
9 Atomicidad ¿cómo asegurar la atomicidad o TX atómica ( atomacity or Atomic Broadcast )? La única forma de garantizar que cada miembro reciba el mensaje es pedirle que devuelva un reconocimiento al recibirlo pero ¿y si aun así falla algún host? Una solución [Birman89]: El emisor envía un mensaje a todos los miembros. Se setean timers y se reenvía el mensaje en los casos necesarios Cuando un miembro recibe el mensaje, si lo ha RX ya lo descarta. Si no, lo envía a todos los miembros del grupo (usando también Timers y retransmisiones, RTX). No importa las fallas de red o procesos , En un cierto T todos los Pi activos tendrán Mi
10 Ordenamiento de MensajesOtra propiedad deseable es la del ordenamiento de mensajes Supongamos 5 miembros. Los miembros P0,P1,P3 y P4 pertenecen a un mismo grupo En forma simultanea, los miembros P0 y P4 desean enviar un mensaje (m) al grupo. Podrían enviarlos en este orden: 1 3 1 2 3 4 4 2 5
11 Ordenamiento de Mensajes (cont.1)¿cómo reciben los mensajes los miembros 1 y 3? El miembro 1 recibe los mensajes en este orden: mensaje de 0 mensaje de 4 El miembro 3 recibe los mensajes en este orden: No se cumple el ordenamiento de mensajes! Si P0 y P4 intentan actualizar el mismo item los miembros 1 y 3 terminan con distintos valores .
12 Ordenamiento de Mensajes (cont.2)Se debe tener una semántica bien definida con respecto al orden de entrega de los Mi. “ La mejor garantía es la entrega inmediata de todos los Mi en orden en que fueron enviados “ Ese patrón de envió , Ordenamiento con respecto al tiempo Global (Global Time Ordering ). El ordenamiento no es siempre fácil de implementar Tiempo Absoluto …. , variantes moderadas : Ordenamiento Consistente (Consistent Time Ordering ). Si Ma y Mb llegan cercanos en t el sistema elige a uno como el Primero , si no lo era , nadie lo sabe .. El comportamiento no debería depender de el …. “Se garantiza que llegan en el mismo orden a todo el G, pero podría no ser con el que fueron enviados “ Se han usado otro ordenamientos mas débiles Virtual synchrony (ISIS)
13 Grupos Solapados ( Overlapping Groups)Aunque se cumpla el ordenamiento de mensajes hay situaciones problemáticas Supongamos dos grupos solapados ( G1 y G2). A y D quieren enviar a la vez un mensaje a sus compañeros de grupo: B G2 1 G1 A D 3 C 2
14 Aspecto final del diseñoESCALABILIDAD
15 Implementaciones: ISIS toolkit: es un software que corre sobre Unix y brinda un entorno de multicast ordenado para entregar los requerimientos a los AR’s Gossip: entrega los mensajes no ordenados, basándose en la propagación de updates entre AR’s
16 Group Communication in ISISSynchronous system Loosely synchronous system (loose synchrony) Virtually synchronous system (virtual synchrony) Causally related events - The nature or behavior of the second message might have been influenced in any way by the first message Concurrent events - Two events that are unrelated. What virtual synchrony means is that if two messages are causally related, all processes must receive them in the same (correct) order. However, if they are concurrent, no guarantees are made, and the system is free to deliver them in a different order to different processes if this is easier. Communication Primitives in ISIS ABCAST - basically a two-phase commit protocol for transferring data; GBCAST - same as ABCAST but this is for managing group membership; CBCAST - See Figure 2-38 and Figure 2-39
17 State of the vectors at the other machinesCBCAST in ISIS Two test are performed 1) Vj = Lj + 1 2) Vi <= Li for all i <> j Vector in a message sent by process 0 State of the vectors at the other machines 4 6 8 2 1 5 1 3 7 8 2 5 2 3 5 8 1 3 7 8 2 1 5 4 2 6 8 1 5 5 3 7 8 1 Accept Delay Accept Delay Accept
18 Sincronización en DS.
19 Sincronización (Intro)En un sistema con un procesador, la sincronización entre procesos usa herramientas como semáforos, monitores, etc. esas facilidades suponen de manera implícita la existencia de memoria compartida En los DS no contamos con esa memoria compartida, se buscaron otras técnicas El simple hecho de determinar si el evento A ocurrió antes que el evento B requiere de un cuidadoso análisis .
20 Sincronización de relojesEn un sistema centralizado, el tiempo no tiene ambigüedades ( veremos en otra clase otras ventajas de los mainframes ;-) Si el proceso A pide la hora, y un poco después el proceso B también la pide, el valor obtenido por B es siempre mayor o igual que el obtenido por A En un DS no es tan sencillo. ¿qué implica el carecer de un reloj global?
21 Sincronización de relojesPensemos en el programa make en un entorno distribuido de dos máquinas La sincronización de relojes es muy importante! 2144 2145 2146 2147 máquina que ejecuta el compilador tiempo del reloj local output.o creado 2142 2143 2144 2145 máquina que ejecuta el editor tiempo del reloj local output.c creado
22 Sincronización de relojes¿se pueden sincronizar los relojes en un sistema distribuido? Lamport demostró (1978) que sí: lo que importa no es una sincronización del tiempo absoluto, sino que el orden de los eventos sea el mismo en todas las máquinas En el ejemplo del make lo que importa no es la hora en que se crean output.o y ouput.c, sino el orden en que fueron creados Por otro lado, si dos procesos no interactuan, no es necesario que sus relojes estén sincronizados
23 Sincronización de relojesTipos de relojes: relojes lógicos: las máquinas tienen el mismo valor de reloj, aunque marquen una hora distinta de la real relojes físicos: las máquinas tienen el mismo valor de reloj, y éste no debe desvíarse de la hora real más alla de cierta magnitud
24 Sincronización de relojes lógicosLamport definió la relación “ocurre antes de” La expresión a->b se lee “a ocurre antes de b” e indica que todos los procesos coinciden en que primero ocurre a y después b se cumple: Si a y b son dos eventos en el mismo proceso y a ocurre antes que b, entonces a->b es verdadero Si a es el evento del envío de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces a->b es verdadero
25 Sincronización de relojes lógicos¿de qué forma podemos sincronizar relojes lógicos? Necesitamos una forma de asociar a cada evento a un valor de tiempo C(a) en el que todos los procesos estén de acuerdo Los valores de tiempo deben tener la propiedad de que si a->b entonces C(a)
26 Sincronización de relojes lógicosUn caso de tres procesos, cada uno con su propio reloj Con los mensajes C y D no se cumplen las reglas anteriores! 6 12 18 24 30 36 42 48 54 60 8 16 24 32 40 48 56 64 72 80 10 20 30 40 50 60 70 80 90 100 A B C D
27 Sincronización de relojes lógicosSolución propuesta por Lamport: puesto que C sale en 60 debe llegar en 61 o posterior, ... 6 12 18 24 30 36 42 48 70 76 8 16 24 32 40 48 61 69 77 85 10 20 30 40 50 60 70 80 90 100 A B C D
28 Sincronización de relojes lógicosEn ciertas situaciones existe un requisito adicional: dos eventos no ocurren exactamente al mismo tiempo Para lograr esto podemos usar el tiempo en que ocurre el evento, seguido por el número del proceso después del signo decimal P.ej. si ocurren los eventos 1 y 2 ambos en el tiempo 40, entonces el primero se convierte en 40.1 y el segundo en 40.2
29 Sincronización de relojes físicosAlgoritmo de Cristian: supongamos un conjunto de máquinas. Una de ellas tiene acceso a una fuente fiable de la hora (la llamaremos servidor de tiempo) máquina emisora servidor de tiempo T0 solicitud tiempo I, tiempo de procesamiento de la petición T1
30 Sincronización de relojes físicosPara la máquina emisora, una buena estimación de la hora sería (T1-T0)/2 Y si conocemos el valor de I: (T1-T0-I)/2 Se hacen varias medidas y se toma la media
31 Sincronización de relojes físicosAlgoritmo de Berkeley: en el algoritmo de Cristian, el servidor de tiempo es pasivo. En el UNIX de Berkeley se emplean servidores de tiempo activos El servidor de tiempo realiza un muestreo periódico de todas las máquinas para preguntarles el tiempo Con base en estas respuestas, calcula el tiempo promedio y le indica a las máquinas que avancen o retrasen su reloj la cantidad que sea necesaria
32 Sincronización de relojes físicosAlgoritmos con promedio: los dos métodos anteriores tienen la desventaja de ser centralizados. En este caso dividimos el tiempo en intervalos de resincronización El i-ésimo intervalo comienza en T0+iR y termina en T0+(i+1)R, donde T0 es un momento ya acordado en el pasado y R es una cte. Al comienzo de cada intervalo cada máquina transmite el tiempo actual de su reloj. Puesto que los relojes de las diversas máquinas ni funcionan exactamente a la misma velocidad, estas transmisiones no ocurrirán en forma simultánea Tras transmitir su hora, una máquina arranca un cronómetro local para reunir las demás transmisiones que lleguen en un cierto intervalo S A partir de ellas calcula un nuevo tiempo, p.ej. con la media
33 Sincronización de relojes físicosEjemplo de uso de relojes sincronizados: entrega de cómo máximo un mensaje El problema consiste en evitar que un servidor reciba mensajes duplicados El método tradicional es que cada mensaje tenga un nº de mensaje y que el servidor guarde los nºs de mensajes recibidos Si recibe un mensaje con un nº que ya ha visto, lo descarta Pero, ¿qué pasa si el servidor falla y pierde la tabla de los nºs recibidos?, ¿por cuánto tiempo se deben conservar los nºs de los mensajes recibidos?
34 Sincronización de relojes físicosLa solución haciendo uso del tiempo sincronizado consiste en añadir a cada mensaje una marca de tiempo Para cada conexión, el servidor registra en una tabla la marca de tiempo más reciente que haya visto Si la marca de un mensaje recibido es anterior a la guardada, el mensaje se descarta por duplicado Se pueden eliminar las marcas anteriores que sean anteriores a: G=TiempoActual-TiempoMáximodeVidadeMensaje
35 Exclusión mutua Algoritmo centralizado: La forma más directa de lograrla es similar a la forma en que se hace en un sistema uniprocesador Se elige uno de los procesos en la red como coordinador Cuando un proceso quiere entrar en una sección crítica, envía un mensaje de solicitud al proceso coordinador El coordinador decide y responde afirmativamente (OK) o negativamente (no respondiendo o con un mensaje de “permiso denegado) El coordinador tiene una cola FIFO de las peticiones, por lo que no hay inanición Problemas: el coordinador podría fallar y con él todo el sistema en sistemas grandes el coordinador es un cuello de botella
36 Exclusión mutua Algoritmo de Ricart-Agrawala: El tener un coordinador central que pueda fallar puede ser inaceptable Supongamos que todos los relojes del sistema están sincronizados (p.ej usando el algoritmo de Lamport), de forma que para cualquier par de eventos debe quedar claro cuál ocurrió primero Cuando un proceso quiere entrar en una región crítica construye un mensaje con el nombre de ésta, su número de proceso y la hora actual Envía el mensaje a todos los demás procesos
37 Exclusión mutua Cuando un proceso recibe un mensaje de solicitud de otro proceso: Si el receptor no está en la región crítica y no desea entrar en ella, envía un mensaje OK al emisor Si el receptor ya está en la región crítica, no responde, sino que guarda la solicitud en una lista Si el receptor desea entrar en la región crítica, pero no lo ha logrado todavía, compara la marca de tiempo del mensaje recibido con la marca que él usó en sus mensajes de solicitud: Si el mensaje recibido tiene marca menor, el receptor envía de regreso un mensaje OK Si no, el receptor guarda la solicitud en una lista y no envía nada
38 Exclusión mutua Nótese que cuando un proceso envía una solicitud, para poder entrar en una región crítica debe esperar a que TODOS los demás procesos le respondan con un mensaje OK Cuando sale de la región crítica envía mensajes OK a todos los procesos en su lista y la vacía
39 Exclusión mutua Ejemplo: dos procesos, 0 y 2, quieren entrar en la región crítica a la vez (Entra en R.C) 12 OK OK OK 8 8 1 2 1 2 1 2 12 OK (Entra en R.C)
40 Exclusión mutua Problemas del algoritmo:El tráfico de mensajes es mayor que en algoritmo centralizado El algoritmo centralizado tenía un único punto de fallo, pero éste tiene n puntos de fallo ! Si se pierde una respuesta el emisor quedará esperando y no podrá entrar en la sección crítica. Se puede mejorar haciendo que en vez de no responder se envíe el mensaje de “permiso denegado” Redundancia: todos los procesos participan en todas las solicitudes de entrada a una región crítica
41 Exclusión mutua Algoritmo de paso de fichas:Tenemos una red de bus (Ethernet), pero creamos por software un anillo La posición en el anillo se puede definir p.ej con el orden de las direcciones de red Al principio se le da al proceso 0 del anillo una ficha. La ficha circula por todo el anillo: el proceso k la pasa al proceso k+1 en el anillo mediante un mensaje Un proceso puede entrar en la región crítica solo cuando tenga la ficha. Al salir de la R.C pasa la ficha No se permite entrar en una segunda R.C con la misma ficha
42 Exclusión mutua El algoritmo del paso de fichas es correcto y no puede existir la inanición Problemas: Si la ficha se pierde es difícil detectar la pérdida, puesto que la cantidad de tiempo entre apariciones sucesivas de la ficha en la red no está acotada (porque un proceso puede retenerla todo el tiempo que pase en la R.C)
43 Retraso antes de entrar en RCExclusión mutua Comparación de los tres algoritmos: M= Mensajes necesarios para q un proceso entre y salga de una R.C Algoritmo M Retraso antes de entrar en RC Problema Centralizado 3 Fallo del coordinador Distribuido 2(n-1) Fallo de cualq. proceso Paso de fichas 0 a n-1 Ficha perdida
44 Elección de coordinadorMuchos algoritmos distribuidos necesitan que un proceso actúe como coordinador, iniciador, secuenciador o que desempeñe de alguna forma un papel especial En el algoritmo de exclusión mutua centralizado, por ejemplo A continuación analizaremos dos algoritmos para elección de coordinador Se suele designar como coordinador al proceso con dirección de red mayor
45 Elección de coordinadorAlgoritmo del grandullón: Un proceso P realiza una elección (cuando detecta que el coordinador ha fallado) de la siguiente manera P envía un mensaje ELECCION a los demás procesos con un número mayor Si nadie responde, P gana la elección y se convierte en el coordinador Si uno de los procesos con número mayor responde, toma el control. Envía un mensaje OK al emisor para indicar que está vivo y que tomará el control El receptor realiza entonces una elección, si no lo está haciendo ya Si un proceso que antes estaba inactivo se activa, realiza una elección. Si ocurre que es el proceso en ejecución con número máximo, se convertirá en el nuevo coordinador
46 Elección de coordinadorAlgoritmo de anillo: se forma un anillo lógico con los procesos, de forma que cada proceso conoce quién es su sucesor Cuando un proceso detecta que el coordinador no funciona, construye un mensaje ELECCION con su propio número de proceso y envía el mensaje a su sucesor. Si éste está inactivo, se lo envía al siguiente En cada paso, el emisor añade su propio nº de proceso a la lista en el mensaje En cierto momento, el mensaje regresa al proceso que lo envió. Ese proceso reconoce ese evento cuando recibe un mensaje de entrada con su propio nº de proceso En ese momento, el mensaje recibido cambia a tipo COORDINADOR y se hace circular de nuevo, para informar a los demás de quién es el nuevo coordinador (el miembro de la lista con el nº máximo)
47 Transacciones atómicasNecesitamos una operación de mayor nivel, de mayor capacidad Tal abstracción existe y se utiliza mucho en sistemas distribuidos: la transacción atómica Supongamos que queremos viajar de Las Palmas a Bata (ciudad de Guinea Ecuatorial) Iremos a la agencia de viajes para intentar reservar un billete a Madrid. Lo conseguimos Luego intentaremos reservar un billete de Madrid a Malabo, (en fecha posterior al del primer viaje, naturalmente). Lo conseguimos Intentamos ahora buscar un vuelo de Malabo a Bata. Pero resulta que no hay disponibles En ese caso deberíamos ser capaces de deshacer lo hecho, las dos reservas anteriores O SE HACE TODO O NO SE HACE NADA
48 Transacciones atómicasEjemplo en el ámbito informático: supongamos un banco al que podemos conectarnos por Internet, con la intención de retirar dinero de nuestra cuenta para transferirlo a otra: Retirar(cantidad, cuenta1) Ingresar(cantidad, cuenta) Si la conexión telefónica falla después de la primera operación pero antes de la segunda ? El problema debe resolverse haciendo que ambas acciones constituyan una transacción atómica: o se hacen ambas o no se hace ninguna
49 Transacciones atómicasPodemos tener tres tipos de almacenamiento: Memoria RAM: se borra al fallar la energía o en un fallo de la máquina Disco: sobrevive a fallos anteriores pero podría fallar la cabeza lectora del disco Almacenamiento estable: diseñado para sobrevivir a todo (excepto tal vez a un 11-S) El almacenamiento estable se puede lograr con un par de discos Cuando se quiere escribir se escribe primero en el disco 1 y luego en el disco 2 Si el sistema falla tras escribir en la unidad 1, tras recuperar podemos comprobar que ambos discos son inconsistentes. Hacemos entonces que el 2 copie lo distinto en el 1, pues el 1 es siempre el que se modifica primero Cuando se detecte error (p.ej. por CRC) en un sector de uno de los discos, se repara con la información del otro
50 Transacciones atómicasTrabajaremos con estas primitivas de transacción: BEGIN_TRANSACTION END_TRANSACTION ABORT_TRANSACTION En medio de una transacción se podrán realizar diversas operaciones, según la aplicación Las transacciones deberán ser todo o nada y además deben ejecutarse en exclusión mutua unas con otras
51 Transacciones atómicas¿cómo implementar las transacciones atómicas? espacio de trabajo privado: consiste en mantener una copia de los objetos o memoria que se quiera modificar Por ejemplo, si la transacción implica acceso a un directorio particular, mantenemos una copia Intentamos llevar a cabo la transacción en la copia Si nada falla al final modificamos el original Si no, descartamos la copia
52 Transacciones atómicasOtra forma de implementarlas es la bitácora La bitácora es una lista de los cambios que se van realizando sobre cada objeto implicado en la transacción En la lista se incluye el estado anterior y posterior del objeto x=0; y=0; BEGIN_TRANSACTION x=x+1; y=y+2; x=y*y; END_TRANSACTION Podemos hacer los cambios en los objetos reales, pues con la bitácora tenemos información para deshacer: partimos del final hacia atrás La bitácora se almacenaría en almacenamiento estable x=0/1 Bitácora y=0/2 x=1/4
53 Transacciones atómicasProtocolo de compromiso de dos fases: Uno de los procesos actúa como coordinador El coordinador envia un mensaje de preparado a los demás procesos Y recibe mensajes de los otros procesos indicando si están dispuestos a comprometerse Cuando el coordinador ha recibido todas las respuestas decide si se lleva a cabo la transacción o no Si uno o más procesos no se comprometen (o no responden) la transaccion se aborta Si el coordinador decide que se lleva a cabo la transacción, envía un mensaje notificándolo a los demás procesos
54 Control de concurrenciaUn algoritmo para control de concurrencia en SS.DD se basa en el uso de la cerradura P.ej. al acceder a un archivo, se activa una cerradura de acceso La cerradura puede ser de lectura/escritura La cerradura puede ser a todo el fichero o a ciertos registros (granularidad de la cerradura) La cerradura más usada es la de dos fases: primero se va intentando adquirir todas las cerraduras necesarias, y solo entonces se accede Si no se pudiera acceder a una de las cerraduras, se liberan las ya obtenidas
55 Control de concurrenciaOtra opción es el control optimista de la concurrencia La idea es no hacer nada Se supone que van a producirse pocos conflictos, en la práctica los conflictos son raros, por lo que suele funcionar bien Pero hay que detectar los conflictos. Si se producen hay que deshacer lo hecho
56 Control de concurrenciaOtro método se basa en las marcas de tiempo Se asocia a cada inicio de transacción (BEGIN_TRANSACTION) una marca de tiempo Cuando las transacciones son breves y espaciadas en el tiempo entonces no habrá problema A veces el orden es incorrecto (se detecta que una transición iniciada posteriormente a la transacción activa ha intentado entrar en el archivo, tenido acceso a éste y ha realizado un compromiso) En ese caso la transición activa se aborta
57 Bloqueos en SS.DD Los bloqueos en los ss.dd. son similares a los que ocurren en un sistema uniprocesador Pero son más difíciles de detectar y corregir Aproximaciones posibles: El algoritmo del avestruz (ignorar el problema) Detección (permitir que ocurran bloqueos, detectarlos e intentar recuperarse) Prevención (imponer restricciones para que podamos asegurar que no se van a dar bloqueos) Evitarlos (que los procesos hagan una cuidadosa asignación de recursos para que no se den bloqueos) Estudiaremos a continuación solo la detección y la prevención
58 Bloqueos en SS.DD detección centralizada de bloqueos:cada máquina mantiene su gráfica de recursos y procesos Un coordinador recibe (mediante mensajes) esa información. Con la visión global, toma las decisiones Cuando el coordinado detecta un ciclo, elimina los procesos para romper el bloqueo
59 Bloqueos en SS.DD detección distribuida de bloqueos (algoritmo de Chandy-Misra-Haas): Cuando un proceso debe esperar por un recurso, construye un mensaje especial de exploración, que envía al proceso o procesos que retienen el recurso El mensaje consta de tres números: el proceso que espera, el proceso que envía el mensaje y el proceso al cual se envía Al llegar el mensaje, el receptor comprueba si él también espera a algunos procesos. En ese caso el mensaje se actualiza, conservando el primer campo pero pero reemplazando el segundo por su propio número de proceso y el tercero por el nº del proceso al cual espera El mensaje se reenvía entonces al proceso por el cual espera Si un mensaje regresa al emisor original (el proceso enumerado en el primer campo) es que hay un ciclo y el sistema está bloqueado
60 Bloqueos en SS.DD Ejemplo: 1 1 1 2 2 2 (0,8,0) (0,4,6) (0,2,3) (0,5,7)(0,2,3) 1 2 (0,5,7) 2 2 Máquina 0 Máquina 2 Máquina 1
61 Bloqueos en SS.DD Prevención distribuida de bloqueos:Suponemos que existe un s.d. con tiempo global y transacciones atómicas Asociamos a cada transacción una marca de tiempo global al momento de su inicio Cuando un proceso está a punto de bloquearse en espera de un recurso que está usando otro proceso, se comprueba cuál de ellos tiene la marca de tiempo mayor Si el proceso que tiene el quiere el recurso es más joven podemos entonces optar por hacerlo esperar
62 Replication Outline Failure Models Mirroring Quorums
63 Why Replicate? Performance Survive Failureskeep copy close to remote users caching is a special case Survive Failures availability: provide service during temporary failure fault tolerance: provide service despite catastrophic failure
64 Fault Models Crashed Fail-Stop Byzantinefailed device doesn’t do anything (i.e., fails silently) Fail-Stop failed device tells you that it has failed Byzantine failed device can do anything adversary playing a game against an evil opponent opponent knows what you’re doing and tries to fool you usually some limit on opponent’s actions (e.g. at most k failures)
65 Byzantine Army Problem3000 Blue Soldiers 3000 Blue Soldiers 4000 Red Soldiers
66 Synchrony Assumptions concerning boundedness of component execution or network transmissions Synchronous always performs function in a finite & known time bound Asynchronous no such bound Famous Result: A group of processes cannot agree on a value in an asynchronous system given a single crash failure
67 Network Partitions Can’t tell the difference between a crashed process and a process that’s inaccessible due to a network failure. Network Partition: network failure that cuts processes into two or more groups full communication within each group no communication between groups danger: each group thinks everyone else is dead
68 Mirroring Goal: service up to K failuresApproach: keep K+1 copies of everything Clients do operations on “primary” copy Primary makes sure other copies do operations too Advantage: simple Disadvantages: do every operation K times use K times more storage than necessary
69 Mirroring Details Optimization: contact one replica to readWhat if a replica fails? get up-to-date data from primary after recovering What if primary fails? elect a new primary
70 Election Problem When algorithm terminates, all non-failed processes agree on which replica is the primary Algorithm works despite arbitrary failures and recoveries during the election If there are no more failures and recoveries, the algorithm must eventually terminate
71 Bully Algorithm Use fixed “pecking order” among processese.g., use network addresses Idea: choose the “biggest” non-failed machine as primary Correctness proof is difficult
72 Bully Algorithm DetailsProcess starts an election whenever it recovers or whenever primary has failed how know primary has failed? To start an election, send election messages to all machines bigger than yourself if somebody responds with an ACK, give up if nobody ACKs, declare yourself the primary On receiving election message, reply with ACK and start an election yourself (unless in progress)
73 Quorums Quorum: a set of server machinesDefine what constitutes a “read quorum” and a “write quorum” To write acquire locks on all members of some write quorum do writes on all locked servers release locks To read: similar, but use read quorum
74 Quorums Correctness requirements Locking ensures thatany two write quorums must share a member any read quorum and any write quorum must share a member (read quorums need not overlap) Locking ensures that at most one write happening at a time never have a write and a read happening at the same time
75 Defining Quorums Many alternatives Example Consequencewrite quorum must contain all replicas read quorum may contain any one replica Consequence writes are slow, reads are fast can write only if all replicas are available can read if any one replica is available
76 Defining Quorums (cont)Example: Majority Quorum write quorum: any set with more than half the replicas read quorum: any set with more than half the replicas Consequences modest performance for read and write can proceed as long as more than half the replicas are available
77 Quorums & Version NumbersWrite operation writes only a subset of the servers some servers are out-of-date Remedy put version number stamp on each item in each replica when acquiring locks, get current version number from each replica quorum overlap rules ensure that one member of your quorum has the latest version
78 Version Numbers (cont)When reading, get the data from the latest version number in your quorum When writing, set version number of all replicas you wrote equal to 1 + (max version number in your quorum beforehand) Guarantees correctness even if no recovery action is taken when replica recovers from a crash
79 Quorums and PartitionsOne group has a write quorum (and thus usually a read quorum); that group can do anything other groups are frozen No group has a write quorum, but some groups have a read quorum some groups can read no groups can write No group contains any quorum everyone is frozen
80 Tolerancia a fallos
81 Tolerancia a fallos Un sistema falla cuando no cumple su especificación Los fallos de un sistema pueden estar en un fallo en algún componente. Los fallos de componentes pueden ser: fallos transitorios: una erupción solar que inutiliza un momento un satélite?? fallos intermitentes: mal contacto en un cable,... fallos permanentes: circuito quemado, error software,...
82 Tolerancia a fallos Los fallos del sistema pueden ser:fallos silenciosos: el sistema deja de funcionar o se puede detectar que el sistema ha dejado de funcionar correctamente fallos bizantinos: no se detecta, el sistema sigue funcionando pero produce resultados incorrectos Desde el punto de vista de la t.a.f, los sistemas pueden ser: síncronos: si se puede asegurar que el sistema responde a un mensaje dentro de un tiempo finito conocido asíncronos: si no Los sistemas más problemáticos son pues los que tienen fallos bizantinos y los que son asíncronos
83 Tolerancia a fallos El método más usado en tolerancia a fallos es el empleo de redundancia La redundancia puede ser: de información: p.ej. añadiendo bits con código de Hamming que permita recuperar errores de tiempo: se realiza una acción, y en caso necesario, se repite en el tiempo. P.ej. la transacción atómica. La redundancia en el tiempo es muy útil en fallos intermitentes y transitorios física: se agregan equipos o procesadores adicionales. Se puede hacer de dos formas: réplica activa respaldo primario
84 Tolerancia a fallos Tolerancia a fallos mediante réplica activa: todos los procesadores se usan todo el tiempo como servidores, funcionando en paralelo, ocultando los fallos La réplica activa se utiliza en: biología: los mamíferos tenemos dos ojos, oídos, etc. aviación: los 747 tienen 4 motores pero pueden volar con 3 deporte: varios árbitros Se dice que un sistema es tolerante a k fallos si puede superar fallos en k componentes y seguir cumpliendo sus especificaciones
85 Tolerancia a fallos Si los componentes fallan de manera silenciosa, bastan k+1 de ellos para proporcionar la tolerancia a k fallos Si los componentes tienen fallos bizantinos, continuan su ejecución al fallar y dan respuestas aleatorias o erróneas, por lo que se necesitan al menos 2k+1 componentes para lograr la tolerancia a k fallos
86 Tolerancia a fallos Tolerancia a fallos mediante respaldo primario: en todo instante es un servidor primario el que realiza todo el trabajo. Si el primario falla, el de respaldo comienza a funcionar, todo ello de forma transparente a los programas de aplicación De este esquema también hay numerosos ejemplos en la vida real: gobierno: ej. vicepresidente aviación: ej. copilotos generadores diesel en los hospitales Ventaja con respecto a la réplica activa: la operación normal es más sencilla, funciona solo un servidor en vez de varios en paralelo Desventaja: trabaja mal en presencia de fallos bizantinos, en los que el primario afirma erróneamente que funciona de manera perfecta
87 Tolerancia a fallos Acuerdos en sistemas defectuosos: en ss.dd. es muy importante lograr acuerdos sobre algo (elección de coordinador, si completar una transacción o no). ¿cómo llegar a acuerdos cuando hay fallos? Supongamos que tenemos procesadores perfectos pero una línea de comunicación que puede fallar Ese caso podemos estudiarlo teóricamente con el problema de los dos ejércitos
88 Tolerancia a fallos Problema de los dos ejércitos:El ejército rojo tiene 5000 soldados, acampados en un valle Dos ejércitos azules, cada uno con 3000 efectivos, acampan en las colinas circundantes al valle Si los dos ejércitos azules logran llegar a un acuerdo de ataque simultáneo, derrotarán al ejército rojo Si solo lo intenta uno de los ejércitos azules, saldrá derrotado Supongamos que el comandante del ejército 1 envía un mensaje al comandante del ejército 2. El mensaje dice “Tengo un plan, ataquemos mañana al amanecer” El mensajero logra pasar, y el comandante del ejército 2 le devuelve una nota que dice “Espléndido, ataquemos pues mañana al amanecer” El mensajero regresa a salvo y el comandante 1 prepara entonces a sus tropas
89 Tolerancia a fallos Pero más tarde el comandante 1 se pone a pensar y se da cuenta de que el comandante 2 no sabe si el mensajeró regresó a salvo, y al dudar podría no atreverse a atacar Así que el comandante 1 vuelve a enviar un mensaje Ocurre lo mismo No importa el nº de reconocimientos enviados, el comandante 1 y el comandante 2 nunca llegarán a un acuerdo => Incluso si los procesadores no fallan (comandantes), el acuerdo entre dos procesos no es posible si existe una comunicación no confiable
90 Tolerancia a fallos Supongamos ahora que la comunicación es perfecta pero los procesadores no lo son Ese caso podemos estudiarlo teóricamente con el problema de los generales bizantinos El ejército rojo sigue acampando en el valle, pero n generales azules comandan ejércitos en las colinas cercanas La comunicación es perfecta (p.ej línea telefónica), pero m de los n generales son traidores (fallan). Dan información incorrecta o contradictoria Ahora supongamos que cada general conoce el nº de soldados de que dispone. Definiremos el acuerdo como sigue: los generales intercambian la información del nº de soldados que tienen. Al final del algoritmo cada general debe tener un vector de longitud n. Si el general i es leal, entonces el elemento i es su cantidad de efectivos; en caso contrario está indefinido
91 Tolerancia a fallos Lamport y colaboradores diseñaron un algoritmo recursivo que resuelve este problema bajo ciertas condiciones Veamos cómo funciona para n=4 y m=1 (tres generales leales y uno traidor). Con estos parámetros el algoritmo opera en 4 pasos En el paso uno, cada general envía un mensaje a los demás con la información de sus tropas Los generales leales dicen la verdad, mientras que el traidor puede decir a cada uno de los demás una mentira diferente. Sea el general 3 el traidor. Informan así: general 1: 1 Ksoldados general 2: 2 Ksoldados general 3: x,y,z Ksoldados general 4: 4 Ksoldados
92 Tolerancia a fallos En el paso 2, los resultados recibidos de los otros se reunen en forma de vectores: 1. (1,2,x,4) 2. (1,2,y,4) 3. (1,2,3,4) 4. (1,2,z,4) En el paso 3, cada general pasa su vector a los demás En este paso el general 3 vuelve a mentir, ideando 12 nuevos valores a-l: gral.1 gral gral.4 (1,2,y,4) (1,2,x,4) (1,2,x,4) (a,b,c,d) (e,f,g,h) (1,2,y,4) (1,2,z,4) (1,2,z,4) (i,j,k,l)
93 Tolerancia a fallos Por último, en el paso 4 cada general examina su i-ésimo elemento de cada uno de los vectores que ha recibido Si cualquier valor tiene una mayoría, este valor se coloca en el vector resultado. Si ningún valor tiene mayoría, el elemento correspondiente del vector resultado se marca como INCOGNITA Vemos que en este caso obtenemos como vector resultado: (1,2,INCOGNITA,4) => El general 3 es un traidor!
94 Tolerancia a fallos Lamport y colaboradores demostraron que en un sistema con m procesadores que pueden fallar, el acuerdo solo se logra si se dispone de 2m+1 procesadores que funcionen de manera correcta Si por ejemplo hubiésemos tenido n=3 y m=1 (dos generales leales y un traidor) no hubiésemos podido llegar a un acuerdo