1. Introducción: La cena de los filósofos y las cuatro condiciones de Coffman (1971)

En 1965, el científico de la computación neerlandés Edsger W. Dijkstra formuló el célebre problema de la cena de los filósofos (Dining Philosophers Problem): cinco filósofos $P_0 \dots P_4$ se sientan alrededor de una mesa circular; entre cada par de platos de espaguetis hay un único tenedor ($F_0 \dots F_4$). Para comer, cada filósofo necesita sostener simultáneamente su tenedor izquierdo $F_i$ y su tenedor derecho $F_{(i+1)\bmod 5}$. Si los cinco filósofos sienten hambre en el mismo microsegundo y todos toman su tenedor izquierdo $F_i$, cada uno esperará eternamente a que su vecino derecho suelte el segundo tenedor: todo el sistema se detiene para siempre. Esto es un interbloqueo o bloqueo mutuo (Deadlock).

Formalmente, un subconjunto no vacío de procesos $D \subseteq \mathcal{P}$ está en interbloqueo si y solo si cada proceso $P_i \in D$ está bloqueado esperando un evento (como la liberación de un recurso) que solo puede ser provocado por otro proceso $P_j \in D$ perteneciente al mismo conjunto de espera.

En 1971, Edward G. Coffman Jr., M. J. Elphick y Arie Shoshani demostraron que un interbloqueo de recursos solo puede ocurrir si se cumplen simultáneamente cuatro condiciones necesarias:

1. Exclusión mutua (Mutual Exclusion): Al menos un recurso se mantiene en modo exclusivo (no compartible).
2. Retención y espera (Hold and Wait): Un proceso retiene al menos un recurso mientras espera bloqueado para adquirir recursos adicionales retenidos por otros procesos.
3. Sin expropiación (No Preemption): Los recursos asignados no pueden arrebatarse por la fuerza; solo son liberados voluntariamente por su poseedor.
4. Espera circular (Circular Wait): Existe una cadena cerrada de procesos $\{P_0, P_1, \dots, P_{k-1}\}$ tal que cada $P_i$ espera un recurso retenido por $P_{(i+1)\bmod k}$.

Como las cuatro condiciones son individualmente necesarias, negar lógicamente una sola de ellas hace que el interbloqueo sea matemáticamente imposible ($0\,\%$).

2. Grafo de Asignación de Recursos (RAG) y teoremas de ciclos (Holt, 1972)

En 1972, Richard C. Holt modeló el estado de los recursos mediante un grafo dirigido bipartito llamado Grafo de Asignación de Recursos (RAG) $G = (V, E)$, con vértices $V = \mathcal{P} \cup \mathcal{R}$ (procesos $P_i$ y tipos de recursos $R_j$ con $W_j \ge 1$ instancias idénticas), aristas de solicitud $P_i \to R_j$ y aristas de asignación $R_j \to P_i$.

Tres teoremas fundamentales relacionan los ciclos dirigidos de $G$ con el interbloqueo:

• Teorema 1 (Aciclicidad $\implies$ Ausencia de interbloqueo): Si $G$ no contiene ciclos dirigidos (es un DAG), ningún proceso está en interbloqueo.
• Teorema 2 (Condición necesaria y suficiente con instancia única): Si cada tipo de recurso tiene una sola instancia ($\forall j, W_j = 1$), entonces ciclo dirigido en $G \iff$ interbloqueo.
• Teorema 3 (No suficiencia con múltiples instancias): Si algún recurso tiene múltiples instancias ($\exists j, W_j > 1$), la existencia de un ciclo dirigido es condición necesaria pero NO suficiente para el interbloqueo.

  flowchart TD
    subgraph RAG_Single["Caso A: RAG de instancia única (Ciclo <==> Interbloqueo seguro)"]
        PA1(("P1 (Bloqueado)")) -->|"Solicita"| RA1["R1 (1 instancia: ●)"]
        RA1 -->|"Asignado a"| PA2(("P2 (Bloqueado)"))
        PA2 -->|"Solicita"| RA2["R2 (1 instancia: ●)"]
        RA2 -->|"Asignado a"| PA1
    end

    subgraph RAG_Multi["Caso B: RAG multi-instancia (Existe ciclo P1->R1->P3->R2->P1 pero CERO interbloqueo)"]
        PB1(("P1 (Bloqueado)")) -->|"Solicita"| RB1["R1 (2 instancias: ●●)"]
        RB1 -->|"Instancia #1"| PB3(("P3 (Bloqueado)"))
        PB3 -->|"Solicita"| RB2["R2 (2 instancias: ●●)"]
        RB2 -->|"Instancia #1"| PB1
        RB1 -->|"Instancia #2"| PB2(("P2 (EJECUTANDO: ¡Sin solicitudes!)"))
        RB2 -->|"Instancia #2"| PB4(("P4 (EJECUTANDO: ¡Sin solicitudes!)"))
    end

En el Caso B existe el ciclo $P_1 \to R_1 \to P_3 \to R_2 \to P_1$, pero $P_2$ y $P_4$ tienen grado de salida $0$ (sumideros en ejecución): en cuanto terminen y liberen sus instancias de $R_1$ y $R_2$, el ciclo se romperá automáticamente.

3. Estrategia 1 (Prevención): Demostración por contradicción del orden total de cerrojos

En núcleos de SO (como el validador lockdep de Linux) y aplicaciones multihilo, la condición 4 (espera circular) se elimina imponiendo un orden total de cerrojos (Total Lock Ordering): se asigna a cada cerrojo $L \in \mathcal{L}$ un rango global único $\phi(L) \in \mathbb{N}$ y todo hilo que retenga el conjunto $\mathcal{H}$ solo puede solicitar un nuevo cerrojo $L_{\text{new}}$ si su rango es estrictamente mayor:

【Demostración por reducción al absurdo】: Supongamos que se forma un ciclo de espera $\{P_0, P_1, \dots, P_{k-1}\}$ ($k \ge 2$), donde $P_i$ retiene $L_i$ y espera $L_{(i+1)\bmod k}$. Como todos cumplen la regla de orden estricto, al encadenar las desigualdades alrededor del ciclo resulta:

Ningún número natural puede ser estrictamente menor que sí mismo ($\bot$). Por tanto, ya sea en transferencias bancarias (bloquear siempre primero la cuenta con menor ID) o en la cena de los filósofos (hacer que $P_4$ tome primero su tenedor derecho $F_0$ antes que el izquierdo $F_4$, pues $0 < 4$), la espera circular es imposible. $\blacksquare$

4. Estrategia 2 (Evitación): Algoritmo del banquero de Dijkstra (Traza matricial 5×3)

Cuando el orden de bloqueo depende de los datos en tiempo de ejecución, el algoritmo del banquero de Dijkstra (1965 / Habermann, 1969) exige declarar de antemano la demanda máxima $\mathbf{Max}$ y comprueba en tiempo $O(m \cdot n^2)$ antes de cada concesión si el estado resultante sigue siendo un estado seguro (Safe State) con al menos una secuencia segura (Safe Sequence) ($\text{Interbloqueado} \subsetneq \text{Estado inseguro}$).

Para $n=5$ procesos $\{P_0 \dots P_4\}$ y $m=3$ recursos con $\mathbf{Total} = (A=10, B=5, C=7)$ y suma asignada $(7,2,5)$, el vector disponible inicial es $\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}$:

La secuencia segura $\langle P_1, P_3, P_4, P_0, P_2 \rangle$ demuestra que $t_0$ es seguro. Si $P_1$ solicita $(1,0,2)$, la asignación tentativa deja $\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)$ (concedida al instante). Pero si acto seguido $P_0$ solicita $(0,2,0)$, el disponible cae a $(2,1,0)$, que no cubre el $\mathbf{Need}$ de ningún proceso (estado inseguro): ¡el banquero rechaza la solicitud y bloquea a $P_0$!

5. Estrategias 3 y 4 (Detección WFG, Wait-Die/Wound-Wait, Avestruz) y Livelock vs. Inanición

Los SGBD relacionales (PostgreSQL, MySQL InnoDB) construyen un grafo de espera (Wait-For Graph, WFG) y buscan ciclos mediante DFS en $O(|V|+|E|)$, abortando (rollback) la transacción víctima con menor registro Undo (MySQL detecta al instante; PostgreSQL espera deadlock_timeout = 1s). Las bases de datos distribuidas (Google Spanner) emplean los protocolos con marcas de tiempo $\text{TS}(T_i)$ de Rosenkrantz et al. (1978): Wait-Die (no apropiativo) y Wound-Wait (apropiativo, con menos reinicios inútiles), conservando siempre la marca de tiempo original $\text{TS}(T_i)$ al reintentar para evitar la inanición. Para agotamientos rarísimos de tablas en SO de escritorio, UNIX y Windows aplican el algoritmo del avestruz (Ostrich Algorithm) ignorando el problema para no penalizar cada llamada al sistema diaria.

  flowchart TD
    Req["La transacción distribuida Ti solicita un cerrojo retenido por Tj"] --> Cmp{"Comparar marcas de tiempo: ¿TS(Ti) < TS(Tj)?<br/>(¿Es la solicitante Ti MÁS ANTIGUA que la poseedora Tj?)"}
    Cmp -->|"Sí: Ti es MÁS ANTIGUA (Older)"| WD1["[Wait-Die (no apropiativo)]: La antigua Ti ESPERA a la joven Tj (Viejo -> Joven)<br/>[Wound-Wait (apropiativo)]: ¡La antigua Ti HIERE (aborta) a Tj y toma el cerrojo!"]
    Cmp -->|"No: Ti es MÁS JOVEN (Younger)"| WD2["[Wait-Die (no apropiativo)]: La joven Ti MUERE (aborta y reintenta con mismo TS)<br/>[Wound-Wait (apropiativo)]: La joven Ti ESPERA pacientemente a la antigua Tj (Joven -> Viejo)"]

Por último, comparemos los tres fallos de vivacidad (Liveness):