Comunicación en Grupos
1
Bibliografía



Sistemas Operativos Distribuidos
 A. 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 1988. Sape J. Mullender, ed.,
Addison-Wesley/ACM Press Series (1989).
2
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]

3
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.”
Comunicación en grupo




La comunicación es entre un grupo de procesos
Cuando 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
5
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 )
6
Aspectos de diseño: Membresía



un 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 ?
7
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-ornothing )
 La atomicidad es una propiedad deseable (
facilita la programación de los Sistemas
Distribuidos )

8
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
9
Ordenamiento de Mensajes



Otra 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
0
0
1
2
3
4
3
4
2
10
5
Ordenamiento de Mensajes (cont.1)


¿cómo reciben los mensajes los miembros 1 y 3?
El miembro 1 recibe los mensajes en este orden:



El miembro 3 recibe los mensajes en este orden:




mensaje de 0
mensaje de 4
mensaje de 4
mensaje de 0
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 .
11
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 ).



Ordenamiento Consistente (Consistent Time Ordering ).




El ordenamiento no es siempre fácil de implementar
Tiempo Absoluto …. , variantes moderadas :
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)
12
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:
0
G1
B
1
A
G2
D
3
C
2
13
Aspecto final del diseño

ESCALABILIDAD
14
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

15
Group Communication in ISIS




Synchronous 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
CBCAST 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
0
4
6
8
2
1
5
State of the vectors at the other machines
1
3
7
8
2
1
5
2
3
5
8
2
1
5
3
3
7
8
2
1
5
4
2
6
8
2
1
5
5
3
7
8
3
1
5
Accept
Delay
Accept
Delay
Accept
Sincronización en DS.
18
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 .
19
Sincronización de relojes
En 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?

20
Sincronización de relojes

Pensemos en el programa make en un entorno
distribuido de dos máquinas
máquina que
ejecuta el compilador
2144
2145
2146
2147
2143
2144
2145
tiempo del
reloj local
output.o creado
máquina que
ejecuta el editor
2142
output.c creado

tiempo del
reloj local
La sincronización de relojes es muy importante!
21
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
22
Sincronización de relojes

Tipos 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
23
Sincronización de relojes lógicos
Lamport 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 24
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)<C(b)
 El tiempo de reloj C siempre debe ir hacia
delante, nunca puede ser decreciente

25
Sincronización de relojes lógicos

Un caso de tres procesos, cada uno con su propio reloj
0
0
0
8
10
1
2
1
6
20
1
8
2
4
2
4
3
2
3
0
4
0
6
reglas3
A
D
6
4
8
4
2
5
6
4
6
B
30
40
50
C
60
70
80
Con los mensajes C y D
no se cumplen las
anteriores!
90
10
0
26
Sincronización de relojes lógicos

Solución propuesta por Lamport: puesto que C
sale en 60 debe llegar en 61 o posterior, ...
0
0
0
8
10
1
2
1
6
20
1
8
2
4
2
4
3
2
3
0
4
0
6
3
6
4
2
A
D
4
8
6
1
B
30
40
50
C
60
70
80
90
10
0
27
Sincronización de relojes lógicos
En 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

28
Sincronización de relojes físicos

Algoritmo 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
tiempo
I, tiempo de procesamiento de
la petición
T1
29
Sincronización de relojes físicos

Para 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
30
Sincronización de relojes físicos



Algoritmo 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
31
Sincronización de relojes físicos





Algoritmos 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
32
Sincronización de relojes físicos





Ejemplo 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?
33
Sincronización de relojes físicos
La 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

34
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
35
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
36
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
37
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

38
Exclusión mutua

Ejemplo: dos procesos, 0 y 2, quieren
entrar en la región crítica a la vez
(Entra en R.C)
0
8
1
0
8
12
12
2
OK
OK
1
0
OK
2
OK
1
2
(Entra en R.C)
39
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
40
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
41
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)
42
Exclusión mutua

Comparación de los tres algoritmos:
Algoritmo
M
Retraso antes de
entrar en RC
Centralizado
3
3
2(n-1)
2(n-1)
Distribuido
Problema
Fallo del
coordinador
Fallo de
cualq.
proceso
Paso de
0 a n-1
0 a n-1
Ficha
perdida
M=fichas
Mensajes necesarios para q un proceso entre
y salga de
una R.C
43
Elección de coordinador




Muchos 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
44
Elección de coordinador






Algoritmo 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
45
Elección de coordinador





Algoritmo 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
46
de la lista con el nº máximo)
Transacciones atómicas








Necesitamos 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
47
Transacciones atómicas

Ejemplo 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
48
Transacciones atómicas

Podemos 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 49
uno de los discos, se repara con la información del otro
Transacciones atómicas

Trabajaremos 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
50
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
51
Transacciones atómicas



Otra 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


Bitácora
x=0/1
Bitácora
x=0/1
Bitácora
x=0/1
y=0/2
y=0/2
x=1/4
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
52
Transacciones atómicas







Protocolo 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
53
Control de concurrencia






Un 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
54
Control de concurrencia
Otra 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

55
Control de concurrencia





Otro 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
56
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
57
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

58
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
59
Si un mensaje regresa al emisor original (el proceso
enumerado en el primer campo) es que hay un ciclo y el
Bloqueos en SS.DD

Ejemplo:
(0,8,0)
0
1
Máquina 0
2
(0,2,3)
0
1
2
Máquina 1
(0,4,6)
(0,5,7)
1
0
2
Máquina 2
60
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
61
Replication
Outline
Failure Models
Mirroring
Quorums
62
Why Replicate?

Performance



keep 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
63
Fault Models

Crashed


Fail-Stop


failed device doesn’t do anything (i.e., fails
silently)
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
64
most k failures)
Byzantine Army Problem
3000
Blue
Soldiers
3000
Blue
Soldiers
4000
Red
Soldiers
65
Synchrony

Assumptions concerning boundedness of
component execution or network
transmissions

Synchronous


Asynchronous


always performs function in a finite & known
time bound
no such bound
Famous Result: A group of processes
cannot agree on a value in an
asynchronous system given a single crash
failure
66
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
67
Mirroring
Goal: service up to K failures
 Approach: 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
68
Mirroring Details

Optimization: contact one replica to read

What if a replica fails?


get up-to-date data from primary after
recovering
What if primary fails?

elect a new primary
69
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
70
Bully Algorithm

Use fixed “pecking order” among
processes

e.g., use network addresses

Idea: choose the “biggest” non-failed
machine as primary

Correctness proof is difficult
71
Bully Algorithm Details

Process starts an election whenever it
recovers or whenever primary has failed


To start an election, send election
messages to all machines bigger than
yourself



how know primary has failed?
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
72
Quorums

Quorum: a set of server machines

Define 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
73
Quorums

Correctness requirements



any 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
74
Defining Quorums
Many alternatives
 Example




write 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
75
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
76
Quorums & Version Numbers

Write 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
77
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
78
Quorums and Partitions

One group has a write quorum (and thus
usually a read quorum);



No group has a write quorum, but some
groups have a read quorum



that group can do anything
other groups are frozen
some groups can read
no groups can write
No group contains any quorum

everyone is frozen
79
Tolerancia a fallos
80
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,...
81
Tolerancia a fallos

Los fallos del sistema pueden ser:



Desde el punto de vista de la t.a.f, los sistemas
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
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
82
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
83
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
84
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

85
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
86
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

87
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
88
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
89
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 caso90
contrario está indefinido
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
general
general
general
1:
2:
3:
4:
1 Ksoldados
2 Ksoldados
x,y,z Ksoldados
4 Ksoldados
91
Tolerancia a fallos

En el paso 2, los resultados recibidos de los otros se reunen en
forma de vectores:
1.
2.
3.
4.


(1,2,x,4)
(1,2,y,4)
(1,2,3,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.2
(1,2,y,4)
(a,b,c,d)
(1,2,z,4)
(1,2,x,4)
(e,f,g,h)
(1,2,z,4)
gral.4
(1,2,x,4)
(1,2,y,4)
(i,j,k,l)
92
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!
93
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

94
Descargar

Objetivos