2.4.3 Interbloqueo DeadLock

(Como menciona Albert S. Woodhull, 1999) El bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.

Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de cuatro vehículos que se encuentran en una intersección en el mismo momento. Cada uno necesita que otro se mueva para poder continuar su camino, y ninguno puede continuar.

(Como menciona Albert S. Woodhull, 1999) Los recursos compartidos en este caso son los cuatro cuadrantes. El vehículo que se dirige de oeste a este, por ejemplo, necesita de los cuadrantes suroeste y sureste.En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso).

El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Condiciones necesarias.
También conocidas como condiciones de Coffman por su primera descripción en 1971 en un artículo escrito por E.G.Coffman. Estas condiciones deben cumplirse simultáneamente y no son totalmente independientes una de otra.Sean los procesos Po, P1,.. Pn y los recursos Ro, R1,..., Rm:

*Condición de exclusión mutua: Existencia al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.

*Condición de Posesión y espera: Al menos un proceso Pi ha adquirido un recurso Ri, y lo mantiene mientras espera al menos un recurso Rj que ya ha sido asignado a otro proceso.
Condición de no expropiación: Los recursos no pueden ser apropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.

*Condición de espera circular: Dado el conjunto de procesos P0...Pn, P0 está esperando un recurso adquirido por P1, que está esperando un recurso adquirido por P2, que...,que está esperando un recurso adquirido por Pn, que está esperando un recurso adquirido por P0. Esta condición implica la condición de retención y espera.

Evitando bloqueos mutuos.
Los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. De esta forma, el sistema satisface los pedidos de recursos solamente si se asegura que quedará en un estado seguro. Para que el sistema sea capaz de decidir si el siguiente estado será seguro o inseguro, debe saber por adelantado y en cualquier momento el número y tipo de todos los recursos en existencia, disponibles y requeridos.

Existen varios algoritmos para evitar bloqueos mutuos:

*Algoritmo del banquero, introducido por Dijkstra.
*Algoritmo de grafo de asignación de recursos.
*Algoritmo de Seguridad.
*Algoritmo de solicitud de recursos.