Deadlocks (Abrazos Mortales o Interbloqueos)

Resumen

Definición

Un interbloqueo (deadlock) es una situación en la que un grupo de procesos están indefinidamente bloqueados sin posibilidad de continuar. Cada proceso del grupo ha adquirido un conjunto de recursos necesarios y espera otros que están asignados a otros procesos del grupo, creando un bucle de espera sin salida.

Ejemplo clásico

Sistema con impresora y disco, cada uno accesible en exclusión mutua con semáforos binarios disco e impresora (inicializados en 1).

/* Proceso P0 */          /* Proceso P1 */
sem_wait(disco)           sem_wait(impresora)
sem_wait(impresora)       sem_wait(disco)
/* Usar disco/impresora */ /* Usar disco/impresora */
sem_signal(impresora)     sem_signal(disco)
sem_signal(disco)         sem_signal(impresora)

Secuencia de fallo:

1. P0 obtiene disco (sem_wait(disco) → OK).
2. P1 obtiene impresora (sem_wait(impresora) → OK).
3. P1 pide disco → se bloquea (disco asignado a P0).
4. P0 pide impresora → se bloquea (impresora asignada a P1).
5. Deadlock: P1 espera disco (lo tiene P0), P0 espera impresora (la tiene P1).

Cuatro condiciones necesarias (todas simultáneas)

1. Exclusión mutua: los recursos se acceden en exclusión mutua.
2. Retención y espera: cada proceso tiene recursos asignados y espera otros.
3. No expropiación: los recursos sólo se liberan a petición explícita del proceso (el SO no los puede tomar).
4. Espera circular: los procesos forman una cadena circular de espera (P0 espera a P1, P1 espera a P0).

Estrategias para tratar el problema

1. Prevenir el interbloqueo:

• Asegurar que al menos una de las cuatro condiciones no se produzca.
• Ejemplo: ordenar los recursos linealmente y obligar a que los procesos los pidan en orden creciente → elimina la espera circular.
• En el ejemplo: todos los procesos pedirían primero disco y luego impresora.

2. Evitar el interbloqueo:

• Asignar sólo recursos que no puedan generar interbloqueo.
• Requiere llevar un control detallado de recursos asignados, procesos y recursos esperados.

3. Detectar y recuperar el interbloqueo:

• Dejar que aparezcan interbloqueos.
• Comprobar periódicamente si hay ciclos en el grafo de recursos asignados.
• Para romper el interbloqueo, el SO reinicia algunos de los procesos bloqueados.

Ideas clave

• Un deadlock requiere las cuatro condiciones: exclusión mutua, retención y espera, no expropiación y espera circular.
• La prevención más sencilla es ordenar los recursos y pedirlos en orden creciente.
• La detección periódica permite recuperarse pero con overhead.
• Los deadlocks surgen de la asignación incontrolada de recursos sin protocolo definido.
• El programador puede crear deadlocks involuntariamente al diseñar procesos cooperativos.