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ó.
Procesos y recursos
Sobre los recursos
- Recursos físicos: CPU, memoria, dispositivos.
- Recursos lógicos: archivos, semáforos y monitores
- Cada recurso puede tener instancias idénticas (puede haber 2 impresoras del mismo tipo)
- Si son idénticas, se puede asignar cualquier instancia del recurso
- Definición de clase: es el conjunto de instancias de un recurso
Pautas de asignación
- No se pueden asignar mas recursos que los que hay.
- El proceso debe solicitar un recurso antes de usarlo.
- El proceso debe liberar un recurso después de usarlo.
- Secuencia: solicitud, uso, liberación
System calls, estructuras y operaciones asociadas
System calls:
- Request-release device
- Open file-Close file
- Allocate -free memory Operaciones wait y signal
Deadlock, abrazo mortal o interbloqueo
- Definición: Un conjunto de procesos están en deadlock cuando cada uno de ellos esta esperando por un recurso que esta siendo usado por otro proceso del conjunto
- Un estado de deadlock puede involucrar recursos de diferentes tipos.
Ejemplo
Supongamos un sistema con un scanner y una impresora.
- Un proceso A esta usando el scanner y necesita la impresora.
- Un proceso B esta usando la impresora y necesita el scanner. Resultado: deadlock
Condiciones para que se cumpla deadlock
- Exclusión mutua
- Retención y espera
- No apropiación
- Espera circular
Se deben dar simultáneamente y mantenerse. No son totalmente independientes: la espera circular depende de retención y espera.
Exclusión mutua: Un recurso solo puede usarlo un proceso a la vez: es no compartible. Si otro proceso requiere el recurso tiene que esperar a que el proceso que lo tiene lo libere
Retención y esperar: Debe haber un proceso que retenga por lo menos un recurso y que este esperando un recurso que tiene otro proceso retenido.
No apropiacion: El recurso debe ser liberado voluntariamente por el proceso que lo retiene cuando completa su tarea.
Espera circular:
- Los proceso Pi , P2 ,P3 ,…,Pn… son procesos esperando recursos.
- P1 espera un recurso que retiene P2
- P2 espera un recurso que tiene P3
- Pn espera un recurso que tiene P1
Grafos de asignación de recursos
Sirven para graficar el deadlock. Se definen:
- V, conjunto de vértices. Pueden ser procesos o recursos.
- Procesos: Representados por círculos.
- Recursos: Representados por rectángulos.
- Puntos: representan instancias de recursos.
Un arco entre el proceso Pi y el recurso Rj indica que Pi solicito una instancia del recurso Rj (arco de requerimiento)
Un arco entre el recurso Rj y el proceso Pi indica que el recurso Rj fue asignado al proceso Pi (arco de asignación)
- Si el grafo no contiene ciclos ^ no hay deadlock
- Si el grafo contiene ciclos ^ PUEDE SER que no hay deadlock
Pingback: Deadlock, Interbloqueo, Abrazo Mortal – Parte II – La Compu Del Vecino
Pingback: Deadlock, Interbloqueo, Abrazo Mortal – Parte III – La Compu Del Vecino