Sistemas Distribuidos

Sistemas Distribuidos

Tema: Exclusión MutuaEdgar Adrian Esquivel Mendiola

CINVESTAV, Tamaulipas


Problema de Exclusión Mutua

Acceso exclusivo a algun recurso compartido en una red de procesos.

Posibles solucionesShared MemoryMessage-passingEjemplos:

Impresión de documentos. Manejo de archivos compartidos. CSMA/CD usado para conexiones en Ethernets.


Solución usando paso de mensajes

Algoritmos descentralizados

Coordinador

P1 P2

P3 P4 P5

respuesta petición

respuestaliberación

respuesta

2 1 4

Cola de peticiones

P1

P2

P3

P4

2 1 42 1 4

2 1 42 1 4

petición

petición petición

Controlados por coordinador


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 cualquier momento. Esta es una propiedad de seguridad.

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.


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.


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.


Ejemplo LAMPORT

P1 P2

P3 P4

PeticiónPe

tició

n Petición

1

1

1

1

Petic

ión

Petición

Petició

n

4

4

4

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.


Solución de RICART–AGRAWALA

P1

P2

P3CS

CS

respuestarespuesta

respuesta

respuestaPetic

ión (t

s:1, P

3)Pe

tición

(ts:1

, P3)

Petición

(ts:2, P1)

Petición

(ts:2, P1)

Queue(ts:2, P2)


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.


Solución de MAEKAWA


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.


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.

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.

Token


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.

P1

p3p4

p5

P2

req[1,0,0,0,0]

req[1,0,0,0,0]

req[1,0,0,0,0] req[1,0,0,0,

0]

req[1,0,0,0,0]

Last[0,0,0,0,0]

Proceso p1 envía petición

P1

p3p4

p5

P2

Proceso p2 y p3 envía petición

req[1,1,1,0,0] req[1,1,1,0,

0]

req[1,1,1,0,0]

req[1,1,1,0,0]

req[1,1,1,0,0]

Last[0,0,0,0,0]

P1

p3p4

p5

P2

P1 se prepara para salir

req[1,1,1,0,0] req[1,1,1,0,

0]

req[1,1,1,0,0]

req[1,1,1,0,0]

req[1,1,1,0,0]

Last[1,0,0,0,0] Q(2,3)

Last[1,0,0,0,0]

P1

p3p4

p5

P2

P1 se prepara para salir

req[1,1,1,0,0] req[1,1,1,0,

0]

req[1,1,1,0,0]

req[1,1,1,0,0]

req[1,1,1,0,0]

Q(3)


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.


Algoritmo de RAYMOND1

32

1310 74

1211 1514 65 98


Algoritmo de RAYMONDLos 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.


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.


Gracias por su Atención

Documents

Sistemas Distribuidos