Exclusión mutua

Dos nodos, i y i + 1, ser eliminado simultáneamente resultados en nodo i + 1 no ser eliminado.

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 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 o una lectura y una escritura, ya que conduce a datos inconsecuencia). Los algoritmos de exclusión mutua aseguran 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/hilo puede acceder/modificar el mismo objeto hasta que el primer proceso haya terminado de escribir en el objeto de datos [sección crítica] y liberó el objeto para que otros procesos lo leyeran y escribieran.

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", que se considera el primer tema en el estudio de algoritmos concurrentes.

Un ejemplo simple de por qué la exclusión mutua es importante en la práctica se puede visualizar utilizando una lista de cuatro elementos enlazados individualmente, donde el segundo y el tercero deben eliminarse. La eliminación de un nodo que se encuentra entre otros dos nodos se realiza cambiando el puntero siguiente del nodo anterior para que apunte al siguiente nodo (en otras palabras, si el nodo i se está eliminando, luego el puntero next del nodo i – 1 se cambia para apuntar 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 múltiples subprocesos de ejecución, dos subprocesos de ejecución pueden intentar eliminar dos nodos diferentes simultáneamente, un subproceso de ejecución cambia el puntero siguiente del nodo i – 1 para apuntar al nodo i + 1, mientras que otro subproceso de ejecución cambia el siguiente puntero del nodo i para apuntar 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 se produzcan actualizaciones simultáneas en 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 parte de un subproceso mientras la dirección de memoria antes mencionada está siendo manipulada o leída por uno o más subprocesos.

Descripción del problema

El problema que aborda la exclusión mutua es un problema de recursos compartidos: ¿cómo puede un sistema de software controlar múltiples procesos? acceso a un recurso compartido, cuando cada proceso necesita el control exclusivo de ese recurso mientras hace su trabajo? La solución de exclusión mutua para esto hace que el recurso compartido esté disponible solo mientras el proceso se encuentra en un segmento de código específico denominado sección crítica. Controla el acceso al recurso compartido al controlar 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:

• Debe implementar Exclusión mutua: sólo un proceso puede estar en la sección crítica a la vez.
• Debe estar libre de Deadlocks: si los procesos están tratando de entrar en la sección crítica, uno de ellos debe eventualmente ser capaz de hacerlo con éxito, siempre que ningún proceso permanezca en la sección crítica permanentemente.

La libertad de interbloqueo se puede expandir para implementar una o ambas de estas propiedades:

• Libertad de bloqueo garantiza que cualquier proceso que desee entrar en la sección crítica será capaz de hacerlo eventualmente. Esto es distinto de la evitación del estancamiento, que requiere que algunos El proceso de espera puede acceder a la sección crítica, pero no requiere que cada proceso tenga un giro. Si dos procesos continuamente intercambian un recurso entre ellos, un tercer proceso podría ser bloqueado y experimentar la inanición de recursos, a pesar de que el sistema no está en estancamiento. Si un sistema está libre de bloqueos, garantiza que cada proceso puede conseguir un giro en algún momento del futuro.
• A k-bounded waiting property da un compromiso más preciso que la libertad de bloqueo. La libertad de bloqueo asegura que cada proceso puede acceder a la sección crítica eventualmente: no da garantía de cuánto tiempo será la espera. En la práctica, un proceso podría superar un número arbitrario o sin límites de veces por otros procesos de mayor prioridad antes de que llegue a su turno. Bajo k- una propiedad de espera llena, cada proceso tiene un tiempo de espera máximo finito. Esto funciona estableciendo un límite al número de veces que otros procesos pueden cortar en línea, de modo que ningún proceso puede entrar en la sección crítica más que k veces mientras otro está esperando.

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:

el ciclo de secciones de un solo proceso

Sección no crítica

La operación está fuera de la sección crítica; el proceso no está utilizando o solicitando el recurso compartido.

Intentar

El proceso intenta entrar en la sección crítica.

Sección crítica

El proceso se permite acceder al recurso compartido en esta sección.

Exit

El proceso deja la sección crítica y pone el recurso compartido a disposición de otros procesos.

Si un proceso desea ingresar a la sección crítica, primero debe ejecutar la sección de prueba y esperar hasta que obtenga acceso a la sección crítica. Después de que el proceso haya ejecutado su sección crítica y haya terminado con los recursos compartidos, debe ejecutar la sección de salida para liberarlos para otros procesos. utilizar. El proceso luego regresa a su sección no crítica.

Hacer cumplir la exclusión mutua

Soluciones de hardware

En los sistemas de un solo procesador, la solución más sencilla para lograr la exclusión mutua es deshabilitar las interrupciones durante la sección crítica de un proceso. Esto evitará que se ejecuten las rutinas de servicio de interrupción (evitando efectivamente que un proceso sea reemplazado). Aunque esta solución es eficaz, conduce a muchos problemas. Si una sección crítica es larga, 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, deteniendo efectivamente todo el sistema. Un método más elegante para lograr la exclusión mutua es la espera activa.

La espera ocupada es efectiva tanto para sistemas monoprocesador como multiprocesador. El uso de memoria compartida y una instrucción atómica de prueba y ajuste proporciona la exclusión mutua. Un proceso puede probar y establecer en una ubicación en la memoria compartida y, dado que la operación es atómica, solo un proceso puede establecer la bandera a la vez. Cualquier proceso que no tenga éxito al configurar el indicador puede continuar con 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 preferencia aún es posible, por lo que este método permite que el sistema continúe funcionando, incluso si un proceso se detiene mientras se mantiene el bloqueo.

Se pueden usar varias otras operaciones atómicas para proporcionar la exclusión mutua de estructuras de datos; el más notable de estos es comparar e intercambiar (CAS). CAS se puede utilizar para lograr una exclusión mutua sin esperas para cualquier estructura de datos compartida mediante la creación de una lista enlazada donde cada nodo representa la operación que se desea realizar. Luego, CAS se usa para cambiar los punteros en la lista vinculada 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 deberán volver a intentarlo. Luego, cada proceso puede mantener una copia local de la estructura de datos y, al atravesar la lista vinculada, puede realizar cada operación de la lista en su copia local.

Soluciones de software

Además de las soluciones compatibles con hardware, existen algunas soluciones de software que utilizan la espera ocupada para lograr la exclusión mutua. Ejemplos incluyen:

• El algoritmo de Dekker
• El algoritmo de Peterson
• algoritmo de panadería de Lamport
• El algoritmo de Szymański
• algoritmo de panadería blanco-negro de Taubenfeld
• El algoritmo de Maekawa

Estos algoritmos no funcionan si se utiliza la ejecución desordenada en la plataforma que los ejecuta. Los programadores tienen que especificar un orden estricto en las operaciones de memoria dentro de un hilo.

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 usa la biblioteca de bloqueo del sistema operativo y un subproceso intenta adquirir un bloqueo ya adquirido, el sistema operativo podría suspender el subproceso mediante un cambio de contexto e intercambiarlo con 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 se pueda ejecutar. 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 spinlocks son una opción aceptable. solución (solo para esa situación).

Atado al problema de exclusión mutua

Un registro de pruebas binarias es suficiente para proporcionar la solución libre de bloqueo al problema de exclusión mutua. Pero una solución construida con un registro de testículos puede llevar a la inanición de algunos procesos que se encuentran atrapados en la sección de prueba. De hecho, Ω Ω ()n){displaystyle Omega ({sqrt {n}}} distintos estados de memoria son necesarios para evitar el bloqueo. Para evitar la espera sin límites, n distintos estados de memoria son necesarios.

Exclusión mutua recuperable

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 error mientras se ejecuta un proceso dentro de la sección crítica. Sin embargo, en realidad tales fallas pueden ser un lugar común. Por ejemplo, una pérdida repentina de energía o una interconexión defectuosa puede causar que un proceso en una sección crítica experimente un error irrecuperable o que no pueda continuar. Si ocurre una falla de este tipo, los algoritmos de exclusión mutua convencionales que no toleran fallas pueden bloquearse o fallar en las propiedades clave de actividad. Para hacer frente a este problema, se han propuesto varias soluciones que utilizan mecanismos de recuperación de fallos.

Tipos de dispositivos de exclusión mutua

Las soluciones explicadas anteriormente se pueden usar para construir las primitivas de sincronización a continuación:

• Locks (mutexes)
• Lectores – bloquea el escritor
• Cerraduras recuperadas
• Semaphores
• Monitores
• Mensaje que pasa
• Tuple space

Muchas formas de exclusión mutua tienen efectos secundarios. Por ejemplo, los semáforos clásicos permiten interbloqueos, en los que un proceso obtiene un semáforo, otro proceso obtiene un segundo semáforo y luego ambos esperan hasta que se libera el otro semáforo. Otros efectos secundarios comunes incluyen el hambre, en el que un proceso nunca obtiene suficientes recursos para ejecutarse hasta su finalización; inversión de prioridad, en la que un subproceso de mayor prioridad espera un subproceso de menor prioridad; y latencia alta, en la que la respuesta a las interrupciones no es rápida.

Gran parte de la investigación tiene como objetivo eliminar los efectos anteriores, a menudo con el objetivo de garantizar un progreso sin bloqueos. No se conoce ningún esquema perfecto. El bloqueo de llamadas al sistema solía dormir un proceso completo. Hasta que dichas llamadas se volvieron seguras para subprocesos, no había un mecanismo adecuado para dormir un solo subproceso dentro de un proceso (ver sondeo).