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 está basado en la comunicación por medio de mensajes entre distintos nodos que no comparten ninguna zona de memoria.

Descripción editar

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. Cuando a un proceso le llegue el mensaje de petición de otro debe responder inmediatamente para conceder el permiso, si es que está en condiciones de dárselo, o mantenerlo a la espera de su respuesta, si el nodo que realiza la petición no está en condiciones de que se le conceda la entrada.

Especificaciones editar

La idea básica es que los procesos que quieren entrar en la sección crítica construyen un mensaje de petición (este estará formado por la marca de tiempo actual y su identificador de proceso $<T,p_{i}>$ ). 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. Cuando un proceso recibe la petición de otro de los procesos, tomará una de las siguientes acciones en función de su estado:

Si el proceso receptor está fuera de la región crítica, tiene su variable de estado en LIBERADA, y no quiere entrar, responde inmediatamente al proceso remitente.
Si el proceso receptor se encuentra dentro de la región crítica, tiene su variable de estado TOMADA, no responde y pone en cola esa petición.
Si el proceso receptor también quiere entrar en la región crítica pero aún no lo ha hecho, tiene su variable de estado BUSCADA, comparará la marca de tiempo que lleva el mensaje con la marca de tiempo de su propio mensaje de petición. Entonces, si la marca de tiempo de su solicitud es menor que la que tiene el mensaje que ha recibido, encolará dicho mensaje y no responderá. En caso contrario, al tener su propio mensaje una marca de tiempo más alta que la del mensaje que le ha llegado responderá inmediatamente al proceso remitente.

Algoritmo Ricart y Agrawala

El proceso que envía la petición de entrada a la sección crítica debe esperar la respuesta de todos los demás procesos, es decir, habiendo N procesos, esperará N-1 respuestas. 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.

Cabe destacar la posibilidad en la que dos procesos manden un mensaje de petición de entrada con idénticas marcas temporales, en ese caso, las solicitudes se ordenarán de acuerdo con los identificadores de cada proceso. 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.

Propiedades editar

   Teorema 1 (Exclusión Mutua). El algoritmo provee exclusión mutua.

Demostración. Un nodo i hace verdadero hTi cuando recibe un mensaje Token. 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. Dado que inicialmente existe un único nodo i tal que hTi, o bien existirá un nodo i tal que hTi, o bien exactamente un mensaje Token en tránsito. Luego, existe un único nodo privilegiado. Del código se puede observar que sólo un nodo i tal que hTi puede entrar a su sección crítica. Luego, el algoritmo provee exclusión mutua.

   Teorema 2 (Bosque de Naimi). La relación F= {(i, fatheri) | i ∈ {1, …, N}} forma un conjunto de árboles dirigidos, en que las raíces r de cada árbol, y sólo ellas, cumplen con tDr ∨ hTr.

Demostración. Inicialmente, la propiedad se cumple. Suponga que es cierta en un instante cualquiera. Demostraremos que, luego de ejecutar cualquier paso del algoritmo, la propiedad se mantiene.

      Corolario 1. Un mensaje Request(i) es transmitido entiempo finito 
                   desde su nodo fuente i hasta un nodo j tal que 
                   j=fatherj, quien no retransmitirá el mensaje.

   Teorema 3 (Árbol Virtual de Raymond). Para todo i en R−{p}, la palabra wi es única.

Inicialmente la propiedad se cumple, ya que R={p}. Suponga que se cumple en un instante cualquiera. Demostraremos que la propiedad se mantiene luego de ejecutar cualquier paso del algoritmo.

   Teorema 4. Cualquier petición por ingreso a una sección crítica es atendida en un tiempo finito.

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. Las colas locales de cada uno de los nodos del árbol virtual de Raymond definen el recorrido que hará el token a través de este árbol, asegurando el servicio de cada una de las peticiones.

La correctitud del algoritmo se deduce de este último teorema unido al de exclusión mutua. 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.

Ejemplo editar

Para ilustrar el algoritmo, proponemos una situación que involucra a tres procesos, $p_{1}$ , $p_{2}$ y $p_{3}$ .

Ejemplo de 3 nodos.

Suponemos que $p_{2}$ no está interesado en entrar en la región crítica, mientras que $p_{3}$ y $p_{1}$ sí y lo solicitan con los mensajes de $<32,p_{3}>$ y $<38,p_{1}>$ respectivamente. Al comparar las marcas temporales de cada uno de sus mensajes la petición de $p_{1}$ es mayor que la de $p_{3}$ , cuando $p_{2}$ recibe las peticiones de ambos al no estar interesado en entrar en la sección crítica responde inmediatamente a los dos. Cuando $p_{3}$ recibe la petición de $p_{1}$ ,compara su marca temporal, que es $32$ , con la del mensaje que le llega, la cual es $38$ , y al ser menor la suya que la de $p_{1}$ no responde, manteniendo a $p_{1}$ sin permiso para entrar en la región crítica. De igual manera, cuando $p_{1}$ recibe el mensaje de $p_{3}$ y compara las marcas temporales, al tener una mayor que la de $p_{3}$ responde inmediatamente. Cuando $p_{3}$ recibe las $N-1$ respuestas puede entrar en la sección crítica. Cuando $p_{3}$ salga de ella, responderá a $p_{1}$ de forma que garantiza así su entrada.

Puntos de fallo editar

Puede producirse el fallo de cualquiera de los equipos y entonces no responder a las peticiones, lo que ocasionaría que se interpretara, de manera errónea, como la denegación de entrada a la sección crítica, bloqueando también todas las peticiones siguientes al fallo. 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.

Otro posible fallo es el de entrar en la región crítica cuando se recibe el permiso de la mayoría de los procesos y no de todos en total. 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 $(N-1)$ respuestas.

Costes editar

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 $2(N-1)$ mensajes, siendo $N$ el número de procesos en el sistema; $(N-1)$ multidifusión de mensajes de petición, seguido de $(N-1)$ respuestas. Esto hace que el algoritmo tenga un mayor coste en términos de consumo de ancho de banda que otros algoritmos de exclusión mutua ( $2N-2)$ .

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.

Ventajas editar

La ventaja de este algoritmo es que su retraso de sincronización es solo del tiempo de transmisión de un mensaje, mientras que otros algoritmos tienen también el retraso de sincronización de un mensaje de ida y otro de vuelta.

Problemas editar

Uno de los problemas de este algoritmo es la falla de un nodo. En tal situación, un proceso puede morir de hambre para siempre. Este problema se puede resolver detectando fallas en los nodos después de un tiempo de espera.

Bibliografía editar

George Colouris, Jean Dollimore, Tim Kindberg, Gordon Blair (1988). Distributed Systems. Concepts and Design. Pearson.
Andrew S. TanenBaum, Marteen Van Steen (2001). Distributed Systems: Principles and Paradigms. Pearson.
Ricart, Glenn; Agrawala, Ashok K."An optimal algorithm for mutual exclusion in computer networks"(1 de enero de 1981)
Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. | Tema 6 - Coordinación y Acuerdo
Maekawa, M.,Oldehoeft, A.,Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.
D. Agrawal and A. El Abbadi. (1989). “Efficient solution to the distributed mutual exclusion problem”. In Proceedings of the eighth annual ACM Symposium on Principles of distributed computing. ACM Press.
Ye-In Chang. (1996). “A Simulation Study on Distributed Mutual Exclusion”. Journal of Parallel and Distributed Computing.
Theodore Johnson. (1995). “A Performance Comparison of Fast Distributed Mutual Exclusion Algorithms”. In Proceedings of the 9th International Symposium on Parallel Processing (IPPS’95). IEEE Computer Society Press.
Mamoru Maekawa (1985). “A N Algorithm for Mutual Exclusion in Decentralized Systems”. ACM Transactions on Computer Systems.
Mohamed Naimi, Michel Trehel and Andre Arnold. (1996). “A log(N) Distributed Mutual Exclusion Algorithm based on Path Reversal”. Journal of Parallel and Distributed Computing.

Datos: Q1291716