stringtranslate.com

Punto muerto

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.
  1. Se realiza un único proceso.
  2. El proceso posterior tiene que esperar.
  3. Se produce un punto muerto cuando el primer proceso bloquea el primer recurso al mismo tiempo que el segundo proceso bloquea el segundo recurso.
  4. 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]

  1. 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]
  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 preferencia : 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á 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 interbloqueos, 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 ]

  1. 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 ]
  2. 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.

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]

Punto muerto distribuido

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

Los interbloqueos distribuidos se pueden detectar construyendo un gráfico de espera global a partir de gráficos de espera locales en un detector de interbloqueos 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).

Ver también

Referencias

  1. ^ Coulouris, George (2012). Conceptos y diseño de sistemas distribuidos . Pearson. pag. 716.ISBN​ 978-0-273-76059-7.
  2. ^ Padua, David (2011). Enciclopedia de computación paralela. Saltador. pag. 524.ISBN​ 9780387097657. Archivado desde el 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; 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. ISBN 978-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.
  4. ^ abc Silberschatz, Abraham (2006). Principios del sistema operativo (7ª ed.). Wiley-India. pag. 237.ISBN​ 9788126509621. Archivado desde el original el 25 de enero de 2022 . Consultado el 16 de octubre de 2020 .
  5. ^ Schneider, G. Michael (2009). Invitación a Ciencias de la Computación. Aprendizaje Cengage. pag. 271.ISBN​ 978-0324788594. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  6. ^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 239.ISBN​ 9788126509621. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  7. ^ Conceptos del sistema operativo . Wiley. 2012. pág. 319.ISBN​ 978-1-118-06333-0.
  8. ^ "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 .
  9. ^ a b C Shibu, K. (2009). Introducción a los sistemas integrados (1ª ed.). Educación de Tata McGraw-Hill. pag. 446.ISBN​ 9780070145894. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  10. ^ "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:
  11. ^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 237.ISBN​ 9788126509621. Archivado desde el 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.). Aprendizaje Cengage. pag. 446.ISBN​ 9781418837693. Archivado desde el 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.). Educación Pearson. pag. 117.ISBN​ 9788177581799. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  14. ^ "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 .
  15. ^ "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 .
  16. ^ Silberschatz, Abraham (2006). Principios del sistema operativo (7 ed.). Wiley-India. pag. 244.ISBN​ 9788126509621. Archivado desde el original el 18 de abril de 2021 . Consultado el 16 de octubre de 2020 .
  17. ^ "Algoritmos para evitar puntos muertos en el sistema operativo (SO)". Mente Electrónica . 26 de enero de 2022.
  18. ^ 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 .
  19. ^ 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. ISBN 3-540-09511-X.
  20. ^ 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.
  21. ^ 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.

Otras lecturas

enlaces externos