Algoritmo de exclusión mutua.
Un
algoritmo distribuido.
(El algoritmo de Ricart y
Agrawala ) Este algoritmo requiere de un orden total de todos los eventos en el
sistema. Para cualquier pareja de mensajes debe quedar claro quién ocurrió
primero.
Cuando un proceso desea
entrar a la región crítica, construye un mensaje con el nombre de ésta, su
número de proceso y la hor actual, y la envía a todos los demás procesos y de
forma conceptual a él mismo. Se puede utilizar comunicación en grupo confiable.
Cuando un proceso recibe un
mensaje de solicitud de otro proceso para entrar a una región crítica, debe
distinguir tres casos:
- Si el receptor no está en la región crítica y
no desea entrar a ella, envía de regreso un mensaje ok al emisor.
- Si el receptor desea entrar a la región
crítica, no responde, sino que forma la solicitud en una fila.
- Si el receptor desea entrar a la región
crítica, pero no lo ha logrado todavía, compara la marca de tiempo en el
mensaje recibido con la marca contenida en el mensaje que envió a cada
uno. La menor de las marcas gana. Si el mensaje recibido es menor, el
receptor envía un mensaje ok. Si su propio mensaje tiene una marca menor,
el receptor forma la solicitud en una fila y no envía nada.
Un proceso puede entrar a la
región crítica si obtiene permiso de todos. Si es así, entra y cuando sale
envía mensajes ok a todos los procesos de su fila y elimina los elementos de la
fila.
Con este método la exclusión
mutua queda garantizada sin bloqueo ni inanición. El número de mensajes
necesarios por entrada es de 2(n-1), donde n es el número total de procesos en
el sistema.
Ejemplo: Supongamos que
tenemos 4 procesos numerados del 0 al 3, los procesos 1 y 3 desean entrar a la
región crítica, 0 no desea entrar a la región crítica y 2 esta dentro de la
región crítica. Los procesos 1 y 3 envían mensaje casi al mismo tiempo, pero la
marca de 3 es menor a la de 1 (1 tiene marca de tiempo igual a 3 y 3 tiene
marca de tiempo igual a 2). Cuando 0 recibe el mensaje de 3 le otorga el
permiso, como la marca de tiempo de 3 es menor que la de 1 entonces 1 debe
enviar un mensaje de ok a 3, 2 esta dentro de la región crítica por lo que
forma el mensaje de 3 en una fila.
Cuando 0 recibe el mensaje
de 1 le responde con un ok, 3 al recibir el mensaje de 1 checa su propia marca
de tiempo, como su marca de tiempo es menor que la de 1 entonces forma la
solicitud de 1 es una fila y no responde nada. El proceso 2 al recibir mensaje
de 1, forma el mensaje en una fila ya que 2 esta en la r.c.
El proceso 3 tiene el
permiso de 0 y 1 para entrar a la región crítica, y el proceso 1 tiene el
permiso de 0. Cuando 2 sale de la región crítica envía mensajes de ok a los
procesos de su fila, en este caso, a los procesos 3 y 1.
El proceso 3 ya tiene el permiso de todos por
lo tanto puede entrar a la r.c., mientras que el proceso 1 debe esperar a que 3
salga de la región crítica. Cuando 3 salga de la región crítica debe enviar un
mensaje de ok al proceso 1.
Ahora existen n puntos de
falla. Sino hay respuesta, se interpretará como ua negación de permiso, aún
cuando el proceso haya muerto, podría haber bloqueos.
Una posible modificación es
la siguiente, cada vez que se haga una solicitud debe haber una respuesta
negativa o positiva.
Funciona bien con
comunicación en grupo, donde se tenga un registro de los integrantes del grupo,
quiénes entran y quiénes han salido o han fallado. Funciona bien con grupos
pequeños.
El algoritmo es más lento,
más complejo y más caro y menos robusto que el centralizado. Pero sirve para
estimular a investigadores a producir algoritmos útiles.
