Hispanopedia Wiki
Articulo de referencia

Punto muerto (informática)

Ambos procesos necesitan recursos para continuar su ejecución. P1 requiere el recurso adicional R1 y dispone del recurso R2 ; P2 requiere el recurso adicional R2 y dispone de R1...

Hispanopedia WikiContenido en espanolLectura gratuita

Ambos procesos necesitan recursos para continuar su ejecución. P1 requiere el recurso adicional R1 y dispone del recurso R2 ; P2 requiere el recurso adicional R2 y dispone 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 prioridad de derecha a izquierda. Se produce un bloqueo cuando todos los procesos bloquean el recurso simultáneamente (líneas negras). El bloqueo se puede resolver rompiendo la simetría.

En la computación concurrente , el interbloqueo es cualquier situación en la que ningún miembro de un 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 de 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 interbloqueo cuando un proceso o hilo entra en estado de espera porque un recurso del sistema solicitado está siendo utilizado por otro proceso en espera, el cual a su vez está esperando otro recurso que está siendo utilizado por otro proceso en espera. [ 3 ] Si un proceso permanece indefinidamente sin poder cambiar su estado porque los recursos que solicita están siendo utilizados por otro proceso que también está en espera, entonces se dice que el sistema está en un interbloqueo. [ 4 ]

En un sistema de comunicaciones , los bloqueos se producen principalmente debido a la pérdida o corrupción de señales, más que a la contención por los recursos. [ 5 ]

Dos procesos compitiendo por dos recursos en orden inverso.
  1. Un único proceso se lleva a cabo.
  2. El proceso posterior tendrá que esperar.
  3. Se produce un interbloqueo cuando el primer proceso bloquea el primer recurso al mismo tiempo que el segundo proceso bloquea el segundo recurso.
  4. El bloqueo se puede resolver cancelando y reiniciando el primer proceso.

Condiciones

Una situación de interbloqueo en un recurso solo puede surgir si todas las siguientes condiciones ocurren simultáneamente en un sistema: [ 6 ]

  1. Exclusión mutua : los recursos múltiples no se pueden compartir; solo un proceso a la vez puede usar cada recurso. [ 7 ] [ 8 ]
  2. Retención y espera o retención de recursos: un proceso está reteniendo actualmente al menos un recurso y solicitando recursos adicionales que están siendo retenidos por otros procesos.
  3. Sin expropiación : un recurso solo puede ser liberado voluntariamente por el proceso que lo posee.
  4. Espera circular: cada proceso debe estar esperando un recurso que está siendo retenido por otro proceso, el cual a su vez está esperando a que el primer proceso libere el recurso. En general, existe un conjunto de procesos en espera, P = { P 1 , P 2 , ..., P N }, tal 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 P N esté esperando un recurso retenido por P 1. [ 4 ] [ 9 ]

Estas cuatro condiciones se conocen como las condiciones de Coffman desde 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 interbloqueo en sistemas de recursos de instancia única, solo indican la posibilidad de interbloqueo en sistemas que tienen múltiples instancias de recursos. [ 10 ]

Manejo de bloqueos

La mayoría de los sistemas operativos actuales no pueden evitar los interbloqueos. [ 11 ] Cuando se produce un interbloqueo, los distintos sistemas operativos responden a ellos de maneras distintas y no estándar. La mayoría de los enfoques funcionan evitando que se produzca una de las cuatro condiciones de Coffman , especialmente la cuarta. [ 12 ] Los principales enfoques son los siguientes.

Ignorar el bloqueo mutuo

En este enfoque, se supone que nunca ocurrirá un interbloqueo. Esta es también una aplicación del algoritmo del avestruz . [ 12 ] [ 13 ] Este enfoque fue utilizado inicialmente por MINIX y UNIX . [ 9 ] Se utiliza cuando los intervalos de tiempo entre ocurrencias de interbloqueos son grandes y la pérdida de datos que se produce cada vez es tolerable.

Ignorar los interbloqueos puede hacerse de forma segura si se demuestra formalmente que nunca ocurren. Un ejemplo es el marco RTIC. [ 14 ]

Detección

Bajo la detección de interbloqueos, se permite que estos ocurran. Luego, se examina el estado del sistema para detectar que se ha producido un interbloqueo y, posteriormente, se corrige. Se emplea un algoritmo que rastrea la asignación de recursos y los estados de los procesos, revierte y reinicia uno o más procesos para eliminar el interbloqueo detectado. Detectar un interbloqueo que ya se ha producido es posible fácilmente, ya que el planificador de recursos del sistema operativo conoce los recursos que cada proceso ha bloqueado o que actualmente solicita. [ 13 ]

Una vez detectado un interbloqueo, se puede corregir utilizando uno de los siguientes métodos: [ 15 ]

  1. Terminación del proceso: uno o más procesos involucrados en el interbloqueo pueden ser abortados. Se podría optar por abortar todos los procesos concurrentes involucrados en el interbloqueo. Esto garantiza que el interbloqueo se resuelva con certeza y rapidez. Sin embargo, el costo 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 interbloqueo. Este enfoque tiene una sobrecarga elevada, ya que después de cada aborto un algoritmo debe determinar si el sistema aún se encuentra en interbloqueo. Se deben considerar varios factores al elegir un candidato para la terminación, como la prioridad y la antigüedad del proceso. [ 15 ]
  2. Expropiación de recursos: los recursos asignados a varios procesos pueden ser sucesivamente expropiados y asignados a otros procesos hasta que se rompa el bloqueo. [ 16 ]

Prevención

(A) Dos procesos compiten por un recurso, siguiendo una política de primero en llegar, primero en ser atendido. (B) El interbloqueo ocurre cuando ambos procesos bloquean el recurso simultáneamente. (C) El interbloqueo se puede resolver rompiendo la simetría de los bloqueos. (D) El interbloqueo se puede prevenir rompiendo la simetría del mecanismo de bloqueo.

La prevención de bloqueos funciona impidiendo que se produzca una de las cuatro condiciones de Coffman.

  • Eliminar la condición de exclusión mutua implica que ningún proceso tendrá acceso exclusivo a un recurso. Esto resulta imposible para los recursos que no se pueden almacenar en cola . Sin embargo, incluso con recursos almacenados en cola, aún podría producirse un interbloqueo. Los algoritmos que evitan la exclusión mutua se denominan algoritmos de sincronización sin bloqueo .
  • Las condiciones de espera o retención de recursos pueden eliminarse exigiendo que los procesos soliciten todos los recursos que necesitarán antes de iniciarse (o antes de emprender un conjunto particular de operaciones). Este conocimiento previo suele ser difícil de satisfacer y, en cualquier caso, supone un uso ineficiente de los recursos. Otra opción es exigir que los procesos soliciten recursos solo cuando no dispongan de ellos; primero, deben liberar todos los recursos que tengan actualmente antes de solicitar todos los recursos que necesitarán desde cero. Esto también suele ser poco práctico, ya que los recursos pueden asignarse y permanecer sin usar durante largos periodos. Además, un proceso que requiera un recurso popular puede tener que esperar indefinidamente, puesto que dicho recurso siempre puede estar asignado a algún proceso, lo que provoca escasez de recursos . [ 17 ] (Estos algoritmos, como la serialización de tokens , se conocen como algoritmos de todo o nada ).
  • La condición de no expropiación también puede ser difícil o imposible de evitar, ya que un proceso debe poder tener un recurso durante un cierto tiempo, o el resultado del procesamiento puede ser inconsistente o puede ocurrir thrashing . Sin embargo, la incapacidad de imponer la expropiación puede interferir con un algoritmo de prioridad . La expropiación de un recurso "bloqueado" generalmente implica una reversión , y debe evitarse ya que es muy costosa en términos de sobrecarga. Los algoritmos que permiten la expropiación incluyen algoritmos sin bloqueo y sin espera y control de concurrencia optimista . Si un proceso que posee algunos recursos y solicita otros recursos que no se le pueden asignar de inmediato, la condición puede eliminarse liberando todos los recursos que actualmente posee ese proceso.
  • La condición final es la condición de espera circular . Los enfoques que evitan las 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 el orden ascendente de la enumeración. [ 4 ] También se puede utilizar la solución de Dijkstra .

prevención de bloqueos

De forma similar a la prevención de interbloqueos, el enfoque de evitación de interbloqueos garantiza que no se produzcan en un sistema. Si bien el término "evitación de interbloqueos" parece muy similar a "prevención de interbloqueos" en un contexto lingüístico, son muy diferentes en el manejo de interbloqueos. La evitación de interbloqueos no impone condiciones, como ocurre en la prevención, sino que cada solicitud de recursos se analiza cuidadosamente para determinar si puede satisfacerse de forma segura sin provocar un interbloqueo.

La prevención de interbloqueos requiere que el sistema operativo reciba información adicional con antelación sobre los recursos que un proceso solicitará y utilizará durante su ejecución. El algoritmo de prevención de interbloqueos analiza cada solicitud, comprobando que no exista posibilidad de que se produzca un interbloqueo en el futuro si se asigna el recurso solicitado. La desventaja de este enfoque radica en que requiere información previa sobre cómo se solicitarán los recursos en el futuro. Uno de los algoritmos de prevención de interbloqueos más utilizados es el algoritmo del banquero . [ 18 ]

Livelock

Un bloqueo mutuo es similar a un interbloqueo, con la diferencia de que los estados de los procesos involucrados en el bloqueo mutuo cambian constantemente entre sí, sin que ninguno progrese.

El término fue acuñado por Edward A. Ashcroft en un artículo de 1975 [ 19 ] en relación con un análisis de los sistemas de reserva de aerolíneas. [ 20 ] El bloqueo es un caso especial de escasez de recursos ; la definición general solo indica que un proceso específico no está progresando. [ 21 ]

El bloqueo mutuo es un riesgo en algunos algoritmos que detectan y se recuperan de bloqueos . Si más de un proceso realiza una acción, el algoritmo de detección de bloqueos mutuos puede activarse repetidamente. Esto se puede evitar asegurando que solo un proceso (elegido arbitrariamente o por prioridad) realice la acción. [ 22 ]

Interbloqueo distribuido

Los interbloqueos distribuidos pueden ocurrir en sistemas distribuidos cuando se utilizan transacciones distribuidas o control de concurrencia .

A diferencia de los sistemas centralizados , la detección y resolución de interbloqueos distribuidos es más compleja debido a la falta de memoria compartida y la necesidad de coordinación entre los nodos. Para gestionar estos escenarios, se utilizan técnicas como grafos de espera , algoritmos distribuidos (como el seguimiento de aristas; por ejemplo, Chandy-Misra-Haas ) y prevención de interbloqueos (por ejemplo, métodos basados ​​en tiempos de espera). El reto reside en garantizar la consistencia y evitar falsos positivos o negativos debido a retrasos en la red o fallos parciales.

Los interbloqueos fantasma son bloqueos 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 solicita R2 , y el primer mensaje se pierde o se retrasa, un coordinador (detector de interbloqueos) podría concluir erróneamente que existe un interbloqueo (si la solicitud de R2 , estando disponible R1, provocara un interbloqueo).

Véase también

Referencias

  1. ↑ Coulouris, George (2012). Conceptos y diseño de sistemas distribuidos . Pearson. pág.  716. ISBN 978-0-273-76059-7.
  2. ↑ Padua, David (2011). Enciclopedia de Computación Paralela . Springer. pág. 524. ISBN  9780387097657Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  3. ↑ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel; Fossum, Tryggve; Smith, Burton; Philippe, Bernard; Sameh, Ahmed; Irigoin, François; Feautrier, Paul; Praun, Christoph von; Bocchino, Robert L.; Snir, Marc; George, Thomas; Sarin, Vivek; Jann, Joefon (2011). "Deadlocks". Encyclopedia of Parallel Computing . Boston, MA: Springer US. pp. 524–527 . doi : 10.1007/978-0-387-09766-4_282 . ISBN  978-0-387-09765-7S2CID 241456017. Un interbloqueo es una condición que puede ocurrir en un sistema compuesto por múltiples procesos que pueden acceder a recursos compartidos. Se dice que ocurre un interbloqueo cuando dos o más procesos esperan a que el otro libere un recurso. Ninguno de los procesos puede avanzar. 
  4. 1 2 3 Silberschatz, Abraham (2006). Principios de sistemas operativos (7.ª ed.). Wiley-India. pág. 237. ISBN   9788126509621Archivado del original el 25 de enero de 2022. Consultado el 16 de octubre de 2020 .
  5. ↑ Schneider, G. Michael (2009). Invitación a la informática . Cengage Learning. pág. 271. ISBN  978-0324788594Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  6. ↑ Silberschatz, Abraham (2006). Principios de sistemas operativos (7.ª ed.). Wiley-India. pág. 239. ISBN   9788126509621Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  7. ↑ Conceptos de sistemas operativos . Wiley. 2012. pág. 319. ISBN  978-1-118-06333-0.
  8. ↑ "ECS 150 Primavera 1999: Cuatro condiciones necesarias y suficientes para el bloqueo" . nob.cs.ucdavis.edu . Archivado del original el 29 de abril de 2018. Recuperado el 29 de abril de 2018 .
  9. ^ Shibu , K. (2009) . Introducción a los sistemas integrados (1ª ed.). Educación de Tata McGraw-Hill. pag. 446.ISBN​   9780070145894Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  10. ↑ "Sistemas Operativos: Interbloqueos" . www.cs.uic.edu . Archivado del 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 grafo de asignación de recursos indica la posibilidad de un interbloqueo, pero no lo garantiza. Considérense, por ejemplo, las figuras 7.3 y 7.4 a continuación:
  11. ↑ Silberschatz, Abraham (2006). Principios de sistemas operativos (7.ª ed.). Wiley-India. pág. 237. ISBN   9788126509621Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  12. 1 2 Stuart, Brian L. (2008). Principios de sistemas operativos (1.ª ed.). Cengage Learning. pág. 446. ISBN   9781418837693Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  13. 1 2 Tanenbaum, Andrew S. (1995). Sistemas operativos distribuidos (1.ª ed.). Pearson Education. pág. 117. ISBN   9788177581799Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  14. ↑ "Prefacio - Concurrencia en tiempo real impulsada por interrupciones" . Archivado del original el 18 de septiembre de 2020. Consultado el 1 de octubre de 2020 .
  15. 1 2 "6.2: Detección y prevención de interbloqueos" . Engineering LibreTexts . 22 de marzo de 2021. Recuperado el 22 de octubre de 2025 .
  16. ↑ "Centro de conocimiento de IBM" . www.ibm.com . Archivado del original el 19 de marzo de 2017. Consultado el 29 de abril de 2018 .
  17. ↑ Silberschatz, Abraham (2006). Principios de sistemas operativos (7.ª ed.). Wiley-India. pág. 244. ISBN   9788126509621Archivado del original el 18 de abril de 2021. Consultado el 16 de octubre de 2020 .
  18. ↑ "Algoritmos para evitar bloqueos en sistemas operativos (SO)" . Electronics Mind . 26 de enero de 2022.
  19. ↑ Ashcroft, EA (1975). "Proving assertions about parallel programs" . Journal of Computer and System Sciences . 10 : 110–135 . doi : 10.1016/S0022-0000(75)80018-3 .
  20. ↑ Kwong, YS (1979). "Sobre la ausencia de bloqueos en programas paralelos". Semántica de la computación concurrente . Notas de clase en ciencias de la computación. Vol. 70. págs. 172–190 . doi : 10.1007/BFb0022469 . ISBN   3-540-09511-X.
  21. ↑ Anderson, James H.; Yong-jik Kim (2001). "Exclusión mutua de memoria compartida: principales tendencias de investigación desde 1986" . Archivado del original el 25 de mayo de 2006.
  22. ↑ Zöbel, Dieter (octubre de 1983). "El problema del bloqueo mutuo: una bibliografía de clasificación" . ACM SIGOPS Operating Systems Review . 17 (4): 6– 15. doi : 10.1145/850752.850753 . ISSN 0163-5980 . S2CID 38901737 .  

Lecturas adicionales

  • Kaveh, Nima; Emmerich, Wolfgang. "Detección de interbloqueos en sistemas de objetos distribuidos" (PDF) . Actas de la 8.ª Conferencia Europea de Ingeniería de Software celebrada conjuntamente con el 9.º Simposio Internacional {ACM} {SIGSOFT} sobre Fundamentos de la Ingeniería de Software 2001, Viena, Austria, 10-14 de septiembre de 2001. ACM SIGSOFT Software Engineering Notes . ACM. doi : 10.1145/503209.503216 .
  • Bensalem, Saddek; Fernandez, 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). "System Deadlocks" (PDF) . ACM Computing Surveys . 3 (2): 67– 78. doi : 10.1145/356586.356588 . S2CID 15975305. Archivado del original (PDF) el 27 de enero de 2012. Recuperado el 20 de diciembre de 2004 . 
  • Mogul, Jeffrey C.; Ramakrishnan, KK (1997). "Eliminación del bloqueo de recepción en un núcleo controlado por interrupciones". ACM Transactions on Computer Systems . 15 (3): 217– 252. CiteSeerX 10.1.1.156.667 . doi : 10.1145/263326.263335 . ISSN 0734-2071 . S2CID 215749380 .   
  • Havender, James W. (1968). "Cómo evitar el bloqueo en sistemas multitarea" . IBM Systems Journal . 7 (2): 74. doi : 10.1147/sj.72.0074 . Archivado del original el 24 de febrero de 2012. Recuperado el 27 de enero de 2009 .
  • Holliday, JoAnne L.; El Abbadi, Amr. "Detección de interbloqueos distribuidos" . Enciclopedia de computación distribuida . Archivado del original el 2 de noviembre de 2015. Recuperado el 29 de diciembre de 2004 .
  • Knapp, Edgar (1987). "Detección de interbloqueos en bases de datos distribuidas". ACM Computing Surveys . 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 planificación óptima de detección de interbloqueos". IEEE Transactions on Computers . 55 (9): 1178– 1187. Bibcode : 2006ITCmp..55.1178L . CiteSeerX 10.1.1.259.4311 . doi : 10.1109/tc.2006.151 . S2CID 7813284 .  
  • " Sincronización avanzada en hilos de Java " por Scott Oaks y Henry Wong
  • Agentes de detección de interbloqueos
  • Interbloqueo en el repositorio de patrones de Portland
  • Etimología de "punto muerto"