Exclusión mutua (informática)

Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar que entre más de un proceso a la vez en la sección crítica. La sección crítica es el fragmento de código donde puede modificarse un recurso compartido.

La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.

Descripción

La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como spin lock o espera activa.

Algunos sistemas tienen instrucciones multioperación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente.

Requisitos

Los requisitos esenciales para la exclusión mutua son: • [EM1] (seguridad): A lo sumo un proceso puede estar ejecutándose una vez en la SC. • [EM2] (supervivencia): Las peticiones para entrar y salir de la SC al final deben ser concedidas, esto implica la inexistencia de deadlocks e inanición. • [EM3] (ordenación): Si una petición para entrar en la SC ocurrió antes que otra, entonces la entrada a la SC se garantiza en ese orden.

Algoritmos

Los algoritmos de exclusión mutua ayudan a garantizar que un proceso pueda escribir en una sola dirección y que en ciertas secciones de código otro proceso pueda acceder a los recursos necesarios, para ello existen 3 clases de algoritmos:

Basados en tokens: Un único token se comparte entre varios nodos, el proceso que posea el token se entrega a la región crítica. Ejemplo:
- Algoritmo de servidor centralizado
- Algoritmo en anillo
- Algoritmo de Ricart y Agrawala
No basados en tokens: El acceso a la región crítica se otorga mediante turnos y mensajes, se usan marcas de tiempo para accesos equitativos. Ejemplo:
- Algoritmo de cola compartida.
Basados en quorums: Cada nodo pertenece a la red que a su vez se divide en subconjuntos de nodos (quorums), cada que entren a una región crítica el quorum se bloquea.
- Algoritmo de Maekawa

Desventajas

La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.

A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la Inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata.

La mayor parte de la investigación actual en este campo, pretende eliminar los efectos anteriormente descritos. Si bien no hay un esquema perfecto conocido, hay un interesante esquema no clásico de envío de mensajes entre fragmentos de código que, aunque permite inversiones de prioridad y produce una mayor latencia, impide los interbloqueos.