Sistemas Distribuidos
Tema: Exclusión Mutua
Edgar Adrian Esquivel Mendiola
CINVESTAV, Tamaulipas
Problema de Exclusión Mutua
 Acceso exclusivo a algun recurso compartido en una
red de procesos.
 Posibles soluciones
 Shared Memory
 Message-passing
 Ejemplos:
 Impresión de documentos.
 Manejo de archivos compartidos.
 CSMA/CD usado para conexiones en Ethernets.
Sistemas Distribuidos
Solución usando paso de mensajes
2 1
Algoritmos descentralizados
4
P4
petición
2 1
4
P2
petición
Controlados por coordinador
P1
P3
P
1
P
2
2 1
2 1
petición
respuesta
Cola de peticiones
Coordinador
2
respuesta
liberación
P
3
Sistemas
Distribuidos
P
4
respuesta
P
5
1
4
4
4
El problema consiste en diseñar un protocolo que
satisfaga las siguientes condiciones:
 ME1. [Mutual exclusion] A lo más un proceso puede
permanecer en su CS(sección critica) en
momento. Esta es una propiedad de seguridad.
cualquier
 ME2.
[Freedom
from
deadlock]
En
todas
las
configuraciones, por lo menos un proceso debe ser elegible
para tomar una acción y entrar en su sección crítica. Esta
es también una propiedad de seguridad.
 ME3. [Progress] Cada proceso tratando de entrar en su CS
debe eventualmente triunfar. Esta es una propiedad de
vivacidad.
Sistemas Distribuidos
LAMPORT

LA1. Para solicitar la entrada a la CS (sección crítica), un proceso envía un mensaje de
solicitud con una marca de tiempo a cada uno de los procesos en el sistema e introduce
la petición en su cola Q local.

LA2. Cuando un proceso recibe una petición, la coloca en su Q. Si el proceso no esta
en la sección critica, entonces envía un acuse de recibido con una marca de tiempo al
emisor . En otro caso, aplaza el envió del acuse de recibido hasta que sale de la sección
crítica.

LA3. Un proceso entra en la sección crítica cuando:

(i) su petición esta ordenada adelante de las otras peticiones(i.ela marca de tiempo de
su propia petición es menor que la marca de tiempo de los otros procesos) en su cola
local, y

(ii) ha recibido el acuse de los demás procesos en respuesta de su petición actual.

LA4. Para salir de la CS un, proceso(i) elimina la petición de su cola local, y(ii) envía un
mensaje de liberación a los demás procesos.

LA5. Cuando un proceso recibe un mensaje de liberación, remueve la correspondiente
petición de su cola.
Sistemas Distribuidos
Características del Mensaje
 El cuerpo del msg (mensaje) se compone de 3
campos:
 Emisor: quien envía el mensaje.
 Tipo: petición | liberación | acuse.
 Ts (timeStamp): marca de tiempo asignada por el
emisor.
Sistemas Distribuidos
Ejemplo LAMPORT
1 4
Petición
P1
1 4
Petición
Petición
P2
P3
P4
Petición
Sistemas Distribuidos
1 4
1 4
RICART–AGRAWALA
 RA1. Cada proceso que busca entrar a la region critica, envia un
mensaje de peticion con marca de tiempo a los demas procesos en el
sistema.
 RA2. Cuando un proceso recibe una petición envía un acuse de
recibido al emisor, solo cuando(i) el proceso no esta interesado en
entrar a la sección critica, o(ii) el proceso esta intentando a la CS,
pero su marca de tiempo es mas grande que la del emisor. Si el
proceso se encuentra en la CS, entonces almacenara todas las
peticiones hasta su salida de la CS.
 RA3. Un proceso entra en la CS, cuando recibe un acuse de las
restantes n−1 procesos.
 RA4. Una vez que sale de la SC, un proceso debe enviar un acuse a
cada una de las pendientes peticiones antes de hacer una nueva
petición o ejecutar otras acciones.
Sistemas Distribuidos
Solución de RICART–AGRAWALA
CS
P1
respuesta
respuesta
P2
respuesta
CS
Queue
(ts:2, P2)
Sistemas Distribuidos
P3
MAEKAWA
 MA1. Para entrar a la sección critica, un proceso i primero envía un mensaje
de petición con marca de tiempo a cada proceso de Si.
 MA2.Un proceso (fuera de la sección critica) que recibe peticiones envía un
acuse de recibido al proceso del cual su petición tiene la marca de tiempo
mas baja. Se bloquea a si mismo para otros procesos y mantiene todas las
demás peticiones en esperando en la cola de peticiones. Si el nodo que
recibió se encuentra en la sección critica, entonces el acuse de recibido es
aplazado.
 MA3. Un proceso entra en CS cuando recibe acuse de todos los demás
procesos de Si.
 MA4. Durante la salida de CS, el proceso envía un mensaje de liberación a
los demás procesos de Si.
 MA5. Una vez recibido un mensaje de liberación del proceso i, el proceso se
desbloquea a si mismo, elimina la petición actual , y envía un acuse de
recibido a el proceso que tiene la marca de tiempo mas baja.
Sistemas Distribuidos
Solución de MAEKAWA
Sistemas Distribuidos
Solución de MAEKAWA
 Por ejemplo, G(a) = {b, d, e}; G(c) = {a, b, f}; G(g) = {c, d, f}
 Digamos que a, c, g hacen peticiones simultaneas
 El sitio b responde positivamente a a
 El sitio b encola la respuesta al sitio c hasta que obtiene una
respuesta de a, pero podría enviar respuestas positivas al sitio a
 Mientras que el sitio f responde positivamente a el sitio g, pero
debe encolar la respuesta para el sitio c.
 Eventualmente, el sitio a enviara una respuesta a los nodos de su
subconjunto, y el sitio b entonces respondera positivamente al
sitio c.
Sistemas Distribuidos
TOKEN PASSING ALGORITHMS
 Solo el proceso que tiene el token
puede entrar a la sección critica.
 Para entrar a la sección critica, se
espera pasivamente el token.
Cuando esta en la sección critica,
mantiene el token.
Token
 Para salir de la CS, el proceso
envía el token al vecino.
 Si un proceso no necesita entrar a
la sección critica cuando recibe el
token, lo pasa a el siguiente
proceso.
Sistemas Distribuidos
SUZUKI–KASAMI ALGORITHM
 Se asume que inicialmente un proceso arbitrario posee
el token. Un proceso i que no tiene el token pero quiere
entrar a la CS , transmite una petición (i, num), donde
num es el numero de secuencia de la petición. El
algoritmo garantiza que eventualmente cada proceso i
recibe el token.
 Cada proceso i mantiene un arreglo req[0,…, n-1] de
enteros, donde req[j] designa el numero de secuencia
de la ultima petición recibida del proceso j.
Sistemas Distribuidos
req[1,0,0,0,0]
req[1,0,0,0,0]
req[1,1,1,0,0]
P
2
P1
Last[0,0,0,0,0]
req[1,1,1,0,0]
P1
P
2
p4
p3
Last[0,0,0,0,0]
req[1,0,0,0,0]
p4
p3
req[1,1,1,0,0]
req[1,1,1,0,0]
req[1,0,0,0,0]
p5
req[1,1,1,0,0]
req[1,1,1,0,0]
P
2
Last[1,0,0,0,0]
Q(2,3)
req[1,1,1,0,0]
Proceso p2 y p3 envía petición
Proceso p1 envía petición
P1
p5
req[1,0,0,0,0]
req[1,1,1,0,0]
req[1,1,1,0,0]
P
2
P1
Last[1,0,0,0,0]
Q(3)
p4
p3
req[1,1,1,0,0]
req[1,1,1,0,0]
p4
p3
req[1,1,1,0,0]
req[1,1,1,0,0]
p5
req[1,1,1,0,0]
P1 se prepara para salir
p5
req[1,1,1,0,0]
P1 se prepara para salir
SUZUKI–KASAMI ALGORITHM
 Cada proceso usa las siguientes dos estructuras de
datos que son pasadas con el token por el proceso
actual:
 Un arreglo last[0,...,n-1] de enteros, donde last[k]=r
implica que durante su ultima visita a la CS, el proceso
k ha completado el ciclo rth.
 Una cola Q que contiene identificadores de procesos
con peticiones pendientes.
Sistemas Distribuidos
Algoritmo de RAYMOND
1
2
10
11
3
4
13
12
Sistemas Distribuidos
14
15
5
7
6
8
9
Algoritmo de RAYMOND
 Los algoritmos trabajan en una red con topología de
árbol.
 El nodo que mantiene el token sirve como el nodo raíz,
cada arista tiene asignada una dirección, siguiendo la
dirección de estas aristas la petición llega a la raíz.
 Si la raíz cambia de un proceso a otro también la
dirección de las aristas cambia.
 Cada proceso tiene una cola Q en donde almacena las
peticiones de sus hijos.
Sistemas Distribuidos
Algoritmo de RAYMOND
 R1. Cuando un nodo tiene el token, entra en la seccion critica. En
otro caso, para entrar a la seccion critica, el nodo i registra la
peticion en su cola local Q.
 R2. Cuando un nodo j (que no tiene el token) tiene la cola Q de
peticiones no vacia, envia una peticion a su soporte, a menos que
j ya lo haya hecho y este esperando el token.
 R3. Cuando la raíz recibe una peticion, envia el token a el vecino
que se encuentra en su Q local si ha acompletado su propia CS.
Entonces otorga la variable soporte a ese vecino.
 R4.Al recibir un token, el nodo j lo envia a su vecino que esta en la
cebecera de su Q local, y elimina la peticion de Q, y da la viable
soporte a ese vecino. Si hay peticiones pendientes en Q, entonces
j envia otra peticion a su soporte.
Sistemas Distribuidos
Gracias por su Atención
Sistemas Distribuidos
Descargar

ch07a - Cinvestav