Exclusión mutua (informática)
Keywords: Exclusión mutua (informática), Algoritmo, C. A. R. Hoare, Edsger Dijkstra, Estructura de datos, Exclusión mutua, Interrupción, Monitor, Programación concurrente
Para otros usos de Exclusión mutua, véase la página de desambiguación.
Los algoritmos de exclusión mutua (comúnmente abreviada como mutex) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan concurrentemente a recursos que no pueden ser compartidos.
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 vital porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal. Si la sección crítica no está protegida, esto puede provocar fallos graves.
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, denominado "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 test-and-set indivisible 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 sistema operativos usan comúnmente.
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 los "benchmarks" 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 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.
Algunos ejemplos de algoritmos clásicos de exclusión mutua son:
- El algoritmo de Dekker.
- El algoritmo de Peterson.
Ver también
- Semáforo (inventado por Edsger Dijkstra) (descripción muy sencilla)
- Monitor(inventado por C. A. R. Hoare) (sin interbloqueos)