Algoritmo de Ricart-Agrawala

Algoritmo de exclusión mutua en un sistema distribuido

El algoritmo Ricart-Agrawala es un algoritmo de exclusión mutua en un sistema distribuido . Este algoritmo es una extensión y optimización del algoritmo de exclusión mutua distribuida de Lamport , al eliminar la necesidad de mensajes de liberación. ^[1] Fue desarrollado por los científicos informáticos Glenn Ricart y Ashok Agrawala .

Algoritmo

Terminología

• Un sitio es cualquier dispositivo informático que ejecuta el algoritmo Ricart-Agrawala
• El sitio solicitante es el sitio que solicita ingresar a la sección crítica.
• El sitio receptor es cualquier otro sitio que recibe una solicitud del sitio solicitante.

Algoritmo

Solicitando sitio

• Envía un mensaje a todos los sitios. Este mensaje incluye el nombre del sitio y la marca de tiempo actual del sistema según su reloj lógico ( que se supone que está sincronizado con los demás sitios ).

Sitio de recepción

• Al recibir un mensaje de solicitud, enviar inmediatamente un mensaje de respuesta con marca de tiempo si y solo si:

• El proceso de recepción no está interesado actualmente en la sección crítica O
• El proceso de recepción tiene una prioridad más baja ( normalmente esto significa tener una marca de tiempo posterior)

• De lo contrario, el proceso de recepción aplazará el mensaje de respuesta. Esto significa que se enviará una respuesta solo después de que el proceso de recepción haya terminado de utilizar la sección crítica.

Sección crítica:

• El sitio solicitante ingresa a su sección crítica solo después de recibir todos los mensajes de respuesta.
• Al salir de la sección crítica, el sitio envía todos los mensajes de respuesta diferida.

Actuación

• Número máximo de mensajes de red: ${\displaystyle 2*(N-1)}$
• Retrasos de sincronización: Un retraso en la propagación del mensaje

Optimizaciones comunes

Una vez que el sitio ha recibido un mensaje del sitio , el sitio puede ingresar a la sección crítica varias veces sin recibir permiso de en los intentos posteriores hasta el momento en que ha enviado un mensaje a . Esto se llama optimización de Roucairol-Carvalho o algoritmo de Roucairol-Carvalho. ${\displaystyle P_{i}}$ ${\displaystyle reply}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}}$ ${\displaystyle reply}$ ${\displaystyle P_{j}}$

Problemas

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

Véase también

• El algoritmo de panadería de Lamport
• Algoritmo de exclusión mutua distribuida de Lamport
• Algoritmo de Maekawa
• Algoritmo de Suzuki-Kasami
• Algoritmo de Raymond
• Algoritmo de Naimi-Trehel

Referencias

1. Ricart, Glenn; Agrawala, Ashok K. (1 de enero de 1981). "Un algoritmo óptimo para la exclusión mutua en redes informáticas". Comunicaciones de la ACM . 24 (1): 9–17. doi : 10.1145/358527.358537 . S2CID  1779615.

• Maekawa, M., Oldehoeft, A., Oldehoeft, R. (1987). Sistemas operativos: concepto avanzado. Benjamin/Cummings Publishing Company, Inc.