La exclusión mutua es una propiedad de control de concurrencia que se introduce para evitar condiciones de carrera. Es el requisito de que un proceso no puede ingresar a su sección crítica mientras otro proceso concurrente está actualmente presente o ejecutándose en su sección crítica, es decir, solo se permite que un proceso ejecute la sección crítica en un momento dado.
Exclusión mutua en sistema informático único vs. sistema distribuido:
en un solo sistema informático, la memoria y otros recursos se comparten entre diferentes procesos. El estado de los recursos compartidos y el estado de los usuarios está fácilmente disponible en la memoria compartida, por lo que con la ayuda de variables compartidas (por ejemplo: semáforos ), el problema de exclusión mutua se puede resolver fácilmente.
En los sistemas distribuidos, no tenemos memoria compartida ni un reloj físico común y, por lo tanto, no podemos resolver el problema de exclusión mutua utilizando variables compartidas. Para eliminar el problema de exclusión mutua en el sistema distribuido, se utiliza un enfoque basado en el paso de mensajes.
Un sitio en sistema distribuido no tiene información completa del estado del sistema debido a la falta de memoria compartida y un reloj físico común.
Requisitos del algoritmo de exclusión mutua:
- Sin interbloqueo:
dos o más sitios no deben esperar interminablemente ningún mensaje que nunca llegará. - Sin hambre:
cada sitio que quiera ejecutar una sección crítica debe tener la oportunidad de ejecutarla en un tiempo finito. Cualquier sitio no debe esperar indefinidamente para ejecutar la sección crítica mientras que otro sitio ejecuta repetidamente la sección crítica - Equidad:
cada sitio debe tener una oportunidad justa de ejecutar la sección crítica. Cualquier solicitud de ejecución de la sección crítica debe ejecutarse en el orden en que se realizan, es decir, las requests de ejecución de la sección crítica deben ejecutarse en el orden de llegada al sistema. - Tolerancia a fallos:
en caso de fallo, debería ser capaz de reconocerlo por sí mismo para seguir funcionando sin ninguna interrupción.
Solución a la exclusión mutua distribuida:
como sabemos, las variables compartidas o un kernel local no se pueden usar para implementar la exclusión mutua en sistemas distribuidos. El paso de mensajes es una forma de implementar la exclusión mutua. A continuación se muestran los tres enfoques basados en el paso de mensajes para implementar la exclusión mutua en sistemas distribuidos:
- Algoritmo basado en token:
- Un token único se comparte entre todos los sitios.
- Si un sitio posee el token único, se le permite ingresar a su sección crítica
- Este enfoque utiliza el número de secuencia para ordenar las requests de la sección crítica.
- Cada solicitud de sección crítica contiene un número de secuencia. Este número de secuencia se utiliza para distinguir las requests antiguas de las actuales.
- Este enfoque asegura la exclusión mutua ya que el token es único
-
Example: Suzuki-Kasami’s Broadcast Algorithm
- Enfoque no basado en tokens:
- Un sitio se comunica con otros sitios para determinar qué sitios deben ejecutar la sección crítica a continuación. Esto requiere el intercambio de dos o más rondas sucesivas de mensajes entre sitios.
- Este enfoque utiliza marcas de tiempo en lugar de números de secuencia para solicitar requests para la sección crítica.
- Cada vez que un sitio solicita una sección crítica, obtiene una marca de tiempo. La marca de tiempo también se utiliza para resolver cualquier conflicto entre las requests de secciones críticas.
- Todos los algoritmos que siguen un enfoque no basado en tokens mantienen un reloj lógico. Los relojes lógicos se actualizan según el esquema de Lamport
-
Example: Lamport's algorithm, Ricart–Agrawala algorithm
- Enfoque basado en quórum:
- En lugar de solicitar permiso para ejecutar la sección crítica de todos los demás sitios, cada sitio solicita solo un subconjunto de sitios que se denomina quórum .
- Dos subconjuntos cualesquiera de sitios o Quórum contienen un sitio común.
- Este sitio común es responsable de garantizar la exclusión mutua.
-
Example: Maekawa’s Algorithm