Abrazo mortal o Interbloqueos o DeadlocK:

Abrazo mortal o Interbloqueos o DeadlocK:

Es una situación en donde un grupo de procesos se bloquea permanente como resultado de que cada proceso ha obtenido un subconjunto de los recursos necesarios para su terminación y se encuentra esperando indefinidamente por lo la liberación de otros recursos que están siendo ocupados por otros procesos los cuales también esperan por recursos ocupados por el primer proceso, haciendo imposible que cualquiera de los procesos pueda proceder.

Los deadlocks ocurren en ambientes concurrentes como resultado de una concesión, sin control, de los recursos del sistema que solicitan los procesos.

Los abrazos mortales pueden también involucrar diferentes tipos de recursos. Por ejemplo, considere un sistema con una impresora y una unidad de disco. Suponga que el proceso A tiene asignada la unidad de disco y que el proceso B tiene asignada la impresora. Ahora, si A pide la impresora y B pide la unidad de disco, ocurre un abrazo mortal.

 Una situación de abrazo mortal puede surgir si y solo si las siguientes cuatro condiciones ocurren simultáneamente en un sistema:

1.       Exclusión Mutua: Cada recurso se asigna por lo regular exactamente a un proceso o bien está disponible.

2.       Retener y Esperar: Los procesos que regularmente contienen recursos otorgados antes  pueden solicitar nuevos recursos. Debe existir un proceso que retenga al menos un recurso y este esperando para adquirir recursos adicionales que están siendo retenidos por otros procesos.

3.       No existe el derecho de desasignar (No preemtion): Los recursos previamente otorgados no pueden extraerse por la fuerza de un proceso.

4.       Espera Circular: Debe haber una cadena de dos o más procesos, cada uno de los cuales este esperando un recurso contenido en el siguiente miembro de la cadena. Debe existir un conjunto {p0, p1, ...,pn} de procesos en espera tal que p0 esté esperando por un recurso que está siendo retenido por p1, p1 está esperando por un recurso que está siendo retenido por p2, ..., pn-1 está esperando por un recurso que está siendo retenido por pn y pn está esperando por un recurso que está siendo retenido por p0.

La condición de espera circular implica la condición de retener y esperar, de tal manera que las cuatro condiciones no son totalmente independientes. Sin embargo, puede ser útil el considerar cada condición por separado.

Una forma de modelar estas condiciones es usando un grafo de recursos: los círculos representan procesos, los cuadrados recursos. Una arista desde un recurso a un proceso indica que el recurso ha sido asignado al proceso. Una arista desde un proceso a un recurso indica que el proceso ha solicitado el recurso, y está bloqueado esperándolo. Entonces, si hacemos el grafo con todos lo procesos y todos los recursos del sistema y encontramos un ciclo, los procesos en el ciclo están bajo bloqueo mutuo.

Clases de algoritmos para detección de deadlocks en sistemas Distribuidos

Existen tres clases de algoritmos de detección de deadlocks:

1. Centralizados: el mantenimiento y detección se realiza en un solo lugar.

2. Distribuidos: la gráfica del estado del sistema se encuentra distribuido en varios lugares.

3. Jerárquicos: los lugares del sistema se arreglan en una jerarquía y cada nodo es responsable por  la gráfica de estado de sus descendientes.

Algoritmos centralizados para detectar deadlocks

·         Ho and Ramamoorthy. Dos fases.

·         Algoritmo de una fase

Algoritmos distribuidos para detección de deadlocks

·         Algoritmo de Chandy-Misra-Hass.

·         Algoritmo de Menasce and Muntz.

Algoritmos jerárquicos para detección de deadlocks

·         Algoritmo de Menasce y Muntz.

·         Algoritmo de Ho y Ramamoorthy

Conclusiones

Los deadlocks aparecen en cualquier tipo de sistema concurrente (paralelo o distribuido) provocados por factores de sincronización y administración de recursos. El desarrollador de   aplicaciones es responsable de tener en cuenta la presencia de deadlocks al administrar recursos propios de la aplicación.

En contraste con la prevención de deadlocks, la técnica de detección y recuperación parece más adecuada para sistemas distribuidos. Sin embargo, debido a los retrasos de comunicación existe la posibilidad de detectar deadlocks falsos. Así que técnicas más formales se requieren para garantizar la no existencia de deadlocks.

Para el caso de los sistemas distribuidos existen tres estrategias para detección de deadlocks: centralizadas, distribuidas y jerárquicas. Los factores que se utilizan para evaluar el rendimiento de los algoritmos propuestos son: tamaño y número de mensajes, y el tiempo de retraso que existe para que el algoritmo detecte un deadlock.