¿Cómo se puede implementar la exclusión mutua en sistemas distribuidos?

2 Algoritmo de Ricart-Agrawala

El algoritmo de Ricart-Agrawala es una optimización del algoritmo de Lamport para la exclusión mutua en sistemas distribuidos. Reduce el número de mensajes intercambiados utilizando el concepto de respuestas diferidas. Cuando un proceso desea entrar en una sección crítica, envía un mensaje de solicitud a todos los demás procesos con su valor de reloj lógico actual y el identificador de recurso. Cada proceso compara su mensaje de solicitud con el mensaje de solicitud del remitente: si el remitente tiene una prioridad más alta, responde con un mensaje de confirmación y actualiza su reloj lógico, y si el remitente tiene una prioridad más baja, difiere la respuesta hasta que salga de la sección crítica o abandone la solicitud. Cuando un proceso recibe confirmaciones de todos los demás procesos, entra en la sección crítica. Al salir de la sección crítica, envía un mensaje de liberación a todos los demás procesos con su valor de reloj lógico actual y el identificador de recursos, así como cualquier respuesta diferida que no se haya reconocido antes.

3 Algoritmos basados en tokens

Un enfoque diferente para la exclusión mutua en sistemas distribuidos es utilizar algoritmos basados en tokens, que se basan en un mensaje especial llamado token que circula entre los procesos. El proceso que contiene el token tiene el derecho exclusivo de ingresar a la sección crítica. Los algoritmos basados en tokens vienen en dos variedades: basados en anillos y basados en árboles. Los algoritmos basados en anillo organizan los procesos en un anillo lógico y el token se pasa de un proceso al siguiente en un orden fijo. El algoritmo Suzuki-Kasami es un ejemplo de esto, utilizando un token con un vector de solicitudes de cada proceso y una cola de solicitudes pendientes. Los algoritmos basados en árboles organizan los procesos en un árbol lógico y el token se pasa de la raíz a las hojas y viceversa. Un ejemplo de esto es el algoritmo de Raymond, que utiliza un token con la identidad del proceso que lo solicitó en último lugar. Cuando un proceso desea entrar en la sección crítica, envía un mensaje de solicitud a su padre en el árbol. Si recibe el token, entra en la sección crítica y lo devuelve a su padre con la identidad del siguiente solicitante.