Un conjunto de procesos está en interbloqueo (deadlock) si cada proceso del conjunto espera un evento que sólo puede causar otro proceso del conjunto. Aparece con frecuencia al usar Sistemas Operativos/Semáforos y Sistemas Operativos/Mutex y monitores en orden incorrecto.

Recursos

• Apropiativos: pueden quitarse al proceso sin efectos negativos (p. ej. memoria).
• No apropiativos: no pueden quitarse sin que falle el cómputo (p. ej. una impresora a medio imprimir).

Uso de un recurso: solicitar → usar → liberar.

Condiciones de Coffman (1971)

Las cuatro deben cumplirse para que haya interbloqueo:

1. Exclusión mutua: cada recurso está asignado a un solo proceso o disponible.
2. Contención y espera (hold and wait): un proceso que tiene recursos puede pedir más.
3. No apropiación: los recursos no se pueden quitar a la fuerza.
4. Espera circular: existe una cadena circular de dos o más procesos, cada uno esperando un recurso del siguiente.

Grafos de asignación de recursos

Procesos como círculos, recursos como cuadrados. Arista recurso → proceso: el recurso está asignado. Arista proceso → recurso: el proceso lo solicita. Un ciclo en el grafo (con una instancia por recurso) indica interbloqueo.

Estrategias

1. Ignorar el problema (algoritmo del avestruz)

Si los interbloqueos son raros y el coste de evitarlos alto, se ignoran. Es lo que hacen la mayoría de los SO de propósito general.

2. Detección y recuperación

• Una instancia por recurso: buscar ciclos en el grafo.
• Varias instancias: usar la matriz de asignación actual C, la de solicitudes R, el vector de existentes E y el de disponibles A; buscar procesos cuyas solicitudes puedan satisfacerse.
• Recuperación: apropiación, retroceso (rollback a un checkpoint) o eliminación de procesos.

3. Evitación (avoidance)

Conceder recursos sólo si el sistema queda en un estado seguro: uno donde existe un orden en que todos los procesos pueden terminar.

Algoritmo del banquero (Dijkstra, 1965): como un banquero que concede créditos, comprueba antes de cada asignación que el estado resultante sea seguro. Problema: requiere conocer de antemano las necesidades máximas, algo raro en la práctica.

4. Prevención

Atacar una de las cuatro condiciones:

La última es la más práctica: si todos los hilos toman los candados en el mismo orden global, no puede haber ciclos.

Problemas relacionados

• Bloqueo en dos fases (bases de datos): fase de adquisición y fase de liberación.
• Interbloqueos de comunicación: A espera respuesta de B que nunca llega; se resuelven con timeouts.
• Livelock: los procesos no están bloqueados pero no progresan (ej. dos personas que se apartan hacia el mismo lado en un pasillo).
• Inanición (starvation): un proceso nunca obtiene el recurso aunque no haya interbloqueo; se evita con FCFS.

Ver Sistemas Operativos/Problemas clásicos de IPC (la cena de los filósofos).

#sistemas-operativos #tanenbaum #concurrencia #deadlock