Qué es un interbloqueo

1. Qué es un interbloqueo

Un interbloqueo (deadlock) ocurre cuando dos o más hilos se bloquean mutuamente esperando recursos que tienen los demás, y ninguno puede progresar. Es una situación de espera circular: cada hilo espera a que otro libere un recurso, pero ese otro también está esperando.

El interbloqueo es el peor fallo de la sincronización porque es silencioso: no hay error, no hay crash, no hay mensaje. El programa simplemente deja de avanzar. Los hilos están bloqueados para siempre, consumiendo memoria y otros recursos, pero sin hacer trabajo útil.

El interbloqueo fue estudiado formalmente por Edward Coffman en 1971, quien identificó las cuatro condiciones necesarias para que ocurra.

2. Un ejemplo desarrollado

Dos hilos y dos mutexes. Cada hilo adquiere los dos mutexes, pero en orden diferente:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_b = PTHREAD_MUTEX_INITIALIZER;

void *hilo_1(void *arg) {
    pthread_mutex_lock(&mutex_a);   /* adquiere A */
    sleep(1);                      /* simular trabajo */
    pthread_mutex_lock(&mutex_b);   /* espera B (bloqueado) */
    /* ... usar ambos mutexes ... */
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
    return NULL;
}

void *hilo_2(void *arg) {
    pthread_mutex_lock(&mutex_b);   /* adquiere B */
    sleep(1);                      /* simular trabajo */
    pthread_mutex_lock(&mutex_a);   /* espera A (bloqueado) */
    /* ... usar ambos mutexes ... */
    pthread_mutex_unlock(&mutex_a);
    pthread_mutex_unlock(&mutex_b);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, hilo_1, NULL);
    pthread_create(&t2, NULL, hilo_2, NULL);
    pthread_join(t1, NULL);  /* nunca retorna */
    pthread_join(t2, NULL);  /* nunca retorna */
    return 0;
}

Escenario de deadlock:

1. t = 0: Hilo 1 adquiere mutex_a. Hilo 2 adquiere mutex_b. adquirir
2. t = 1: Hilo 1 intenta adquirir mutex_b. Está ocupado (Hilo 2 lo tiene). Hilo 1 se bloquea. bloquear
3. t = 1: Hilo 2 intenta adquirir mutex_a. Está ocupado (Hilo 1 lo tiene). Hilo 2 se bloquea. bloquear
4. t = ∞: Ambos hilos bloqueados para siempre. Deadlock. deadlock

El programa nunca termina. pthread_join espera indefinidamente. El único forma de salir es matar el proceso (Ctrl+C o kill).

3. Las cuatro condiciones de Coffman

Edward Coffman identificó en 1971 que un interbloqueo solo puede ocurrir si se cumplen las cuatro condiciones simultáneamente:

Si cualquiera de estas cuatro condiciones no se cumple, no puede haber deadlock. Por eso, las técnicas de prevención rompen una de estas condiciones.

4. Condición 1: exclusión mutua

La exclusión mutua significa que un recurso solo puede ser usado por un proceso a la vez. Esta condición es inherente a los recursos que no son compartibles (como los mutexes, los archivos en modo exclusivo, etc.).

Los recursos que son compartibles (como la memoria de solo lectura, los archivos en modo lectura) no requieren exclusión mutua y no pueden causar deadlock.

Para romper esta condición, se harían los recursos compartibles (por ejemplo, permitir que varios hilos lean el mismo archivo simultáneamente). Pero esto no es posible para recursos que requieren exclusión mutua (como un mutex).

5. Condición 2: retención y espera

La retención y espera significa que un proceso que tiene un recurso puede solicitar otro. Esto es lo que causa el deadlock: un hilo tiene mutex_a y solicita mutex_b.

Para romper esta condición, se requiere que un proceso solicite todos los recursos que necesita de una vez, o que libere los recursos que tiene antes de solicitar nuevos. Esto se llama asignación atómica de recursos.

6. Condición 3: no apropiación

La no apropiación significa que un recurso no se puede quitar a un proceso; solo se libera voluntariamente. Esto es típico de los mutexes y otros recursos de sincronización.

Para romper esta condición, se permite quitar recursos a un proceso (preemption). Por ejemplo, si un hilo tiene un mutex y otro hilo de mayor prioridad lo necesita, el sistema puede quitarle el mutex al primero. Esto es complejo y puede causar inconsistencias.

7. Condición 4: espera circular

La espera circular significa que existe una cadena circular de procesos, cada uno esperando un recurso del siguiente. Esta es la condición más fácil de romper: basta con imponer un orden en la adquisición de recursos.

Para romper esta condición, se asigna un orden total a los recursos y se requiere que los procesos los adquieran en ese orden. Por ejemplo, si los mutexes se numeran, un proceso solo puede adquirir mutex_b después de haber adquirido mutex_a (si a < b).

8. Las cuatro simultáneamente

En el ejemplo del tema, las cuatro condiciones se cumplen:

1. Exclusión mutua: mutex_a y mutex_b solo pueden ser usados por un hilo a la vez. mutex
2. Retención y espera: Hilo 1 tiene mutex_a y solicita mutex_b. Hilo 2 tiene mutex_b y solicita mutex_a. hold & wait
3. No apropiación: ni el sistema ni el otro hilo pueden quitarle el mutex al hilo que lo tiene. no preemption
4. Espera circular: Hilo 1 espera mutex_b (Hilo 2), Hilo 2 espera mutex_a (Hilo 1). ciclo

Si se rompe cualquiera de estas cuatro, no hay deadlock. Las técnicas de prevención (tema 37) rompen una de estas condiciones.

9. Tipos de interbloqueo

Los interbloqueos se clasifican en:

10. Interbloqueo vs. inanición

El interbloqueo y la inanición son problemas distintos:

Un sistema puede tener inanición sin interbloqueo (un proceso de baja prioridad espera indefinidamente, pero los demás progresan). Y un sistema puede tener interbloqueo sin inanición (los procesos bloqueados no progresan, pero no es por prioridad).

11. Simulador interactivo

Este simulador muestra cómo se produce un deadlock y cómo se puede evitar:

12. Resumen

• Un interbloqueo ocurre cuando procesos se esperan mutuamente para siempre.
• Las cuatro condiciones de Coffman deben cumplirse simultáneamente.
• Las condiciones son: exclusión mutua, retención y espera, no apropiación, espera circular.
• Si se rompe una condición, no hay deadlock.
• El interbloqueo es silencioso: no hay error ni crash.
• El interbloqueo afecta a todos los procesos involucrados.
• La inanición es un problema distinto: afecta a un proceso individual.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta deadlock.c y observa que el programa se bloquea.
2. Modifica el programa para adquirir los mutexes en el mismo orden y verifica que no hay deadlock.
3. Dibuja el grafo de asignación de recursos para el ejemplo.
4. Explica qué condición se rompe en cada técnica de prevención.
5. Diseña un programa con 3 hilos y 3 mutexes que se bloquee.
6. Investiga cómo detecta deadlock el núcleo de Linux.