Deadlock en sistemas operativos
En la situación 2, tanto P2 como P1 se van a encontrar bloqueados, debido a que P2 está esperando a que P1 libere el recurso 2 y P1 está esperando a que P2 libere el recurso 1, ambos procesos se encuentran en DEADLOCK. El problema acá no fue el orden de ejecución, sino que ambos se bloquearon y no pueden ejecutar.
- Mutua exclusión: evitar la mutua exclusión sobre recursos compartibles. Ej: apertura de archivos en modo lectura.
- Espera y retención:
- Que los procesos pidan y se le asignen previamente todos los recursos que vaya a usar, desde el vamos
- Que un proceso para pedir un nuevo recurso tenga que liberar todos los que retiene
- Sin desalojo:
- Si un proceso pide un recurso que no está disponible, debe esperar y además, liberar todos los recursos que tenía asignados
- Si un proceso pide un recurso retenido por otro proceso en espera, los mismos son desalojados y asignados al primero
- Espera circular: Se debe requerir que los recursos se pidan en orden. Si todos los procesos piden los recursos bajo un orden estipulado, no se va a producir espera circular.
- El proceso deberá indicarle al SO cuáles van a ser los recursos máximos que puede llegar a solicitar durante su tiempo de vida, es decir, que exista una cota superior.
- Ante cada solicitud, se analizará si se le asigna el recurso al proceso o si se lo hace esperar. Para tomar una decisión se realizará una simulación teniendo en cuenta las posibles futuras solicitudes y liberaciones de recursos por parte de todos los procesos del sistema.
- Se mantendrá al sistema siempre en Estado Seguro
- Un estado es seguro si el sistema puede asignar recursos a cada proceso (hasta su máximo) en determinado orden sin que eso produzca un deadlock (existe una secuencia segura)
- Si el estado es seguro => no existe ni existirá deadlock
- Si el estado es inseguro => podría ocurrir deadlock
- Sólo se asignará un recurso si dicha asignación deja al sistema en estado seguro
- Se podría utilizar un grafo de asignación de recursos para analizar el estado del sistema (agregando el tipo de arista declaración
- Matriz de peticiones máximas -> Esta estructura se utiliza debido a que por cada proceso voy a necesitar saber de cada recurso cuantas instancias me va a pedir como máximo
- Matriz de recursos asignados -> Esta estructura se utiliza debido a que por cada proceso voy a necesitar saber de cada recurso cuantas instancias ya se le asignó
- Matriz de necesidad -> Es la resta entre la matriz de peticiones máximas y la matriz de recursos asignados, cuántos recursos pidió como máximo y cuales ya se le asignó
- Vector de recursos totales
- Vector de recursos disponibles -> Vector de recursos totales menos los que ya se asignaron
Evasión de deadlocks
Una forma más sofisticada que la prevención de deadlocks, es la evasión
¿Qué pasos vamos a seguir para llevar a cabo esta evasión?
¿Qué se hará en dicha“simulación”?
Evasión de deadlocks - Algoritmo del banquero
A continuación en la situación A vamos a ver como cuando P3 pide 1 R2, se va a tener que producir una simulación para determinar si se le asigna o no:En el paso 2 para definir si la petición es válida o no, nos fijamos en la matriz de necesidad.
En el paso 3 para saber si tenemos esa cantidad disponible, nos fijamos en la tabla de recursos disponibles.
¿Y en el paso 4 cómo sabemos si el estado resultante es seguro o no?
Acordarse de que es importante en el paso 4.1 siempre vamos a tener que actualizar la tabla de recursos asignados, la de necesidad, y la de recursos disponibles para saber cómo estoy.
Con esta simulación nosotros todavía no le dimos el recurso, lo estamos simulando. Luego del paso 4.1 vamos a querer saber si hay un orden en que yo le pueda dar todos los recursos a los procesos y que vayan terminando.
Como bien vemos, en el paso 4.2, tuvimos en cuenta los recursos que podían llegar a pedir P1, P2, y P3, junto con los recursos disponibles, y en el orden en que le terminamos dando los recursos a cada proceso (primero P3, luego P2, y luego P1), pudimos lograr una secuencia segura.
La situación B, en donde P2 la va a pedir 2 R2, va a terminar siendo distinta a la situación A:
Vemos si el estado resultante es seguro:
En esta situación no se pudo obtener ninguna secuencia segura debido a que independientemente del orden, no le podemos asegurar a ninguno de los procesos su ejecución:
-Si empieza ejecutando P1, no le podemos garantizar la posible petición de 1 R1
-Si empieza ejecutando P2, no le podemos garantizar la posible petición de 1 R1
-Si empieza ejecutando P3, no le podemos garantizar la posible petición de 1 R2.
Esto no significa que si o si va a ocurrir un deadlock, sino que significa que puede llegar a haber deadlock si yo le doy los 2 R2 a P2 debido a que no existe ninguna secuencia segura.
Detección y recuperación de deadlocks
Una vez visto prevención y evasión de deadlocks, tenemos una 3er forma para el tratamiento de deadlocks: detección y recuperación.
➢ Acá, al igual que en el algoritmo del banquero, se realizará una simulación de asignación de recursos, en este caso, para ver si puede satisfacer todas las peticiones actuales
➢ Estructuras necesarias
o Matriz de asignación
o Matriz de peticiones (actuales)
o Vectores de recursos totales y disponibles
➢ Tiene un coste significativo asociado
o Mantenimiento de la información necesaria y la ejecución del algoritmo de detección
o Potenciales pérdidas inherentes al proceso de recuperación
¿Con qué frecuencia hay que correr el algoritmo de detección?
Se corre cada intervalos regulares, buscando procesos que no puedan continuar ejecutando, aunque la frecuencia real depende mucho de cómo se programe el algoritmo.