Estado en el que los miembros se bloquean entre sí
Ambos procesos necesitan recursos para continuar con la ejecución. P1 requiere el recurso adicional R1 y está en posesión del recurso R2 , P2 requiere el recurso adicional R2 y está en posesión de R1 ; ninguno de los procesos puede continuar.Cuatro procesos (líneas azules) compiten por un recurso (círculo gris), siguiendo una política de derecha antes que izquierda. Se produce un punto muerto cuando todos los procesos bloquean el recurso simultáneamente (líneas negras). El punto muerto se puede resolver rompiendo la simetría.
En la computación concurrente , un punto muerto es cualquier situación en la que ningún miembro de algún grupo de entidades puede continuar porque cada uno espera a que otro miembro, incluido él mismo, realice una acción, como enviar un mensaje o, más comúnmente, liberar un bloqueo . [1] Los interbloqueos son un problema común en sistemas multiprocesamiento , computación paralela y sistemas distribuidos , porque en estos contextos los sistemas suelen utilizar bloqueos de software o hardware para arbitrar recursos compartidos e implementar la sincronización de procesos . [2]
En un sistema operativo , se produce un punto muerto cuando un proceso o subproceso entra en estado de espera porque un recurso solicitado del sistema está retenido por otro proceso en espera, que a su vez está esperando otro recurso retenido por otro proceso en espera. [3] Si un proceso permanece indefinidamente incapaz de cambiar su estado porque los recursos solicitados por él están siendo utilizados por otro proceso que está esperando, entonces se dice que el sistema está en un punto muerto. [4]
En un sistema de comunicaciones , los interbloqueos se producen principalmente debido a la pérdida o corrupción de señales más que a la disputa por los recursos. [5]
Dos procesos compitiendo por dos recursos en orden opuesto.
Se realiza un único proceso.
El proceso posterior tiene que esperar.
Se produce un punto muerto cuando el primer proceso bloquea el primer recurso al mismo tiempo que el segundo proceso bloquea el segundo recurso.
El punto muerto se puede resolver cancelando y reiniciando el primer proceso.
Condiciones individualmente necesarias y conjuntamente suficientes para el estancamiento
Una situación de interbloqueo en un recurso sólo puede surgir si todas las condiciones siguientes ocurren simultáneamente en un sistema: [6]
Exclusión mutua : al menos un recurso debe mantenerse en un modo que no se pueda compartir (asumimos que un recurso podría tener varias instancias); es decir, sólo un proceso a la vez puede utilizar el recurso. [7] De lo contrario, no se impediría que los procesos utilicen el recurso cuando sea necesario. Sólo un proceso puede utilizar el recurso en un instante dado. [8]
Retener y esperar o retención de recursos: un proceso actualmente retiene al menos un recurso y solicita recursos adicionales que están retenidos por otros procesos.
Sin preferencia : un recurso sólo puede ser liberado voluntariamente por el proceso que lo posee.
Espera circular: cada proceso debe estar esperando un recurso que está retenido por otro proceso, que a su vez está esperando que el primer proceso libere el recurso. En general, hay un conjunto de procesos de espera, P = { P 1 , P 2 , ..., P N }, de modo que P 1 está esperando un recurso retenido por P 2 , P 2 está esperando un recurso retenido por P 3 y así sucesivamente hasta que PN esté esperando un recurso retenido por P 1 . [4] [9]
Estas cuatro condiciones se conocen como condiciones de Coffman por su primera descripción en un artículo de 1971 de Edward G. Coffman, Jr. [9]
Si bien estas condiciones son suficientes para producir un punto muerto en sistemas de recursos de instancia única, sólo indican la posibilidad de un punto muerto en sistemas que tienen múltiples instancias de recursos. [10]
Manejo de interbloqueos
La mayoría de los sistemas operativos actuales no pueden evitar los puntos muertos. [11] Cuando se produce un punto muerto, diferentes sistemas operativos responden de diferentes maneras no estándar. La mayoría de los enfoques funcionan evitando que ocurra una de las cuatro condiciones de Coffman , especialmente la cuarta. [12] Los principales enfoques son los siguientes.
Ignorando el punto muerto
En este enfoque, se supone que nunca ocurrirá un punto muerto. Esta también es una aplicación del algoritmo de avestruz . [12] [13] Este enfoque fue utilizado inicialmente por MINIX y UNIX . [9] Esto se utiliza cuando los intervalos de tiempo entre la aparición de interbloqueos son grandes y la pérdida de datos que se produce cada vez es tolerable.
Es posible ignorar los puntos muertos de forma segura si se demuestra formalmente que nunca ocurren. Un ejemplo es el marco RTIC. [14]
Detección
Bajo la detección de interbloqueo, se permite que se produzcan interbloqueos. Luego se examina el estado del sistema para detectar que se ha producido un punto muerto y posteriormente se corrige. Se emplea un algoritmo que rastrea la asignación de recursos y los estados de los procesos, retrocede y reinicia uno o más de los procesos para eliminar el punto muerto detectado. Es fácil detectar un punto muerto que ya se ha producido, ya que el programador de recursos del sistema operativo conoce los recursos que cada proceso ha bloqueado y/o solicitado actualmente. [13]
Una vez que se detecta un punto muerto, se puede corregir utilizando uno de los siguientes métodos: [ cita necesaria ]
Terminación del proceso: uno o más procesos involucrados en el punto muerto pueden ser abortados. Se podría optar por abortar todos los procesos competitivos involucrados en el punto muerto. Esto garantiza que el punto muerto se resuelva con certeza y rapidez. [ cita necesaria ] Pero el gasto es alto ya que se perderán cálculos parciales. O bien, se podría optar por abortar un proceso a la vez hasta que se resuelva el punto muerto. Este enfoque tiene una gran sobrecarga porque después de cada aborto, un algoritmo debe determinar si el sistema todavía está en punto muerto. [ cita necesaria ] Se deben considerar varios factores al elegir un candidato para la terminación, como la prioridad y la antigüedad del proceso. [ cita necesaria ]
Prioridad de recursos: los recursos asignados a varios procesos pueden ser priorizados y asignados sucesivamente a otros procesos hasta que se rompa el punto muerto. [15] [ verificación fallida ]
Prevención
(A) Dos procesos compitiendo por un recurso, siguiendo una política de orden de llegada. (B) El punto muerto ocurre cuando ambos procesos bloquean el recurso simultáneamente. (C) El punto muerto se puede resolver rompiendo la simetría de las cerraduras. (D) El punto muerto se puede evitar rompiendo la simetría del mecanismo de bloqueo.
La prevención de interbloqueo funciona impidiendo que se produzca una de las cuatro condiciones de Coffman.
Eliminar la condición de exclusión mutua significa que ningún proceso tendrá acceso exclusivo a un recurso. Esto resulta imposible para los recursos que no se pueden poner en cola . Pero incluso con recursos en cola, el punto muerto aún podría ocurrir. Los algoritmos que evitan la exclusión mutua se denominan algoritmos de sincronización sin bloqueo .
Las condiciones de retención y espera o retención de recursos pueden eliminarse exigiendo a los procesos que soliciten todos los recursos que necesitarán antes de iniciar (o antes de embarcarse en un conjunto particular de operaciones). Este conocimiento adelantado es muchas veces difícil de satisfacer y, en cualquier caso, supone un uso ineficiente de los recursos. Otra forma es exigir que los procesos soliciten recursos sólo cuando no los tenga; Primero, deben liberar todos los recursos que tienen actualmente antes de solicitar todos los recursos que necesitarán desde cero. Esto también suele resultar poco práctico. Esto es así porque los recursos pueden asignarse y permanecer sin utilizarse durante largos períodos. Además, un proceso que requiere un recurso popular puede tener que esperar indefinidamente, ya que dicho recurso siempre puede asignarse a algún proceso, lo que resulta en una escasez de recursos . [16] (Estos algoritmos, como la serialización de tokens , se conocen como algoritmos de todo o nada ).
La condición de no preferencia también puede ser difícil o imposible de evitar, ya que un proceso debe poder tener un recurso durante un cierto período de tiempo, o el resultado del procesamiento puede ser inconsistente o puede ocurrir una paliza . Sin embargo, la incapacidad de hacer cumplir la preferencia puede interferir con un algoritmo de prioridad . La preferencia de un recurso "bloqueado" generalmente implica una reversión y debe evitarse ya que es muy costoso en términos generales. Los algoritmos que permiten la preferencia incluyen algoritmos sin bloqueo y sin espera y control de concurrencia optimista . Si un proceso contiene algunos recursos y solicita otros recursos que no se le pueden asignar inmediatamente, la condición puede eliminarse liberando todos los recursos actualmente retenidos de ese proceso.
La condición final es la condición de espera circular . Los enfoques que evitan esperas circulares incluyen deshabilitar las interrupciones durante las secciones críticas y usar una jerarquía para determinar un orden parcial de los recursos. Si no existe una jerarquía obvia, incluso la dirección de memoria de los recursos se ha utilizado para determinar el orden y los recursos se solicitan en orden creciente de la enumeración. [4] También se puede utilizar la solución de Dijkstra .
Evitar puntos muertos
De manera similar a la prevención de interbloqueos, el enfoque para evitar interbloqueos garantiza que no se producirá un interbloqueo en un sistema. El término "evitar puntos muertos" parece estar muy cerca de "prevención de puntos muertos" en un contexto lingüístico, pero son muy diferentes en el contexto del manejo de puntos muertos. La evitación de interbloqueos no impone ninguna condición como se ve en la prevención, pero aquí cada solicitud de recurso se analiza cuidadosamente para ver si se puede cumplir de manera segura sin causar un interbloqueo.
Para evitar interbloqueos es necesario que el sistema operativo reciba por adelantado información adicional sobre qué recursos solicitará y utilizará un proceso durante su vida útil. El algoritmo para evitar interbloqueos analiza todas y cada una de las solicitudes examinando que no hay posibilidad de que se produzca un interbloqueo en el futuro si se asigna el recurso solicitado. El inconveniente de este enfoque es que requiere información previa sobre cómo se solicitarán los recursos en el futuro. Uno de los algoritmos para evitar interbloqueos más utilizados es el algoritmo de Banker . [17]
bloqueo vivo
Un livelock es similar a un interbloqueo, excepto que los estados de los procesos involucrados en el livelock cambian constantemente entre sí, sin que ninguno progrese.
El término fue acuñado por Edward A. Ashcroft en un artículo de 1975 [18] en relación con un examen de los sistemas de reserva de aerolíneas. [19] Livelock es un caso especial de escasez de recursos ; la definición general sólo establece que un proceso específico no está progresando. [20]
Livelock es un riesgo con algunos algoritmos que detectan y se recuperan del punto muerto . Si más de un proceso toma acción, el algoritmo de detección de interbloqueo se puede activar repetidamente. Esto se puede evitar garantizando que sólo un proceso (elegido arbitrariamente o por prioridad) entre en acción. [21]
Los puntos muertos distribuidos se pueden detectar construyendo un gráfico de espera global a partir de gráficos de espera locales en un detector de puntos muertos o mediante un algoritmo distribuido como la persecución de bordes.
Los interbloqueos fantasma son interbloqueos que se detectan erróneamente en un sistema distribuido debido a retrasos internos del sistema, pero que en realidad no existen. Por ejemplo, si un proceso libera un recurso R1 y emite una solicitud para R2 , y el primer mensaje se pierde o se retrasa, un coordinador (detector de interbloqueos) podría concluir falsamente un interbloqueo (si la solicitud de R2 mientras se tiene R1 causaría un punto muerto).
^ Coulouris, George (2012). Conceptos y diseño de sistemas distribuidos . Pearson. pag. 716.ISBN 978-0-273-76059-7.
^ Padua, David (2011). Enciclopedia de computación paralela. Saltador. pag. 524.ISBN9780387097657. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Felipe, Bernardo; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Sonríe, Marc; Jorge, Tomás; Sarín, Vivek; Jann, Joefon (2011). "Puntos muertos". Enciclopedia de Computación Paralela . Boston, MA: Springer EE. UU. págs. 524–527. doi :10.1007/978-0-387-09766-4_282. ISBN978-0-387-09765-7. S2CID 241456017. Un punto muerto es una condición que puede ocurrir en un sistema compuesto por múltiples procesos que pueden acceder a recursos compartidos. Se dice que se produce un punto muerto cuando dos o más procesos esperan entre sí para liberar un recurso. Ninguno de los procesos puede avanzar.
^ abc Silberschatz, Abraham (2006). Principios del sistema operativo (7ª ed.). Wiley-India. pag. 237.ISBN9788126509621. Archivado desde el original el 25 de enero de 2022 . Consultado el 16 de octubre de 2020 .
^ Schneider, G. Michael (2009). Invitación a Ciencias de la Computación. Aprendizaje Cengage. pag. 271.ISBN978-0324788594. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 239.ISBN9788126509621. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ Conceptos del sistema operativo . Wiley. 2012. pág. 319.ISBN978-1-118-06333-0.
^ "ECS 150 primavera de 1999: cuatro condiciones necesarias y suficientes para un punto muerto". nob.cs.ucdavis.edu . Archivado desde el original el 29 de abril de 2018 . Consultado el 29 de abril de 2018 .
^ a b C Shibu, K. (2009). Introducción a los sistemas integrados (1ª ed.). Educación de Tata McGraw-Hill. pag. 446.ISBN9780070145894. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ "Sistemas operativos: puntos muertos". www.cs.uic.edu . Archivado desde el original el 28 de mayo de 2020 . Consultado el 25 de abril de 2020 . Si una categoría de recursos contiene más de una instancia, la presencia de un ciclo en el gráfico de asignación de recursos indica la posibilidad de un punto muerto, pero no lo garantiza. Considere, por ejemplo, las Figuras 7.3 y 7.4 a continuación:
^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 237.ISBN9788126509621. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ ab Stuart, Brian L. (2008). Principios de los sistemas operativos (1ª ed.). Aprendizaje Cengage. pag. 446.ISBN9781418837693. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ ab Tanenbaum, Andrew S. (1995). Sistemas operativos distribuidos (1ª ed.). Educación Pearson. pag. 117.ISBN9788177581799. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ "Prefacio: simultaneidad impulsada por interrupciones en tiempo real". Archivado desde el original el 18 de septiembre de 2020 . Consultado el 1 de octubre de 2020 .
^ "Centro de conocimiento de IBM". www.ibm.com . Archivado desde el original el 19 de marzo de 2017 . Consultado el 29 de abril de 2018 .
^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 244.ISBN9788126509621. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
^ "Algoritmos para evitar puntos muertos en el sistema operativo (SO)". Mente Electrónica . 26 de enero de 2022.
^ Ashcroft, EA (1975). "Demostrar afirmaciones sobre programas paralelos". Revista de Ciencias de la Computación y de Sistemas . 10 : 110-135. doi : 10.1016/S0022-0000(75)80018-3 .
^ Kwong, YS (1979). "Sobre la ausencia de livelocks en programas paralelos". Semántica de la computación concurrente . Apuntes de conferencias sobre informática. vol. 70, págs. 172-190. doi :10.1007/BFb0022469. ISBN3-540-09511-X.
^ Anderson, James H .; Yong-jik Kim (2001). "Exclusión mutua de memoria compartida: principales tendencias de investigación desde 1986". Archivado desde el original el 25 de mayo de 2006.
^ Zöbel, Dieter (octubre de 1983). "El problema del punto muerto: una bibliografía clasificatoria". Revisión de los sistemas operativos ACM SIGOPS . 17 (4): 6-15. doi : 10.1145/850752.850753 . ISSN 0163-5980. S2CID 38901737.
Lectura adicional
Kaveh, Nima; Emmerich, Wolfgang. "Detección de puntos muertos en sistemas de objetos distribuidos" (PDF) . Londres: University College de Londres. {{cite journal}}: Citar diario requiere |journal=( ayuda )
Bensalem, Saddek; Fernández, Jean-Claude; Havelund, Klaus; Mounier, Laurent (2006). "Confirmación de potenciales de interbloqueo detectados mediante análisis en tiempo de ejecución". Actas del taller de 2006 sobre sistemas paralelos y distribuidos: pruebas y depuración . ACM. págs. 41–50. CiteSeerX 10.1.1.431.3757 . doi :10.1145/1147403.1147412. ISBN 978-1595934147. S2CID 2544690.
Coffman, Edward G. Jr.; Elphick, Michael J.; Shoshani, Arie (1971). "Estancamientos del sistema" (PDF) . Encuestas de Computación ACM . 3 (2): 67–78. doi :10.1145/356586.356588. S2CID 15975305.
Mogul, Jeffrey C.; Ramakrishnan, KK (1997). "Eliminación del bloqueo activo de recepción en un kernel controlado por interrupciones". Transacciones ACM en sistemas informáticos . 15 (3): 217–252. CiteSeerX 10.1.1.156.667 . doi :10.1145/263326.263335. ISSN 0734-2071. S2CID 215749380.
Havender, James W. (1968). "Evitar el estancamiento en los sistemas multitarea". Revista de sistemas IBM . 7 (2): 74. doi :10.1147/sj.72.0074. Archivado desde el original el 24 de febrero de 2012 . Consultado el 27 de enero de 2009 .
Holliday, JoAnne L.; El Abbadi, Amr. "Detección distribuida de interbloqueos". Enciclopedia de Computación Distribuida . Archivado desde el original el 2 de noviembre de 2015 . Consultado el 29 de diciembre de 2004 .
Knapp, Edgar (1987). "Detección de interbloqueos en bases de datos distribuidas". Encuestas de Computación ACM . 19 (4): 303–328. CiteSeerX 10.1.1.137.6874 . doi :10.1145/45075.46163. ISSN 0360-0300. S2CID 2353246.
Ling, Yibei; Chen, Shigang; Chiang, Jason (2006). "Sobre la programación óptima de detección de interbloqueos". Transacciones IEEE en computadoras . 55 (9): 1178-1187. CiteSeerX 10.1.1.259.4311 . doi :10.1109/tc.2006.151. S2CID 7813284.
Enlaces externos
"Sincronización avanzada en subprocesos de Java" por Scott Oaks y Henry Wong
Agentes de detección de interbloqueos
DeadLock en el repositorio de patrones de Portland