Algoritmo de Ricart y Agrawala
El algoritmo de Ricart y Agrawala es un algoritmo de exclusión mutua distribuida en computación distribuida, desarrollado en 1981 por Glenn Ricart y Ashok Agrawala, fue desarrollado como una alternativa mejorada al algoritmo centralizado, el cual, es el algoritmo más sencillo de exclusión mutua.
El algoritmo de Ricart y Agrawala se basa en la coordinación entre N procesos para conceder la entrada a una determinada región crítica, es decir, en la implementación de exclusión mutua entre N procesos.
La idea básica es que los procesos que deseen entrar en una sección crítica deben tener la aprobación de todos los demás nodos involucrados en la coordinación.
Sin la aprobación de todos los demás un nodo no puede acceder a dicha sección crítica.
Para tener la aprobación de todos los procesos que participan en la exclusión mutua, el nodo inicial debe crear un mensaje de petición.
Ese mensaje de petición se enviará a todos los procesos incluido él mismo (mensaje de multidifusión).
El proceso que solicita con ese mensaje de petición entrar a la sección crítica solo podrá entrar en ella cuando todos los demás procesos hayan respondido a dicho mensaje.
Cabe indicar que cada proceso tendrá una variable de estado propia en función de si está fuera de la sección crítica, LIBERADA, si quiere entrar en la sección crítica, BUSCADA, o si se encuentra en la sección crítica, TOMADA.
En el momento que tenga todas las respuestas podrá entrar en la sección crítica, mientras esté en ella encolará todos los mensajes que le lleguen de petición de entrada a la sección crítica.
Cuando salga de ella, comenzará a responder a todos los procesos que haya puesto en cola durante su estancia en la sección crítica, y tras ello, borrará dicha cola.
Hay que tener en cuenta también que cuando un proceso solicita la entrada en la sección crítica aplaza todo el procesamiento de peticiones de otros procesos hasta que su propia solicitud haya sido enviada y se haya enviado con la marca temporal T, de esta manera se garantiza que los procesos realicen decisiones consistentes cuando procesan peticiones.
Un nodo i hace falso hTi sólo cuando envía exactamente un mensaje Token.
Un mensaje Token sólo puede ser enviado por un nodo i tal que hTi.
Demostraremos que, luego de ejecutar cualquier paso del algoritmo, la propiedad se mantiene.
Inicialmente la propiedad se cumple, ya que R={p}.
Demostraremos que la propiedad se mantiene luego de ejecutar cualquier paso del algoritmo.
La demostración de este teorema se basa en el Corolario del Teorema del Bosque de Naimi, que asegura que una petición llegará en tiempo finito a un nodo del árbol virtual de Raymond.
Note que, si hay sólo una petición pendiente, el Árbol Virtual de Raymond está formado por sólo un nodo y existe un único árbol en el Bosque de Naimi compuesto por todos los nodos del sistema.
Si los N nodos del sistema quieren ingresar a su sección crítica, existen N árboles independientes en el Bosque de Naimi.
Bajo estas condiciones, todos los nodos pertenecen al Árbol Virtual de Raymond.
Para ilustrar el algoritmo, proponemos una situación que involucra a tres procesos,
no está interesado en entrar en la región crítica, mientras que
recibe las peticiones de ambos al no estar interesado en entrar en la sección crítica responde inmediatamente a los dos.
y compara las marcas temporales, al tener una mayor que la de
Esto puede arreglarse si a los mensajes de petición siempre se responde con un ACK, de forma que si un equipo no contestara se consideraría que está caído y se le saca del grupo para evitar fallos.
Para evitar este caso, en este algoritmo siempre es necesaria la respuesta de todos los demás nodos para entrar en la región crítica, es decir, un proceso se mantendrá a la espera hasta que no reciba
Teniendo todo lo expuesto en cuenta, en este algoritmo se consigue la exclusión mutua sin interbloqueo ni inanición, para lograr esto, se requieren por cada entrar a la sección crítica
El rendimiento de este algoritmo se podría mejorar porque en primer lugar el proceso que entró en último lugar a la región crítica y que no ha recibido peticiones para entrar, aunque sigue el protocolo puede decidir volver a entrar en ella.
Y, en segundo lugar, Ricart y Agrawala refinaron el protocolo de tal forma que se necesiten en el peor de los casos, N mensajes para realizar la entrada en la sección crítica.
En tal situación, un proceso puede morir de hambre para siempre.
