stringtranslate.com

Punto muerto (informática)

Ambos procesos necesitan recursos para continuar 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 bloqueo cuando todos los procesos bloquean el recurso simultáneamente (líneas negras). El bloqueo se puede resolver rompiendo la simetría.

En computación concurrente , un bloqueo es cualquier situación en la que ningún miembro de algún grupo de entidades puede continuar porque cada uno espera que otro miembro, incluido él mismo, realice una acción, como enviar un mensaje o, más comúnmente, liberar un bloqueo . [1] Los bloqueos son un problema común en sistemas de multiprocesamiento , computación paralela y sistemas distribuidos , porque en estos contextos los sistemas a menudo usan bloqueos de software o hardware para arbitrar recursos compartidos e implementar la sincronización de procesos . [2]

En un sistema operativo , un bloqueo ocurre cuando un proceso o subproceso entra en un estado de espera porque un recurso del sistema solicitado está en poder de otro proceso en espera, que a su vez está esperando otro recurso en poder de otro proceso en espera. [3] Si un proceso permanece indefinidamente incapaz de cambiar su estado porque los recursos que solicita están siendo utilizados por otro proceso que a su vez está esperando, entonces se dice que el sistema está en un bloqueo. [4]

En un sistema de comunicaciones , los bloqueos ocurren 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.
  1. Se lleva a cabo un único proceso.
  2. El proceso posterior tendrá que esperar.
  3. Se produce un bloqueo 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 individualmente necesarias y conjuntamente suficientes para el estancamiento

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

  1. Exclusión mutua : no se pueden compartir varios recursos; solo un proceso a la vez puede usar cada recurso. [7] [8]
  2. 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.
  3. Sin prelación : un recurso sólo puede ser liberado voluntariamente por el proceso que lo posee.
  4. Espera circular: cada proceso debe estar esperando un recurso que está en poder de otro proceso, que a su vez está esperando que el primer proceso libere el recurso. En general, hay un conjunto de procesos en espera, P = { P 1 , P 2 , ..., P N }, de modo que P 1 está esperando un recurso en poder de P 2 , P 2 está esperando un recurso en poder de P 3 y así sucesivamente hasta que P N está esperando un recurso en poder de P 1 . [4] [9]

Estas cuatro condiciones se conocen como 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 bloqueo en sistemas de recursos de instancia única, solo indican la posibilidad de bloqueo 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 bloqueos. [11] Cuando se produce un bloqueo, los distintos sistemas operativos responden a ellos de maneras 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 enfoques principales son los siguientes.

Ignorando el punto muerto

En este enfoque, se supone que nunca se producirá un bloqueo. Esta es también una aplicación del algoritmo Ostrich . [12] [13] Este enfoque fue utilizado inicialmente por MINIX y UNIX . [9] Esto se utiliza cuando los intervalos de tiempo entre las ocurrencias de bloqueos son grandes y la pérdida de datos incurrida cada vez es tolerable.

Se puede ignorar los bloqueos si se demuestra formalmente que nunca ocurren. Un ejemplo es el marco RTIC. [14]

Detección

En el marco de la detección de interbloqueos, se permite que se produzcan. A continuación, se examina el estado del sistema para detectar que se ha producido un interbloqueo y, posteriormente, se corrige. Se emplea un algoritmo que realiza un seguimiento de la asignación de recursos y de los estados de los procesos, revierte y reinicia uno o más de los procesos para eliminar el interbloqueo detectado. Detectar un interbloqueo que ya se ha producido es fácilmente posible, ya que el programador de recursos del sistema operativo conoce los recursos que cada proceso ha bloqueado y/o solicitado actualmente. [13]

Una vez detectado un bloqueo, se puede corregir mediante uno de los siguientes métodos: [ cita requerida ]

  1. Terminación de proceso: se pueden abortar uno o más procesos involucrados en el punto muerto. Se podría elegir abortar todos los procesos en competencia involucrados en el punto muerto. Esto garantiza que el punto muerto se resuelva con certeza y rapidez. [ cita requerida ] Pero el costo es alto ya que se perderán cálculos parciales. O bien, se podría elegir 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 requerida ] Se deben considerar varios factores al elegir un candidato para la terminación, como la prioridad y la antigüedad del proceso. [ cita requerida ]
  2. Prelación de recursos: los recursos asignados a varios procesos pueden ser prendidos y asignados sucesivamente a otros procesos hasta que se rompa el punto muerto. [15] [ verificación fallida ]

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 puede resolverse rompiendo la simetría de los bloqueos. (D) El interbloqueo puede evitarse rompiendo la simetría del mecanismo de bloqueo.

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

Prevención de bloqueos

De manera similar a la prevención de interbloqueos, el enfoque de evitación de interbloqueos garantiza que no se produzcan interbloqueos en un sistema. El término "evitación de interbloqueos" parece ser muy similar a "prevención de interbloqueos" en un contexto lingüístico, pero son muy diferentes en el contexto del manejo de interbloqueos. 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.

La prevención de bloqueos requiere que el sistema operativo reciba de antemano información adicional sobre qué recursos solicitará y utilizará un proceso durante su vida útil. El algoritmo de prevención de bloqueos analiza todas y cada una de las solicitudes examinando que no haya posibilidad de que se produzca un bloqueo en el futuro si se asigna el recurso solicitado. El inconveniente de este enfoque es que requiere información de antemano sobre cómo se solicitarán los recursos en el futuro. Uno de los algoritmos de prevención de bloqueos más utilizados es el algoritmo de Banker . [17]

Bloqueo de vida

Un bloqueo activo es similar a un bloqueo mutuo, excepto que los estados de los procesos involucrados en el bloqueo activo cambian constantemente unos con respecto a otros y ninguno progresa.

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 solo establece que un proceso específico no está progresando. [20]

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

Bloqueo distribuido

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

Los bloqueos distribuidos se pueden detectar construyendo un gráfico de espera global a partir de gráficos de espera locales en un detector de bloqueos o mediante un algoritmo distribuido como la búsqueda de bordes.

Los interbloqueos fantasma son interbloqueos que se detectan de forma errónea 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 erróneamente que existe un interbloqueo (si la solicitud para R2 mientras se tiene R1 provocaría 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, Jack B; Dennis, Jack B; 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). "Bloqueos". Enciclopedia de computación paralela . Boston, MA: Springer US. págs. 524–527. doi :10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09766-4_282 . 978-0-387-09765-7. S2CID  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 se produce un interbloqueo cuando dos o más procesos esperan que el otro libere un recurso. Ninguno de los procesos puede avanzar.
  4. ^ abc 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 desde el original el 29 de abril de 2018 . Consultado el 29 de abril de 2018 .
  9. ^ abc Shibu, K. (2009). Introducción a los sistemas integrados (1.ª ed.). Tata McGraw-Hill Education. pág. 446. ISBN 9780070145894Archivado del original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  10. ^ "Sistemas operativos: bloqueos". 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 bloqueo, pero no lo garantiza. Considere, 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. ^ ab Stuart, Brian L. (2008). Principios de los 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. ^ ab 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 impulsada por interrupciones en tiempo real". Archivado desde el original el 18 de septiembre de 2020 . Consultado el 1 de octubre de 2020 .
  15. ^ "IBM Knowledge Center". www.ibm.com . Archivado desde el original el 19 de marzo de 2017 . Consultado el 29 de abril de 2018 .
  16. ^ 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 .
  17. ^ "Algoritmos para evitar bloqueos en sistemas operativos (OS)". Electronics Mind . 26 de enero de 2022.
  18. ^ Ashcroft, EA (1975). "Probar afirmaciones sobre programas paralelos". Journal of Computer and System Sciences . 10 : 110–135. doi : 10.1016/S0022-0000(75)80018-3 .
  19. ^ Kwong, YS (1979). "Sobre la ausencia de bloqueos activos en programas paralelos". Semántica de computación concurrente . Apuntes de clase en informática. Vol. 70. págs. 172–190. doi :10.1007/BFb0022469. ISBN. 3-540-09511-X.
  20. ^ Anderson, James H. ; Yong-jik Kim (2001). «Exclusión mutua en memoria compartida: principales tendencias de investigación desde 1986». Archivado desde el original el 25 de mayo de 2006.
  21. ^ Zöbel, Dieter (octubre de 1983). "El problema del bloqueo: una bibliografía clasificatoria". ACM SIGOPS Operating Systems Review . 17 (4): 6–15. doi : 10.1145/850752.850753 . ISSN  0163-5980. S2CID  38901737.

Lectura adicional

Enlaces externos