En informática , la exclusión mutua es una propiedad del control de concurrencia , que se instituye con el propósito de prevenir condiciones de carrera . Es el requisito de que un hilo de ejecución nunca entre en una sección crítica mientras un hilo de ejecución concurrente ya esté accediendo a dicha sección crítica, lo que se refiere a un intervalo de tiempo durante el cual un hilo de ejecución accede a un recurso compartido o a una memoria compartida .
El recurso compartido es un objeto de datos que dos o más subprocesos simultáneos intentan modificar (donde se permiten dos operaciones de lectura simultáneas, pero no se permiten dos operaciones de escritura simultáneas ni una de lectura y una de escritura, ya que esto genera inconsistencia en los datos). Los algoritmos de exclusión mutua garantizan que, si un proceso ya está realizando una operación de escritura en un objeto de datos [sección crítica], ningún otro proceso o subproceso puede acceder o modificar el mismo objeto hasta que el primer proceso haya terminado de escribir en el objeto de datos [sección crítica] y haya liberado el objeto para que otros procesos puedan leer y escribir en él.
El requisito de exclusión mutua fue identificado y resuelto por primera vez por Edsger W. Dijkstra en su artículo seminal de 1965 "Solución de un problema en el control de programación concurrente", [1] [2] que se considera el primer tema en el estudio de algoritmos concurrentes. [3]
Un ejemplo simple de por qué la exclusión mutua es importante en la práctica se puede visualizar usando una lista enlazada simple de cuatro elementos, donde el segundo y el tercero se deben eliminar. La eliminación de un nodo que se encuentra entre otros dos nodos se realiza cambiando el siguiente puntero del nodo anterior para que apunte al siguiente nodo (en otras palabras, si se está eliminando el nodo i , entonces el siguiente puntero del nodo i – 1 se cambia para que apunte al nodo i + 1 , eliminando así de la lista enlazada cualquier referencia al nodo i ). Cuando una lista enlazada de este tipo se comparte entre varios subprocesos de ejecución, dos subprocesos de ejecución pueden intentar eliminar dos nodos diferentes simultáneamente, un subproceso de ejecución cambia el siguiente puntero del nodo i – 1 para que apunte al nodo i + 1 , mientras que otro subproceso de ejecución cambia el siguiente puntero del nodo i para que apunte al nodo i + 2 . Aunque ambas operaciones de eliminación se completan con éxito, no se logra el estado deseado de la lista enlazada: el nodo i + 1 permanece en la lista, porque el siguiente puntero del nodo i – 1 apunta al nodo i + 1 .
Este problema (llamado condición de carrera ) se puede evitar utilizando el requisito de exclusión mutua para garantizar que no puedan producirse actualizaciones simultáneas de la misma parte de la lista.
El término exclusión mutua también se utiliza en referencia a la escritura simultánea de una dirección de memoria por un hilo mientras la dirección de memoria mencionada anteriormente está siendo manipulada o leída por uno o más hilos adicionales.
El problema que aborda la exclusión mutua es un problema de compartición de recursos: ¿cómo puede un sistema de software controlar el acceso de múltiples procesos a un recurso compartido, cuando cada proceso necesita control exclusivo de ese recurso mientras realiza su trabajo? La solución de exclusión mutua para esto hace que el recurso compartido esté disponible solo mientras el proceso se encuentre en un segmento de código específico llamado sección crítica . Controla el acceso al recurso compartido controlando cada ejecución mutua de esa parte de su programa donde se usaría el recurso.
Una solución exitosa a este problema debe tener al menos estas dos propiedades:
La libertad de bloqueo se puede ampliar para implementar una o ambas de estas propiedades:
El programa de cada proceso se puede dividir en cuatro secciones, lo que da como resultado cuatro estados. La ejecución del programa pasa por estos cuatro estados en orden: [5]
Si un proceso desea ingresar a la sección crítica, primero debe ejecutar la sección de intento y esperar hasta obtener acceso a la sección crítica. Una vez que el proceso ha ejecutado su sección crítica y ha terminado con los recursos compartidos, debe ejecutar la sección de salida para liberarlos para que otros procesos los usen. Luego, el proceso regresa a su sección no crítica.
En sistemas monoprocesador , la solución más sencilla para lograr la exclusión mutua es desactivar las interrupciones durante la sección crítica de un proceso. Esto evitará que se ejecuten rutinas de servicio de interrupciones (lo que evitará de manera efectiva que se interrumpa un proceso ). Aunque esta solución es efectiva, genera muchos problemas. Si una sección crítica es larga, entonces el reloj del sistema se desviará cada vez que se ejecute una sección crítica porque la interrupción del temporizador ya no recibe servicio, por lo que es imposible rastrear el tiempo durante la sección crítica. Además, si un proceso se detiene durante su sección crítica, el control nunca se devolverá a otro proceso, lo que detendrá efectivamente todo el sistema. Un método más elegante para lograr la exclusión mutua es la espera ocupada .
La espera activa es eficaz tanto para sistemas monoprocesador como multiprocesador . El uso de memoria compartida y una instrucción atómica de prueba y configuración proporcionan la exclusión mutua. Un proceso puede probar y configurar en una ubicación de la memoria compartida y, dado que la operación es atómica, solo un proceso puede configurar el indicador a la vez. Cualquier proceso que no logre configurar el indicador puede continuar realizando otras tareas e intentarlo nuevamente más tarde, liberar el procesador a otro proceso e intentarlo nuevamente más tarde, o continuar en bucle mientras verifica el indicador hasta que logre adquirirlo. La preempción aún es posible, por lo que este método permite que el sistema continúe funcionando, incluso si un proceso se detiene mientras mantiene el bloqueo.
Se pueden utilizar otras operaciones atómicas para proporcionar exclusión mutua de estructuras de datos; la más notable de ellas es la comparación e intercambio (CAS). CAS se puede utilizar para lograr la exclusión mutua sin espera para cualquier estructura de datos compartida mediante la creación de una lista enlazada donde cada nodo representa la operación deseada que se va a realizar. CAS se utiliza luego para cambiar los punteros en la lista enlazada [6] durante la inserción de un nuevo nodo. Solo un proceso puede tener éxito en su CAS; todos los demás procesos que intenten agregar un nodo al mismo tiempo tendrán que intentarlo de nuevo. Cada proceso puede entonces mantener una copia local de la estructura de datos y, al recorrer la lista enlazada, puede realizar cada operación de la lista en su copia local.
Además de las soluciones basadas en hardware, existen algunas soluciones de software que utilizan la espera activa para lograr la exclusión mutua. Algunos ejemplos son:
Estos algoritmos no funcionan si se utiliza una ejecución fuera de orden en la plataforma que los ejecuta. Los programadores deben especificar un orden estricto en las operaciones de memoria dentro de un hilo. [8]
A menudo es preferible utilizar las funciones de sincronización proporcionadas por la biblioteca de subprocesos múltiples de un sistema operativo , que aprovechará las soluciones de hardware si es posible, pero utilizará soluciones de software si no existen soluciones de hardware. Por ejemplo, cuando se utiliza la biblioteca de bloqueos del sistema operativo y un subproceso intenta adquirir un bloqueo ya adquirido, el sistema operativo podría suspender el subproceso utilizando un cambio de contexto y cambiarlo por otro subproceso que esté listo para ejecutarse, o podría poner ese procesador en un estado de bajo consumo de energía si no hay otro subproceso que pueda ejecutarse. Por lo tanto, la mayoría de los métodos de exclusión mutua modernos intentan reducir la latencia y las esperas ocupadas mediante el uso de colas y cambios de contexto. Sin embargo, si se puede demostrar que el tiempo que se dedica a suspender un subproceso y luego restaurarlo es siempre mayor que el tiempo que se debe esperar para que un subproceso esté listo para ejecutarse después de haber sido bloqueado en una situación particular, entonces los bloqueos de giro son una solución aceptable (solo para esa situación). [ cita requerida ]
Un registro binario de prueba y configuración es suficiente para proporcionar una solución sin bloqueos al problema de exclusión mutua. Pero una solución construida con un registro de prueba y configuración puede posiblemente llevar a la inanición de algunos procesos que quedan atrapados en la sección de prueba. [4] De hecho, se requieren estados de memoria distintos para evitar el bloqueo. Para evitar una espera ilimitada, se requieren n estados de memoria distintos. [9]
La mayoría de los algoritmos de exclusión mutua están diseñados con la suposición de que no se produce ningún fallo mientras un proceso se está ejecutando dentro de la sección crítica. Sin embargo, en la realidad, estos fallos pueden ser habituales. Por ejemplo, una pérdida repentina de energía o una interconexión defectuosa pueden hacer que un proceso en una sección crítica experimente un error irrecuperable o que no pueda continuar. Si se produce un fallo de este tipo, los algoritmos de exclusión mutua convencionales, no tolerantes a fallos, pueden bloquearse o hacer que fallen las propiedades de actividad clave. Para abordar este problema, se han propuesto varias soluciones que utilizan mecanismos de recuperación ante fallos. [10]
Las soluciones explicadas anteriormente se pueden utilizar para construir las primitivas de sincronización siguientes:
Muchas formas de exclusión mutua tienen efectos secundarios. Por ejemplo, los semáforos clásicos permiten bloqueos , en los que un proceso obtiene un semáforo, otro proceso obtiene un segundo semáforo y luego ambos esperan hasta que se libere el otro semáforo. Otros efectos secundarios comunes incluyen la inanición , en la que un proceso nunca obtiene los recursos suficientes para completar su ejecución; la inversión de prioridad , en la que un subproceso de mayor prioridad espera a un subproceso de menor prioridad; y la alta latencia, en la que la respuesta a las interrupciones no es rápida.
Se han realizado muchas investigaciones para eliminar los efectos anteriores, a menudo con el objetivo de garantizar un progreso sin bloqueos . No se conoce ningún esquema perfecto. Las llamadas al sistema bloqueantes solían poner en suspensión un proceso completo. Hasta que dichas llamadas se volvieron seguras para subprocesos , no existía un mecanismo adecuado para poner en suspensión un único subproceso dentro de un proceso (consulte sondeo ). [ cita requerida ]
