1. Qué es la detección
La detección de interbloqueos permite que el sistema entre en un deadlock y luego lo detecte y recupere. A diferencia de la prevención (estática) y la evasión (dinámica), la detección es reactiva: deja que el deadlock ocurra y luego lo resuelve.
La detección tiene dos partes:
- Detección: determinar si hay un deadlock (buscar ciclos en el RAG).
- Recuperación: salir del deadlock (terminar procesos o quitar recursos).
La detección es útil cuando la prevención es demasiado restrictiva y la evasión requiere información que no está disponible.
2. Cuándo detectar
La detección se puede ejecutar:
| Cuándo | Ventaja | Desventaja |
|---|---|---|
| Cada vez que se solicita un recurso | Detecta el deadlock inmediatamente. | Overhead alto. |
| Periódicamente | Menos overhead. | El deadlock puede persistir un tiempo. |
| Cuando la utilización de la CPU baja | Detecta deadlocks que causan inactividad. | Puede ser tarde. |
En la práctica, la detección periódica es la más usada: se ejecuta cada cierto tiempo (por ejemplo, cada minuto) y se verifica si hay deadlocks.
3. El algoritmo de detección
El algoritmo de detección es similar a la prueba de seguridad del banquero, pero sin la demanda máxima (no se necesita porque los procesos ya tienen los recursos):
- Inicializar: Work = Available. Finish[i] = false para todos (o true si Allocation[i] = 0). init
- Buscar un proceso i tal que Finish[i] = false y Request[i] ≤ Work. buscar
- Si existe: Work = Work + Allocation[i]. Finish[i] = true. Volver al paso 2. simular
- Si no existe: si algún Finish[i] es false, hay deadlock. Los procesos con Finish[i] = false están en deadlock. resultado
La idea es simular que los procesos que pueden terminar lo hacen, liberando sus recursos. Los que no pueden terminar están en deadlock.
4. Un ejemplo desarrollado
Un sistema con 3 procesos y 3 tipos de recursos (A, B, C) con 10, 5, 7 instancias:
| Proceso | Allocation (A,B,C) | Request (A,B,C) |
|---|---|---|
| P0 | (0,1,0) | (0,0,0) |
| P1 | (2,0,0) | (2,0,2) |
| P2 | (3,0,3) | (0,0,0) |
Available = (10-0-2-3, 5-1-0-0, 7-0-0-3) = (5, 4, 4).
Detección:
- Work = (5,4,4). Buscar proceso con Request ≤ Work. init
- P0: Request = (0,0,0) ≤ (5,4,4). ✓. Work = (5,4,4) + (0,1,0) = (5,5,4). Finish[0] = true. P0
- P2: Request = (0,0,0) ≤ (5,5,4). ✓. Work = (5,5,4) + (3,0,3) = (8,5,7). Finish[2] = true. P2
- P1: Request = (2,0,2) ≤ (8,5,7). ✓. Work = (8,5,7) + (2,0,0) = (10,5,7). Finish[1] = true. P1
- Todos terminaron. No hay deadlock. seguro
Si P1 hubiera solicitado (3,0,2) en lugar de (2,0,2), no se podría satisfacer (3 > 2 en A), y P1 estaría en deadlock (si P0 y P2 no liberan suficientes recursos).
5. Recuperación
Una vez detectado el deadlock, hay que recuperarse. Hay dos enfoques:
| Enfoque | Cómo funciona | Ventaja | Desventaja |
|---|---|---|---|
| Terminación de procesos | Matar uno o más procesos para liberar recursos. | Simple, efectivo. | Pérdida de trabajo, inconsistencia. |
| Preemption de recursos | Quitar recursos a un proceso y dárselos a otro. | No se pierde el proceso. | Puede causar inconsistencia. |
6. Terminación de procesos
La terminación puede ser:
- Total: matar todos los procesos en deadlock. Simple pero costoso (se pierde todo el trabajo).
- Parcial: matar un proceso a la vez hasta que se rompa el deadlock. Menos costoso pero más complejo.
Para elegir qué proceso matar (la víctima), se consideran:
- Prioridad: matar el de menor prioridad.
- Tiempo de ejecución: matar el que ha ejecutado menos (menos trabajo perdido).
- Recursos usados: matar el que usa más recursos (libera más).
- Procesos restantes: matar el que afecta a menos procesos.
- Interactividad: no matar procesos interactivos.
Después de matar a la víctima, hay que revertir los efectos: si el proceso había modificado datos compartidos, hay que deshacer los cambios.
7. Preemption de recursos
La preemption consiste en quitar recursos a un proceso y dárselos a otro. Requiere:
- Guardar el estado: del proceso al que se le quita el recurso.
- Restaurar el estado: cuando el proceso recupera el recurso.
- Rollback: deshacer las operaciones que el proceso hizo con el recurso.
La preemption es compleja y rara vez se usa en la práctica, excepto para la CPU (el planificador preempta la CPU rutinariamente).
8. Costos de la recuperación
La recuperación tiene costos:
- Pérdida de trabajo: si se mata un proceso, se pierde su trabajo.
- Inconsistencia: si un proceso había modificado datos compartidos, el sistema puede quedar inconsistente.
- Overhead: la detección y la recuperación consumen tiempo.
- Complejidad: la recuperación es compleja de implementar correctamente.
9. Comparación: prevención vs. evasión vs. detección
| Aspecto | Prevención | Evasión | Detección |
|---|---|---|---|
| Cuándo | Diseño (estática) | Tiempo de ejecución (dinámica) | Tiempo de ejecución (reactiva) |
| Información necesaria | Ninguna | Demanda máxima | Asignación actual |
| Overhead | Bajo (diseño) | Alto (prueba de seguridad) | Medio (detección periódica) |
| Flexibilidad | Baja | Media | Alta |
| Uso real | Muy usado | Poco usado | Usado en bases de datos |
La prevención es la más usada en la práctica porque es simple y no tiene overhead en tiempo de ejecución. La evasión es la más flexible pero requiere información que no siempre está disponible. La detección se usa en sistemas donde el deadlock es raro pero posible (bases de datos).
10. Detección en Linux
Linux no detecta deadlocks en el espacio de usuario. El núcleo tiene mecanismos para detectar deadlocks en el núcleo mismo (lockdep), pero no para procesos de usuario.
Para los procesos de usuario, Linux confía en la prevención (el programador debe diseñar el código para evitar deadlocks). Las herramientas como ThreadSanitizer y Helgrind pueden detectar posibles deadlocks en tiempo de desarrollo.
Las bases de datos (como PostgreSQL) implementan detección de deadlocks: periódicamente buscan ciclos en el grafo de locks y abortan una transacción (víctima) para romper el ciclo.
11. Simulador interactivo
Este simulador ejecuta el algoritmo de detección y muestra si hay deadlock:
Simulador · detección de deadlock
12. Resumen
- La detección permite que el deadlock ocurra y luego lo resuelve.
- El algoritmo de detección busca ciclos en el grafo de asignación.
- La recuperación se hace por terminación de procesos o preemption de recursos.
- La terminación puede ser total o parcial (elegir una víctima).
- La preemption requiere guardar y restaurar el estado.
- La detección se usa en bases de datos y sistemas donde el deadlock es raro.
- Linux no detecta deadlocks en el espacio de usuario.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es la detección de interbloqueos?
Permitir que el deadlock ocurra y luego detectarlo y recuperarse.
2. ¿Cuándo se puede ejecutar la detección?
Cada vez que se solicita un recurso, periódicamente, o cuando la utilización de la CPU baja.
3. ¿Cómo funciona el algoritmo de detección?
Simula que los procesos que pueden terminar lo hacen, liberando recursos. Los que no pueden terminar están en deadlock.
4. ¿Qué es la recuperación?
Salir del deadlock terminando procesos o quitando recursos.
5. ¿Qué es la terminación total?
Matar todos los procesos en deadlock.
6. ¿Qué es la terminación parcial?
Matar un proceso a la vez hasta que se rompa el deadlock.
7. ¿Qué factores se consideran para elegir a la víctima?
Prioridad, tiempo de ejecución, recursos usados, procesos restantes, interactividad.
8. ¿Qué es la preemption de recursos?
Quitar recursos a un proceso y dárselos a otro.
9. ¿Por qué la detección es poco usada en sistemas operativos?
Porque la prevención es más simple y no tiene overhead en tiempo de ejecución.
10. ¿Dónde se usa la detección en la práctica?
En bases de datos (PostgreSQL, MySQL) y otros sistemas donde el deadlock es raro.
Para practicar
- Implementa el algoritmo de detección en C.
- Diseña un conjunto de procesos y recursos con deadlock y verifica con el algoritmo.
- Explica cómo se elige a la víctima en un sistema real.
- Investiga cómo PostgreSQL detecta deadlocks.
- Compara la detección con la prevención y la evasión.
- Explica por qué la detección es poco usada en sistemas operativos.