Coordinacion

Índice

Coordinación

Página
Pantalla
Imprimir

Joaquín Seoane Pascual

Cerrar

joaquin@dit.upm.es

Salir

Departamento de Ingeniería de Sistemas Telemáticos
Universidad Politécnica de Madrid
23 de octubre de 2007

Coordinación
23 de octubre
de 2007
Página:
1 de 25

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Página
Pantalla
Imprimir

Índice

Cerrar
Salir

Coordinacióndistribuida

3

Exclusión mutua

4

Robustez

13

Coordinación
23 de octubre
de 2007
Página:
2 de 25

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Coordinación distribuida

Página
Pantalla

Algoritmos para llegar a acuerdos (Capítulo 12)

Imprimir
Cerrar

Exclusión mutua.

Salir

Elección de coordinador.
Multienvíos.
Consenso y acuerdo con fallos bizantinos.

Coordinación23 de octubre
de 2007
Página:
3 de 25

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Exclusión mutua
Sólo un proceso accede al recurso a al vez
Página

Solución trivial:

Pantalla

Si el recurso está en una máquina, utilizarlo llamando a un procedimiento remoto, con un servidor monoproceso.

Imprimir
Cerrar
Salir

Coordinación
23 de octubre
de 2007
Página:
4 de 25

•First•Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Observaciones sobre el procedimiento remoto
El servicio puede existir sin exclusión:
−→ hay que añadir servicio de exclusión.

Página
Pantalla
Imprimir
Cerrar
Salir

El recurso puede estar distribuido:

• Espacio radioeléctrico.
• Taller con varias entradas.

Coordinación
23 de octubre
de 2007
Página:
5 de 25

•First •Prev •Next •Last •GoBack •Full Screen •Close •Quit

Índice

Exclusión mutua centralizada
1
2

ón
Petici

c

1

e
Respu

sta

c

2

2

3

1

2

3

ón
ici

t
Pe

c

Pantalla

2

3

Página

Imprimir
Cerrar

Se pide el recurso, que nadie
usa.

1

c

2
3

Se concede, anotando al deman- Peticiones posteriores se retradante en una cola.
san.

1
2

c

3

1
2

2 3

23

No se responden, pero se encolan.

ón

aci
Liber

3Salir

c

a
est

u

sp
Re

3

La liberación elimina el proceso Y se concede a quen lleve más
de la cola.
tiempo esperando.
Coordinación
23 de octubre
de 2007
Página:
6 de 25

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Análisis de la exclusión mutua centralizada
Corrección: Sólo un proceso está a la vez en la región crítica.

Página
Pantalla
Imprimir
Cerrar

Viveza: Todoproceso obtiene su región crítica
(si los otros se comportan bien).

Salir

Ecuanimidad: Las peticiones se sirve en orden FIFO.
Complejidad: Tres mensajes fiables por petición.

Coordinación
23 de octubre
de 2007
Página:
7 de 25

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Índice

Vulnerabilidad de la exclusión mutua centralizada
La caída del coordinador bloquea al sistema.

PáginaPantalla

• Detección: ¿estás ahí?
• Elección de otro.
• Recuperación: preguntando a todos los procesos para reconstruir el es-

Imprimir
Cerrar
Salir

tado del coordinador.
La caída de un proceso en la región crítica bloquea al sistema.

• Vigilancia.
• Liberación automática de recurso pasado un tiempo.
Coordinación
23 de octubre
de 2007
Página:
8 de 25

•First •Prev •Next •Last •Go Back •FullScreen •Close •Quit

Índice

Exclusión en anillos
El testigo se pasa, a menos que
se quiera entrar en la región
crítica, en cuyo caso se retiene
el tiempo necesario.

1
5

Página
Pantalla
Imprimir
Cerrar
Salir

2

Complejidad:

• 1 − ∞ mensajes por
testigo

4

petición.
Vulnerabilidad:

3

• Pérdida de testigo.
• Caída de procesador.
Coordinación
23 de octubre
de 2007
Página:
9 de 25

•First •Prev•Next •Last •Go Back •Full Screen •Close •Quit

Índice

Exclusión distribuida de Ricart-Agrawala
Todo proceso pide y concede regiones.
Debe escuchar incluso en situación de bloqueo.
Página

Las peticiones se hacen a todos.

Pantalla

Un proceso, entra en la región cuando recibe respuestas de todos.

Imprimir
Cerrar

Un proceso, no responde a peticiones cuando está en la región crítica....