Interbloqueos

En sistemas operativos, 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 dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.

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.

Administración de procesos

Necesidad

La sincronización de procesos creados por diferentes equipos de programadores, está a cargo del sistema operativo

Definiciones

Interbloqueo

Se dice que dos o más procesos están bloqueados, cuando están suspendidos en espera de un evento que sólo puede ser activado por uno de los procesos bloqueados, y por lo tanto dicho evento nunca sucederá

Postergación indefinida o Inanición (Starving)

Se dice que uno o más procesos están en postergación indefinida cuando la política de planificación del sistema permite que un proceso quede en espera de un evento por un tiempo indefinido. Esto puede suceder, por ejemplo, cuando la asignación de recursos se realiza por prioridad. De este modo un proceso de baja prioridad estará suspendido mientras existan otros procesos de mayor prioridad.

Envejecimiento: aumentar la prioridad de los procesos conforme pasa el tiempo

Clasificación de recursos

Para el estudio del interbloqueo, los recursos se pueden clasificar en:

Compartido/exclusivos: Se dice que un recursos es compartido si puede ser utilizado por más de un proceso al mismo tiempo. Son exclusivos los que pueden ser utilizados sólo por un proceso a la vez

Apropiativos/inapropiativos: Son apropiativos los recursos asignados a un proceso, que pueden ser desasignados del proceso, por al sistema para asignarlos a otro proceso.

Los recursos involucrados en los interbloqueos son los exclusivos e inapropiativos

Condiciones necesarias para el interbloqueo

Coffman, Elphuck y Shoshani, establecieron cuatro condiciones, necesarias y suficientes, para que se dé un interbloqueo:

Exclusión mutua

Si dos procesos solicitan un recurso exclusivo, uno de los dos quedará suspendido hasta que el favorecido libere el recurso.

Contención o retención y espera

Si un proceso necesita más de un recurso para realizar su trabajo, conservará en su poder los recursos exclusivos ya asignados, mientras espera por otro recurso adicional.

Inapropiatividad

Los recursos asignados a un proceso, sólo pueden ser liberados por el proceso mismo y no pueden ser desasignados por el sistema, cuando otro proceso los necesite.

Espera circular

Dependencia: Si un proceso P1 está suspendido en espera de un recurso exclusivo que está asignado a otro proceso P2, entonces decimos que P1 depende de P2 (P1 <= P2).

Espera circular: Existe

...