Exclusión mutua

En informática , la exclusión mutua es una propiedad del control de concurrencia , que se implementa para prevenir condiciones de carrera . Consiste en el requisito de que un hilo de ejecución nunca acceda a una sección crítica mientras otro hilo de ejecución concurrente ya esté accediendo a dicha sección crítica, que se refiere a un intervalo de tiempo durante el cual un hilo de ejecución accede a un recurso compartido o a memoria compartida .

El recurso compartido es un objeto de datos que dos o más subprocesos concurrentes intentan modificar (se permiten dos operaciones de lectura concurrentes, pero no dos operaciones de escritura concurrentes ni una lectura y una escritura, ya que esto genera inconsistencia de 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/subproceso puede acceder o modificar el mismo objeto hasta que el primer proceso haya terminado de escribir en él [sección crítica] y lo haya liberado para que otros procesos puedan leerlo 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 fundamental 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 sencillo 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 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 nodo siguiente (en otras palabras, si se elimina el nodo $i , entonces el puntero$ siguiente 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 dicha lista enlazada se comparte entre múltiples hilos de ejecución, dos hilos de ejecución pueden intentar eliminar dos nodos diferentes simultáneamente, un hilo de ejecución cambiando el puntero siguiente del nodo $i$ $- 1$ para que apunte al nodo $i$ $+ 1$ , mientras que otro hilo de ejecución cambia el puntero siguiente del nodo $i$ para que apunte al nodo $i$ $+ 2$ . Aunque ambas operaciones de eliminación se completan con éxito, no se alcanza el estado deseado de la lista enlazada: el nodo $i$ $+ 1$ permanece en la lista, porque el puntero next del nodo $i$ $- 1$ apunta al nodo $i$ $+ 1$ .

Este problema (denominado condición de carrera ) puede evitarse 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 para referirse a la escritura simultánea de una dirección de memoria por un hilo mientras que dicha dirección de memoria está siendo manipulada o leída por uno o más hilos.

Descripción del problema

El problema que aborda la exclusión mutua es el de compartir recursos: ¿cómo puede un sistema de software controlar el acceso de múltiples procesos a un recurso compartido, cuando cada proceso necesita el control exclusivo de dicho recurso mientras realiza su trabajo? La solución de exclusión mutua permite que el recurso compartido esté disponible únicamente mientras el proceso se encuentra en un segmento de código específico llamado sección crítica . Controla el acceso al recurso compartido controlando la ejecución mutua de la parte del programa donde se utilizaría dicho recurso.

Una solución exitosa a este problema debe tener al menos estas dos propiedades:

Debe implementar la exclusión mutua : solo un proceso puede estar en la sección crítica a la vez.
Debe estar libre de interbloqueos : si hay procesos que intentan entrar en la sección crítica, uno de ellos debe poder hacerlo con éxito, siempre que ningún proceso permanezca permanentemente en la sección crítica.

La ausencia de bloqueos mutuos puede ampliarse para implementar una o ambas de estas propiedades:

La ausencia de bloqueos garantiza que cualquier proceso que desee acceder a la sección crítica podrá hacerlo eventualmente. Esto difiere de la prevención de interbloqueos , que requiere que algún proceso en espera pueda acceder a la sección crítica, pero no que todos los procesos tengan su turno. Si dos procesos intercambian continuamente un recurso entre ellos, un tercer proceso podría quedar bloqueado y sufrir escasez de recursos , incluso si el sistema no está en interbloqueo. Si un sistema está libre de bloqueos, garantiza que todos los procesos puedan tener su turno en algún momento.
Una propiedad de espera k-limitada proporciona un compromiso más preciso que la ausencia de bloqueo. La ausencia de bloqueo garantiza que cada proceso pueda acceder a la sección crítica eventualmente; no ofrece ninguna garantía sobre cuánto durará la espera. En la práctica, un proceso podría ser superado un número arbitrario o ilimitado de veces por otros procesos de mayor prioridad antes de que le llegue su turno. Bajo una propiedad de espera k- limitada, cada proceso tiene un tiempo máximo de espera finito. Esto funciona estableciendo un límite al número de veces que otros procesos pueden interrumpir la cola, de modo que ningún proceso pueda entrar en la sección crítica más de k veces mientras otro está esperando. ^{[ 4 ]}

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 ]}

Sección no crítica: La operación se encuentra fuera de la sección crítica; el proceso no está utilizando ni solicitando el recurso compartido.

Intentando: El proceso intenta acceder a la sección crítica.

Sección crítica: El proceso tiene permiso para acceder al recurso compartido en esta sección.

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

Si un proceso desea acceder a la sección crítica, primero debe ejecutar la sección de prueba y esperar hasta obtener acceso a ella. Una vez que el proceso ha ejecutado su sección crítica y ha terminado de usar los recursos compartidos, debe ejecutar la sección de salida para liberarlos y que otros procesos puedan utilizarlos. Posteriormente, el proceso regresa a su sección no crítica.

Imponer la exclusión mutua

Soluciones de hardware

En sistemas monoprocesador , la solución más simple 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 así que un proceso sea interrumpido ). Si bien esta solución es efectiva, conlleva muchos problemas. Si una sección crítica es larga, el reloj del sistema se desfasará cada vez que se ejecute una sección crítica porque la interrupción del temporizador ya no se atiende, por lo que el seguimiento del tiempo es imposible 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 activa es eficaz tanto para sistemas monoprocesador como multiprocesador . El uso de memoria compartida y una instrucción atómica de prueba y establecimiento garantizan la exclusión mutua. Un proceso puede realizar una prueba y establecer en una ubicación de la memoria compartida, y dado que la operación es atómica, solo un proceso puede establecer el indicador a la vez. Cualquier proceso que no logre establecer el indicador puede continuar con otras tareas e intentarlo de nuevo más tarde, liberar el procesador a otro proceso e intentarlo de nuevo más tarde, o continuar en un bucle mientras comprueba el indicador hasta que logre adquirirlo. La interrupción sigue siendo 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 varias operaciones atómicas para proporcionar exclusión mutua de estructuras de datos; la más destacada es la operación de comparación e intercambio (CAS). CAS permite lograr la 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 deseada. CAS se utiliza para modificar los punteros de la lista enlazada ^{[ 6 ]} durante la inserción de un nuevo nodo. Solo un proceso puede completar con éxito su operación CAS; todos los demás procesos que intenten agregar un nodo simultáneamente deberán intentarlo de nuevo. Cada proceso puede mantener una copia local de la estructura de datos y, al recorrer la lista enlazada, realizar cada operación en su copia local.

Soluciones de software

Además de las soluciones con soporte de hardware, existen algunas soluciones de software que utilizan la espera activa para lograr la exclusión mutua. Algunos ejemplos son:

El algoritmo de Dekker
El algoritmo de Peterson
Algoritmo de panadería de Lamport ^{[ 7 ]}
El algoritmo de Szymański
El algoritmo de panadería en blanco y negro de Taubenfeld ^{[ 2 ]}
El algoritmo de Maekawa

Estos algoritmos no funcionan si se utiliza la 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 multihilo del sistema operativo , que puede aprovechar el soporte de hardware cuando esté disponible, pero recurrir a mecanismos de software cuando sea necesario. Por ejemplo, cuando se utiliza la función de bloqueo del sistema operativo y un hilo intenta adquirir un bloqueo que ya está en posesión, el sistema operativo puede suspender el hilo mediante un cambio de contexto y programar otro hilo ejecutable, o poner el procesador en un estado de bajo consumo si no hay ningún otro hilo disponible para ejecutarse. Como resultado, la mayoría de las técnicas modernas de exclusión mutua buscan reducir la latencia y la espera activa mediante el uso de colas y cambios de contexto. Sin embargo, si la sobrecarga de suspender y posteriormente restaurar un hilo es demostrablemente mayor que el tiempo que el hilo pasaría esperando a que el bloqueo esté disponible en un escenario específico, entonces los spinlocks pueden ser una solución aceptable en ese contexto. ^{[ 9 ]}^{[ 10 ]}

Límite en el problema de exclusión mutua

Un registro binario de prueba y establecimiento es suficiente para proporcionar la solución sin interbloqueos al problema de exclusión mutua. Pero una solución construida con un registro de prueba y establecimiento puede posiblemente conducir a la inanición de algunos procesos que quedan atrapados en la sección de intentos. ^{[ 4 ]} De hecho, $\Omega ({\sqrt {n}})$ Se requieren estados de memoria distintos para evitar el bloqueo. Para evitar la espera ilimitada, se requieren n estados de memoria distintos. ^{[ 11 ]}

Exclusión mutua recuperable

La mayoría de los algoritmos de exclusión mutua se diseñan bajo el supuesto de que no se produce ningún fallo mientras un proceso se ejecuta dentro de la sección crítica. Sin embargo, en la realidad, tales fallos pueden ser frecuentes. Por ejemplo, una pérdida repentina de energía o una interconexión defectuosa podrían provocar que un proceso en una sección crítica experimente un error irrecuperable o que no pueda continuar. Si se produce tal fallo, los algoritmos de exclusión mutua convencionales, que no toleran fallos, podrían bloquearse o no cumplir con las propiedades clave de vivacidad. Para abordar este problema, se han propuesto varias soluciones que utilizan mecanismos de recuperación ante fallos. ^{[ 12 ]}

Tipos de dispositivos de exclusión mutua

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

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 ambos esperan hasta que se libere el otro. Otros efectos secundarios comunes incluyen la inanición , en la que un proceso nunca obtiene recursos suficientes para completarse; la inversión de prioridad , en la que un hilo de mayor prioridad espera a uno de menor prioridad; y la alta latencia, en la que la respuesta a las interrupciones no es inmediata.

Gran parte de la investigación se centra en eliminar los efectos mencionados, 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 suspender un proceso completo. Hasta que dichas llamadas se volvieron seguras para subprocesos , no existía un mecanismo adecuado para suspender un solo subproceso dentro de un proceso (véase sondeo ). ^{[ 13 ]}

Véase también

Referencias

↑ Dijkstra, EW (1965). "Solución de un problema en el control de programación concurrente" . Communications of the ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID 19357737 .
1 2 Taubenfeld, "El algoritmo de la panadería en blanco y negro" . En Actas de la 18.ª conferencia internacional sobre computación distribuida, DISC 2004. Vol. 18, 56–70, 2004.
↑ "Premio al artículo influyente de PODC: 2002" , Simposio de ACM sobre principios de computación distribuida , consultado el 24 de agosto de 2009.
1 2 Attiya, Hagit ; Welch, Jennifer (25 de marzo de 2004). Computación distribuida: fundamentos, simulaciones y temas avanzados . John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.
↑ Lamport, Leslie (26 de junio de 2000), "El problema de la exclusión mutua, parte II: planteamiento y soluciones" (PDF) , Journal of the Association for Computing Machinery , 33 (2): 313–348 , doi : 10.1145/5383.5384 , S2CID 12012739
↑ Harris, Timothy L. (2001). "Una implementación pragmática de listas enlazadas sin bloqueo" (PDF) . Computación distribuida . Notas de clase en ciencias de la computación. 2180 : 300–314 . doi : 10.1007/3-540-45414-4_21 . ISBN 978-3-540-42605-9Consultado el 1 de diciembre de 2022 .
↑ Lamport, Leslie (agosto de 1974). "Una nueva solución al problema de programación concurrente de Dijkstra" . Communications of the ACM . 17 (8): 453– 455. doi : 10.1145/361082.361093 . S2CID 8736023 .
↑ Holzmann, Gerard J.; Bosnacki, Dragan (1 de octubre de 2007). "El diseño de una extensión multinúcleo del verificador de modelos SPIN" ( PDF) . IEEE Transactions on Software Engineering . 33 (10): 659– 674. doi : 10.1109/TSE.2007.70724 . S2CID 9080331. Archivado (PDF) del original el 9 de octubre de 2022.
↑ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2018). Conceptos de sistemas operativos (10.ª ed.). Wiley. págs. 233–239 . ISBN 978-1119320913.
↑ Herlihy, Maurice ; Shavit, Nir (2012). El arte de la programación multiprocesador (2.ª ed.). Morgan Kaufmann. págs. 11–15 . ISBN 978-0123973375.
↑ Burns, James E.; Paul Jackson, Nancy A. Lynch (enero de 1982), "Requisitos de datos para la implementación de la exclusión mutua de N procesos utilizando una única variable compartida" (PDF) , Journal of the Association for Computing Machinery , 33 ( 2): 313–348
↑ Golab, Wojciech; Ramaraju, Aditya (julio de 2016), "Exclusión mutua recuperable" , Actas del Simposio ACM de 2016 sobre Principios de Computación Distribuida , págs. 65–74 , doi : 10.1145/2933057.2933087 , ISBN 9781450339643, S2CID 8621532
↑ Blieberger, Johann; Burgstaller, Bernd (2018), Casimiro, António; Ferreira, Pedro M. (eds.), "Sincronización segura sin bloqueo en Ada2x" , Tecnologías de software confiables – Ada-Europe 2018 , vol. 10873, Cham: Springer International Publishing, págs. 53 a 69, doi : 10.1007/978-3-319-92432-8_4 , ISBN 978-3-319-92431-1Consultado el 23 de junio de 2026.{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

Lecturas adicionales

Michel Raynal: Algoritmos de exclusión mutua , MIT Press, ISBN 0-262-18119-3
Sunil R. Das, Pradip K. Srimani: Algoritmos de exclusión mutua distribuidos , IEEE Computer Society, ISBN 0-8186-3380-8
Thomas W. Christopher, George K. Thiruvathukal: Plataformas informáticas Java de alto rendimiento , Prentice Hall, ISBN 0-13-016164-0
Gadi Taubenfeld, Algoritmos de sincronización y programación concurrente , Pearson/Prentice Hall, ISBN 0-13-197259-6

Enlaces externos

Temas comunes: Explicación de los hilos POSIX: Las pequeñas cosas llamadas mutexes " por Daniel Robbins
Red de Petri de exclusión mutua en Wayback Machine (archivada el 2 de junio de 2016)
Exclusión mutua con cerraduras: una introducción
Variantes de exclusión mutua en OpenMP
El algoritmo de la panadería en blanco y negro

[1] Dijkstra, EW (1965). "Solución de un problema en el control de programación concurrente" . Communications of the ACM . 8 (9): 569. doi : 10.1145/365559.365617 . S2CID 19357737 .

[Taubenfeld:2004-2] 1 2 Taubenfeld, "El algoritmo de la panadería en blanco y negro" . En Actas de la 18.ª conferencia internacional sobre computación distribuida, DISC 2004. Vol. 18, 56–70, 2004.

[3] "Premio al artículo influyente de PODC: 2002" , Simposio de ACM sobre principios de computación distribuida , consultado el 24 de agosto de 2009.

[Distributed_computing:_fundamentals,_simulations,_and_advanced_topics-4] 1 2 Attiya, Hagit ; Welch, Jennifer (25 de marzo de 2004). Computación distribuida: fundamentos, simulaciones y temas avanzados . John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.

[5] Lamport, Leslie (26 de junio de 2000), "El problema de la exclusión mutua, parte II: planteamiento y soluciones" (PDF) , Journal of the Association for Computing Machinery , 33 (2): 313–348 , doi : 10.1145/5383.5384 , S2CID 12012739

[6] Harris, Timothy L. (2001). "Una implementación pragmática de listas enlazadas sin bloqueo" (PDF) . Computación distribuida . Notas de clase en ciencias de la computación. 2180 : 300–314 . doi : 10.1007/3-540-45414-4_21 . ISBN 978-3-540-42605-9Consultado el 1 de diciembre de 2022 .

[7] Lamport, Leslie (agosto de 1974). "Una nueva solución al problema de programación concurrente de Dijkstra" . Communications of the ACM . 17 (8): 453– 455. doi : 10.1145/361082.361093 . S2CID 8736023 .

[8] Holzmann, Gerard J.; Bosnacki, Dragan (1 de octubre de 2007). "El diseño de una extensión multinúcleo del verificador de modelos SPIN" ( PDF) . IEEE Transactions on Software Engineering . 33 (10): 659– 674. doi : 10.1109/TSE.2007.70724 . S2CID 9080331. Archivado (PDF) del original el 9 de octubre de 2022.

[9] Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2018). Conceptos de sistemas operativos (10.ª ed.). Wiley. págs. 233–239 . ISBN 978-1119320913.

[10] Herlihy, Maurice ; Shavit, Nir (2012). El arte de la programación multiprocesador (2.ª ed.). Morgan Kaufmann. págs. 11–15 . ISBN 978-0123973375.

[11] Burns, James E.; Paul Jackson, Nancy A. Lynch (enero de 1982), "Requisitos de datos para la implementación de la exclusión mutua de N procesos utilizando una única variable compartida" (PDF) , Journal of the Association for Computing Machinery , 33 ( 2): 313–348

[12] Golab, Wojciech; Ramaraju, Aditya (julio de 2016), "Exclusión mutua recuperable" , Actas del Simposio ACM de 2016 sobre Principios de Computación Distribuida , págs. 65–74 , doi : 10.1145/2933057.2933087 , ISBN 9781450339643, S2CID 8621532

[13] Blieberger, Johann; Burgstaller, Bernd (2018), Casimiro, António; Ferreira, Pedro M. (eds.), "Sincronización segura sin bloqueo en Ada2x" , Tecnologías de software confiables – Ada-Europe 2018 , vol. 10873, Cham: Springer International Publishing, págs. 53 a 69, doi : 10.1007/978-3-319-92432-8_4 , ISBN 978-3-319-92431-1Consultado el 23 de junio de 2026.{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[ 1 ]

[ 3 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]