1. Qué es la prevención
La prevención de interbloqueos consiste en diseñar el programa de forma que no se puedan cumplir las cuatro condiciones de Coffman simultáneamente. Si se rompe al menos una condición, no puede haber deadlock, sin importar el orden de ejecución.
La prevención es una técnica estática: se aplica en tiempo de diseño, no en tiempo de ejecución. El programador diseña el código de forma que sea imposible que se produzca un deadlock.
La prevención tiene un costo: puede reducir el rendimiento o la flexibilidad del programa. Pero garantiza que no habrá deadlocks, lo que es esencial para sistemas críticos.
2. Romper las condiciones de Coffman
Cada condición se puede romper de una forma específica:
| Condición | Cómo romperla | Técnica |
|---|---|---|
| Exclusión mutua | Hacer los recursos compartibles. | Raramente aplicable. |
| Retención y espera | Solicitar todos los recursos de una vez, o liberar antes de solicitar. | Asignación atómica. |
| No apropiación | Permitir quitar recursos a un proceso. | Preemption. |
| Espera circular | Imponer un orden total en la adquisición de recursos. | Orden de bloqueo. |
3. Romper la exclusión mutua
La exclusión mutua se rompe haciendo los recursos compartibles: permitir que varios procesos los usen simultáneamente. Por ejemplo, un archivo en modo lectura puede ser compartido por varios procesos.
Sin embargo, esto no es aplicable a recursos que inherentemente requieren exclusión mutua, como los mutexes. No se puede compartir un mutex entre varios hilos: su propósito es la exclusión mutua.
Por eso, esta técnica se usa raramente para prevenir deadlocks.
4. Romper la retención y espera
La retención y espera se rompe de dos formas:
- Solicitar todos los recursos de una vez: un proceso solicita todos los recursos que necesita antes de empezar. Si no puede obtenerlos todos, no obtiene ninguno y espera.
- Liberar antes de solicitar: un proceso libera los recursos que tiene antes de solicitar nuevos.
La primera forma se llama asignación atómica de recursos. Es efectiva pero puede ser ineficiente: un proceso puede retener recursos que no necesita mientras espera otros.
/* Solicitar todos los recursos de una vez. */
void adquirir_recursos(int *recursos, int n) {
/* Intentar adquirir todos. */
for (int i = 0; i < n; i++) {
if (!try_lock(recursos[i])) {
/* No se pudo adquirir todos: liberar los adquiridos. */
for (int j = 0; j < i; j++) {
unlock(recursos[j]);
}
/* Esperar y reintentar. */
wait_and_retry(recursos, n);
return;
}
}
/* Todos adquiridos. */
}5. Romper la no apropiación
La no apropiación se rompe permitiendo quitar recursos a un proceso. Si un proceso tiene un recurso y otro proceso de mayor prioridad lo necesita, el sistema puede quitarle el recurso al primero.
Esto es complejo porque:
- El proceso al que se le quitó el recurso puede estar en un estado inconsistente.
- Hay que guardar el estado del proceso y restaurarlo cuando recupere el recurso.
- No es aplicable a todos los recursos (por ejemplo, un archivo no se puede «quitar»).
La apropiación se usa en sistemas operativos para la CPU (el planificador puede quitarle la CPU a un proceso), pero rara vez para otros recursos.
6. Romper la espera circular
La espera circular se rompe imponiendo un orden total en la adquisición de recursos. Si los recursos se numeran y los procesos los adquieren en orden creciente, no puede haber un ciclo.
Esta es la técnica más usada y la más práctica. Se llama orden de bloqueo (lock ordering).
El orden de bloqueo es la técnica de prevención más usada en la práctica. Es simple de implementar y efectiva. La única dificultad es que todos los programadores deben respetar el mismo orden.
7. El orden de bloqueo
El orden de bloqueo (lock ordering) consiste en asignar un número a cada recurso (mutex, semáforo, etc.) y exigir que los procesos los adquieran en orden creciente. Si un proceso tiene el recurso R5, solo puede adquirir R6 o superior, nunca R4 o inferior.
El orden de bloqueo rompe la espera circular porque no puede haber un ciclo: si todos adquieren en orden creciente, la cadena de espera siempre va hacia arriba, nunca vuelve al principio.
La implementación requiere:
- Asignar un orden: cada mutex tiene un número (por ejemplo, por dirección de memoria o por nombre).
- Verificar el orden: al adquirir un mutex, verificar que su número sea mayor que el del último adquirido.
- Documentar: todos los programadores deben conocer el orden.
En la práctica, el orden se suele asignar por la dirección de memoria del mutex (menor dirección = mayor prioridad) o por un nombre explícito.
8. Un ejemplo desarrollado
El ejemplo del tema 35 (dos hilos, dos mutexes) se arregla con orden de bloqueo:
#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
/* Asignar orden: mutex_a = 1, mutex_b = 2. */
pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER; /* orden 1 */
pthread_mutex_t mutex_b = PTHREAD_MUTEX_INITIALIZER; /* orden 2 */
void *hilo_1(void *arg) {
/* Adquirir en orden: a (1) luego b (2). */
pthread_mutex_lock(&mutex_a);
pthread_mutex_lock(&mutex_b);
/* ... usar ambos ... */
pthread_mutex_unlock(&mutex_b);
pthread_mutex_unlock(&mutex_a);
return NULL;
}
void *hilo_2(void *arg) {
/* Adquirir en el mismo orden: a (1) luego b (2). */
pthread_mutex_lock(&mutex_a); /* antes era mutex_b primero */
pthread_mutex_lock(&mutex_b);
/* ... usar ambos ... */
pthread_mutex_unlock(&mutex_b);
pthread_mutex_unlock(&mutex_a);
return NULL;
}Con el mismo orden de adquisición, no puede haber deadlock: si Hilo 2 quiere mutex_a y Hilo 1 lo tiene, Hilo 2 espera. Cuando Hilo 1 libera mutex_a, Hilo 2 lo adquiere y luego adquiere mutex_b (que Hilo 1 ya liberó). No hay ciclo.
9. Ventajas y desventajas
| Técnica | Ventaja | Desventaja |
|---|---|---|
| Orden de bloqueo | Simple, efectiva, sin overhead en tiempo de ejecución. | Requiere disciplina de todos los programadores. Difícil de mantener en código grande. |
| Asignación atómica | Previene deadlock completamente. | Puede retener recursos innecesariamente. Ineficiente. |
| Apropiación | Permite quitar recursos a procesos. | Compleja, puede causar inconsistencias. |
| Compartir recursos | Elimina la exclusión mutua. | No aplicable a todos los recursos. |
El orden de bloqueo es la técnica más usada en la práctica porque es simple y no tiene overhead. La única dificultad es mantener la disciplina en equipos grandes.
10. Prevención en Linux
Linux usa varias técnicas de prevención:
- Orden de bloqueo: el núcleo tiene un orden parcial de locks. Los locks se adquieren en un orden definido por su tipo.
- lockdep: una herramienta del núcleo que detecta violaciones del orden de bloqueo en tiempo de ejecución. Si un lock se adquiere en un orden incorrecto, lockdep imprime una advertencia.
- Asignación atómica: para algunos recursos, el núcleo solicita todos los locks necesarios de una vez.
- Preemption: el núcleo puede preemptar un proceso que tiene un lock (en algunos casos).
lockdep es una herramienta invaluable para detectar deadlocks en el núcleo. Se activa con CONFIG_LOCKDEP y verifica el orden de todos los locks en tiempo de ejecución.
11. Simulador interactivo
Este simulador muestra cómo el orden de bloqueo previene el deadlock:
Simulador · orden de bloqueo
12. Resumen
- La prevención rompe una de las cuatro condiciones de Coffman.
- La exclusión mutua se rompe haciendo recursos compartibles (raramente aplicable).
- La retención y espera se rompe con asignación atómica de recursos.
- La no apropiación se rompe con preemption (complejo).
- La espera circular se rompe con orden de bloqueo (la técnica principal).
- El orden de bloqueo asigna un número a cada recurso y exige adquisición en orden creciente.
- Linux usa lockdep para verificar el orden de bloqueo en tiempo de ejecución.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es la prevención de interbloqueos?
Diseñar el programa para que no se puedan cumplir las cuatro condiciones de Coffman simultáneamente.
2. ¿Cuál es la técnica de prevención más usada?
El orden de bloqueo (lock ordering).
3. ¿Cómo rompe el orden de bloqueo la espera circular?
Imponiendo un orden total en la adquisición de recursos. No puede haber un ciclo si todos adquieren en orden creciente.
4. ¿Qué es la asignación atómica de recursos?
Solicitar todos los recursos de una vez, o liberar antes de solicitar nuevos.
5. ¿Qué condición rompe la asignación atómica?
La retención y espera.
6. ¿Qué es lockdep?
Una herramienta del núcleo de Linux que detecta violaciones del orden de bloqueo.
7. ¿Por qué la apropiación es difícil de implementar?
Porque el proceso al que se le quitó el recurso puede estar en un estado inconsistente.
8. ¿Por qué la exclusión mutua es difícil de romper?
Porque los recursos que requieren exclusión mutua no se pueden compartir.
9. ¿Qué desventaja tiene el orden de bloqueo?
Requiere disciplina de todos los programadores. Difícil de mantener en código grande.
10. ¿Qué técnica usa Linux para verificar el orden de bloqueo?
lockdep (CONFIG_LOCKDEP).
Para practicar
- Modifica el programa de deadlock del tema 35 para usar orden de bloqueo.
- Implementa la asignación atómica de recursos.
- Explica por qué el orden de bloqueo rompe la espera circular.
- Investiga cómo funciona lockdep en el núcleo de Linux.
- Diseña un esquema de orden de bloqueo para un programa con 5 mutexes.
- Explica por qué la exclusión mutua es la condición más difícil de romper.