← Volver al listado de tecnologías ← Índice de Sistemas Operativos de 0 a Hero

Concurrencia y sus problemas: condiciones de carrera, sección crítica, interbloqueo e inanición

16 de agosto de 2026 Por: Artiko

sistemas-operativosadaelixirconcurrenciacondiciones-de-carreraseccion-criticaexclusion-mutuainterbloqueopeterson

Concurrencia y sus problemas: condiciones de carrera, sección crítica, interbloqueo e inanición

En el capítulo 6 quedó establecido que el sistema operativo puede detener un flujo de ejecución en casi cualquier punto, guardar su contexto y ceder el procesador a otro. Ese mecanismo es lo que permite que un computador con cuatro núcleos sostenga trescientos procesos. También es, exactamente, el origen de todos los problemas de este capítulo.

Cuando un solo flujo ejecuta un programa, el razonamiento es simple: la línea 10 corre después de la línea 9 y antes de la línea 11. Cuando hay dos flujos que comparten datos, esa garantía desaparece. Entre dos instrucciones cualesquiera de un hilo puede haber cero, una o diez mil instrucciones del otro hilo. El programa ya no tiene una historia: tiene un conjunto enorme de historias posibles, y basta con que una de ellas produzca un resultado incorrecto para que el programa sea incorrecto.

Este capítulo trata de identificar esas historias, ponerles nombre y neutralizarlas. Empieza desde cero —qué es concurrencia, qué es paralelismo— y termina resolviendo los tres problemas clásicos de sincronización con código que compila y corre.

Concurrencia y paralelismo no son lo mismo

Las dos palabras se usan como sinónimos en conversación informal, pero describen cosas distintas.

Concurrencia es una propiedad de la estructura del programa: hay varias actividades vivas al mismo tiempo, cada una con su propio avance, y el programa está escrito de modo que sus intercalados sean válidos. La concurrencia existe aunque haya un solo núcleo: el planificador alterna entre las actividades y ninguna termina antes de que otra empiece.

Paralelismo es una propiedad de la ejecución: dos o más instrucciones se ejecutan literalmente en el mismo instante físico, en unidades de cómputo distintas. El paralelismo exige hardware múltiple: varios núcleos, varios procesadores, varias máquinas.

De ahí se sigue una relación asimétrica: todo programa paralelo es concurrente, pero un programa concurrente puede ejecutarse sin ningún paralelismo. Y lo importante para este capítulo: los errores de concurrencia no necesitan paralelismo para aparecer. Un solo núcleo con conmutación de contexto los produce igual.

flowchart TB
    subgraph CONC["Concurrencia — 1 núcleo, intercalado en el tiempo"]
        direction LR
        C1["A: instr 1-3"] --> C2["B: instr 1-2"] --> C3["A: instr 4-6"] --> C4["B: instr 3-7"] --> C5["A: instr 7"]
    end

    subgraph PAR["Paralelismo — 2 núcleos, ejecución simultánea"]
        direction LR
        subgraph N0["Núcleo 0"]
            P1["A: instr 1-7"]
        end
        subgraph N1["Núcleo 1"]
            P2["B: instr 1-7"]
        end
    end

    CONC -.->|"misma estructura de programa"| PAR

    style CONC fill:#1e3a5f,color:#fff
    style PAR fill:#1e5f3a,color:#fff

La tabla siguiente resume las diferencias que importan al escribir código.

Aspecto	Concurrencia	Paralelismo
Qué describe	Cómo está estructurado el programa	Cómo se ejecuta físicamente
Hardware mínimo	Un núcleo	Dos o más núcleos
Objetivo principal	Modelar actividades independientes, no bloquearse en E/S	Reducir el tiempo total de cómputo
Ganancia típica	Capacidad de respuesta, uso del procesador durante esperas	Aceleración proporcional a los núcleos
Simultaneidad real	No garantizada	Garantizada
¿Genera condiciones de carrera?	Sí	Sí, y con ventanas más grandes
Ejemplo	Servidor que atiende mil conexiones con ocho hilos	Multiplicar dos matrices repartiendo filas entre núcleos

Un detalle que suele confundir: pasar de un núcleo a ocho no crea errores nuevos de concurrencia, pero sí hace muchísimo más probable que los errores latentes se manifiesten. Un error que en un núcleo aparecía una vez cada millón de ejecuciones puede aparecer una vez cada mil en ocho núcleos.

Por qué los programas concurrentes son difíciles

Hay tres razones concretas, y conviene nombrarlas antes de ver un solo ejemplo.

No determinismo

Un programa secuencial es determinista: mismas entradas, misma salida, siempre. Un programa concurrente no lo es. La salida depende de decisiones del planificador que no están bajo control del programa y que dependen de carga del sistema, interrupciones, temperatura del procesador y frecuencia de reloj.

Esto invierte la lógica habitual de las pruebas. En secuencial, si el programa pasa el test, el camino que ejercitó el test es correcto. En concurrente, si el programa pasa el test, lo único que sabes es que ese intercalado particular fue correcto. Los otros millones de intercalados siguen sin verificar.

Atomicidad no evidente

Una línea de código fuente no es una unidad indivisible. contador = contador + 1 son al menos tres operaciones de máquina: leer memoria, sumar, escribir memoria. El planificador puede interrumpir entre cualquiera de ellas. La atomicidad —la propiedad de que una operación ocurra completa o no ocurra— hay que construirla explícitamente; no viene por defecto.

Bohrbugs y Heisenbugs

Los errores de programas secuenciales suelen ser Bohrbugs: sólidos, reproducibles, siempre en el mismo lugar con las mismas entradas. Se llaman así por el modelo atómico de Bohr, con electrones en órbitas fijas y predecibles.

Los errores de concurrencia tienden a ser Heisenbugs: cambian o desaparecen cuando se los observa. Agregar un printf para depurar altera los tiempos y el error deja de reproducirse. Compilar sin optimizaciones cambia el código generado y el error se esconde. Correr bajo un depurador serializa la ejecución y el error nunca aparece. El nombre alude al principio de incertidumbre de Heisenberg.

Tipo de error	Reproducible	Sensible a la observación	Estrategia de diagnóstico
Bohrbug	Sí, siempre	No	Depurador paso a paso, bisección del código
Heisenbug	Intermitente	Sí, mucho	Razonamiento sobre intercalados, detectores dinámicos, revisión de invariantes

La consecuencia práctica es que la corrección de un programa concurrente se argumenta, no se prueba a fuerza de ejecuciones. Hay que identificar los datos compartidos, los invariantes que deben mantenerse y demostrar que ningún intercalado los rompe.

La condición de carrera, desarmada

Una condición de carrera ocurre cuando el resultado de un cómputo depende del orden relativo en que dos o más flujos acceden a un dato compartido, y al menos uno de esos accesos es una escritura.

El caso más pequeño posible es un contador.

/* contador_roto.c — compilar: gcc -O0 -pthread contador_roto.c -o contador_roto */
#include <pthread.h>
#include <stdio.h>

#define VUELTAS 1000000

static long contador = 0;

static void *sumar(void *arg)
{
    (void) arg;
    for (int i = 0; i < VUELTAS; i++) {
        contador = contador + 1;
    }
    return NULL;
}

int main(void)
{
    pthread_t h1, h2;

    pthread_create(&h1, NULL, sumar, NULL);
    pthread_create(&h2, NULL, sumar, NULL);
    pthread_join(h1, NULL);
    pthread_join(h2, NULL);

    printf("Esperado: %d\n", 2 * VUELTAS);
    printf("Obtenido: %ld\n", contador);
    printf("Perdidos: %ld\n", (long) (2 * VUELTAS) - contador);
    return 0;
}

El valor esperado es 2 000 000. En una máquina multinúcleo el resultado obtenido suele estar entre 1 000 000 y 2 000 000, y cambia en cada ejecución. Se compila con -O0 a propósito: con optimizaciones el compilador puede mantener el contador en un registro y el efecto se altera.

Qué instrucciones hay realmente debajo

En una arquitectura x86-64, la línea contador = contador + 1 se traduce aproximadamente a tres instrucciones:

mov    contador(%rip), %rax    ; LEER:     copiar memoria al registro
add    $1, %rax                ; MODIFICAR: sumar 1 en el registro
mov    %rax, contador(%rip)    ; ESCRIBIR: copiar el registro a memoria

Este patrón se llama leer-modificar-escribir, y es el corazón de casi toda condición de carrera. El problema es que entre la lectura y la escritura hay una ventana en la que el valor en memoria puede cambiar sin que este hilo se entere.

sequenceDiagram
    participant A as Hilo A
    participant M as Memoria — contador
    participant B as Hilo B

    Note over M: contador = 41
    A->>M: LEER
    M-->>A: 41
    Note over A: registro A = 41
    Note over A,B: cambio de contexto
    B->>M: LEER
    M-->>B: 41
    Note over B: registro B = 41
    Note over B: SUMAR → registro B = 42
    B->>M: ESCRIBIR 42
    Note over M: contador = 42
    Note over A,B: cambio de contexto
    Note over A: SUMAR → registro A = 42
    A->>M: ESCRIBIR 42
    Note over M: contador = 42 — se perdió un incremento

Dos incrementos ejecutados, un solo incremento visible. Esa es la actualización perdida, y es la forma más común de condición de carrera.

La variante verificar-y-actuar

La otra forma común no pierde datos: rompe una condición. El patrón es leer un valor, decidir algo en función de él y actuar suponiendo que el valor sigue siendo el mismo.

/* banco_roto.c — compilar: gcc -O0 -pthread banco_roto.c -o banco_roto */
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

static int fondos = 100;

static void *retirar(void *arg)
{
    int monto = *(int *) arg;

    if (monto <= fondos) {            /* VERIFICAR */
        usleep(1000);                 /* ventana: el planificador puede intervenir */
        fondos = fondos - monto;      /* ACTUAR */
        printf("retira %d, saldo queda en %d\n", monto, fondos);
    } else {
        printf("rechaza %d: fondos insuficientes\n", monto);
    }
    return NULL;
}

int main(void)
{
    pthread_t h1, h2;
    int ana = 80, beto = 70;

    pthread_create(&h1, NULL, retirar, &ana);
    pthread_create(&h2, NULL, retirar, &beto);
    pthread_join(h1, NULL);
    pthread_join(h2, NULL);

    printf("Saldo final: %d\n", fondos);   /* -50: estado declarado imposible */
    return 0;
}

Ambos hilos verifican contra un saldo de 100, ambos pasan la verificación, ambos restan. El saldo final es -50, un estado que el programa declara imposible. El usleep no crea el error: sólo agranda una ventana que ya existía y que en producción se abre unas pocas veces al día.

El invariante violado es fondos >= 0. Y hay que decirlo con precisión: el invariante sí se cumple al inicio y sí se cumpliría si cada retiro se ejecutara completo antes del siguiente. Lo que lo rompe es el intercalado.

El mismo error sin memoria compartida

Podría parecer que este problema es exclusivo de lenguajes con memoria compartida. No lo es: reaparece en cualquier modelo donde el estado se consulte y se modifique en dos pasos separados. En Elixir, donde los procesos no comparten memoria, el error se traslada al protocolo de mensajes.

# banco_roto.exs — ejecutar: elixir banco_roto.exs
{:ok, cuenta} = Agent.start_link(fn -> 100 end)

retirar = fn quien, monto ->
  saldo = Agent.get(cuenta, & &1)          # mensaje 1: VERIFICAR
  Process.sleep(50)                        # ventana entre los dos mensajes

  if monto <= saldo do
    Agent.update(cuenta, &(&1 - monto))    # mensaje 2: ACTUAR
    IO.puts("#{quien} retira #{monto}")
  else
    IO.puts("#{quien} rechazado: fondos insuficientes")
  end
end

[
  Task.async(fn -> retirar.("Ana", 80) end),
  Task.async(fn -> retirar.("Beto", 70) end)
]
|> Enum.each(&Task.await/1)

IO.puts("Saldo final: #{Agent.get(cuenta, & &1)}")

Salida típica: ambos retiran y el saldo final es -50. El Agent serializa cada mensaje individualmente, pero nada serializa la pareja de mensajes. La corrección consiste en convertir verificar-y-actuar en una sola operación:

# banco_correcto.exs — ejecutar: elixir banco_correcto.exs
{:ok, cuenta} = Agent.start_link(fn -> 100 end)

retirar = fn quien, monto ->
  # Un solo mensaje: la decisión y la actualización viajan juntas.
  resultado =
    Agent.get_and_update(cuenta, fn saldo ->
      if monto <= saldo,
        do: {{:ok, saldo - monto}, saldo - monto},
        else: {{:rechazado, saldo}, saldo}
    end)

  case resultado do
    {:ok, nuevo} -> IO.puts("#{quien} retira #{monto}, saldo queda en #{nuevo}")
    {:rechazado, s} -> IO.puts("#{quien} rechazado: saldo #{s} < #{monto}")
  end
end

[Task.async(fn -> retirar.("Ana", 80) end), Task.async(fn -> retirar.("Beto", 70) end)]
|> Enum.each(&Task.await/1)

IO.puts("Saldo final: #{Agent.get(cuenta, & &1)}")

Ahora la decisión y la modificación viajan en el mismo mensaje y el proceso del Agent las ejecuta sin interrupción. El saldo final es 20 y el segundo retiro se rechaza. Esta es la lección general del capítulo, adelantada: la solución nunca es “hacer la ventana más pequeña”; es eliminar la ventana.

Sección crítica

El fragmento de código que accede a un recurso compartido y que no admite intercalado se llama sección crítica. No es una propiedad del recurso: es una propiedad del código que lo usa. El mismo arreglo puede tener secciones críticas en unos accesos y no en otros.

Todo hilo que use un recurso compartido tiene una estructura de cuatro partes:

stateDiagram-v2
    [*] --> Resto
    Resto: Sección restante — trabajo que no toca el recurso compartido
    Entrada: Protocolo de entrada — pedir permiso
    Critica: Sección crítica — acceso exclusivo al recurso
    Salida: Protocolo de salida — devolver el permiso

    Resto --> Entrada: necesita el recurso
    Entrada --> Entrada: permiso denegado, espera
    Entrada --> Critica: permiso concedido
    Critica --> Salida: terminó el acceso
    Salida --> Resto: recurso liberado

Todo el problema de la sincronización consiste en diseñar los protocolos de entrada y salida. La sección crítica y la sección restante las escribe el programador de la aplicación; los protocolos los aporta el sistema operativo, la biblioteca de hilos o el lenguaje.

Los cuatro requisitos de una solución correcta

Una solución al problema de la sección crítica se considera correcta si cumple los cuatro requisitos siguientes. Los tres primeros los formuló Dijkstra; el cuarto es una condición sobre el entorno de ejecución.

Requisito	Enunciado	Qué falla si no se cumple
Exclusión mutua	A lo sumo un hilo dentro de la sección crítica en cada instante	Condiciones de carrera: el problema original queda sin resolver
Progreso	Si la sección crítica está libre y hay hilos queriendo entrar, la decisión de quién entra no puede postergarse indefinidamente, y sólo participan en ella los hilos que quieren entrar	Interbloqueo: nadie entra aunque el recurso está libre
Espera limitada	Existe una cota al número de veces que otros hilos pueden entrar después de que un hilo pidió entrar y antes de que se le conceda	Inanición: un hilo espera para siempre mientras otros pasan
Sin suposiciones de velocidad	La solución no depende del número de procesadores ni de la velocidad relativa de los hilos	La solución funciona en el laboratorio y falla en producción

El requisito de progreso tiene una cláusula que se pasa por alto: sólo participan en la decisión los hilos que quieren entrar. Un hilo que está en su sección restante, o que terminó, no puede tener voto sobre quién entra. El primer intento fallido que veremos incumple exactamente esa cláusula.

Exclusión mutua: intentos por software

La pregunta histórica es si se puede resolver la sección crítica usando sólo lecturas y escrituras de memoria compartida, sin ninguna instrucción especial del procesador. La respuesta es sí, pero el camino hasta ahí pasa por varios intentos que fallan de maneras instructivas. Suponemos dos hilos, identificados como i y j, donde j = 1 - i.

Intento 1: turno estricto

La idea más directa: una variable compartida indica de quién es el turno.

/* Intento 1 — pseudocódigo en C, hilo i. Variable compartida: turno */
int turno = 0;

while (turno != i) { /* entrada: espera activa */ }
/* SECCIÓN CRÍTICA */
turno = j;                     /* salida */

Cumple exclusión mutua: turno tiene un solo valor, así que sólo un hilo puede pasar el while.

Incumple progreso. Si el hilo 0 sale de su sección crítica, pone turno = 1 y se dedica a su sección restante durante una hora, el hilo 1 puede entrar una vez, poner turno = 0 y quedar bloqueado indefinidamente aunque la sección crítica esté libre y el hilo 0 no la quiera. Un hilo que no está interesado está decidiendo por otro.

Además fuerza una alternancia estricta: si el hilo 0 necesita entrar diez veces y el hilo 1 sólo una, el hilo 0 no puede completar sus diez entradas.

Intento 2: banderas de interés

Se cambia el enfoque: cada hilo declara si quiere entrar.

/* Intento 2 — hilo i. Variable compartida: interes */
bool interes[2] = { false, false };

while (interes[j]) { /* entrada: espera a que el otro salga */ }
interes[i] = true;
/* SECCIÓN CRÍTICA */
interes[i] = false;            /* salida */

Incumple exclusión mutua, que es el requisito más importante. Basta este intercalado:

El hilo 0 evalúa interes[1], que es false, y sale del bucle.
Cambio de contexto antes de que el hilo 0 escriba su bandera.
El hilo 1 evalúa interes[0], que sigue siendo false, y sale del bucle.
Ambos ponen su bandera en true y ambos entran a la sección crítica.

La ventana entre “verificar” y “declarar” es la misma condición de carrera que se intentaba resolver.

Intento 3: declarar antes de verificar

La corrección obvia es invertir el orden: primero declarar el interés, después mirar el del otro.

/* Intento 3 — hilo i. Variable compartida: interes */
bool interes[2] = { false, false };

interes[i] = true;             /* entrada: declarar antes de mirar */
while (interes[j]) { /* espera */ }
/* SECCIÓN CRÍTICA */
interes[i] = false;            /* salida */

Cumple exclusión mutua: para que el hilo i entre, interes[j] tuvo que ser falso después de que interes[i] fuera verdadero, y eso no puede darse simétricamente.

Incumple progreso, por interbloqueo. Si ambos hilos ejecutan interes[i] = true antes de que cualquiera llegue al while, ambos ven la bandera del otro levantada y ambos esperan para siempre. Ninguno la bajará, porque bajarla ocurre después de la sección crítica, a la que nunca entrarán.

Es el interbloqueo en su forma más pura: cada uno retiene lo que el otro necesita y espera lo que el otro retiene.

Intento 4: ceder con espera aleatoria

Para romper el interbloqueo anterior, se agrega la posibilidad de ceder: si el otro está interesado, bajar la propia bandera, esperar un rato y volver a intentarlo.

/* Intento 4 — hilo i. Variable compartida: interes */
bool interes[2] = { false, false };

interes[i] = true;             /* entrada */
while (interes[j]) {
    interes[i] = false;        /* cedo el paso */
    esperar(aleatorio());
    interes[i] = true;         /* y lo vuelvo a intentar */
}
/* SECCIÓN CRÍTICA */
interes[i] = false;            /* salida */

Cumple exclusión mutua y no produce interbloqueo permanente, porque la aleatoriedad rompe la simetría con probabilidad 1.

Introduce en cambio un bloqueo vivo (livelock): ambos hilos pueden entrar en un patrón de cortesía mutua donde suben y bajan banderas indefinidamente sin que ninguno entre. Los hilos no están detenidos —consumen procesador, cambian de estado, avanzan instrucciones— pero el trabajo útil es nulo. Formalmente no hay garantía de progreso en tiempo acotado: sólo una garantía probabilística.

Este intento también deja abierta la inanición: si un hilo tiene sistemáticamente peor suerte con los tiempos aleatorios, puede quedar postergado indefinidamente.

flowchart TD
    I1["Intento 1<br/>Turno estricto"] -->|"un hilo no interesado<br/>bloquea al otro"| F1["Falla: progreso"]
    I2["Intento 2<br/>Verificar y luego declarar"] -->|"ventana entre<br/>verificar y declarar"| F2["Falla: exclusión mutua"]
    I3["Intento 3<br/>Declarar y luego verificar"] -->|"ambas banderas<br/>arriba a la vez"| F3["Falla: interbloqueo"]
    I4["Intento 4<br/>Ceder con espera aleatoria"] -->|"cortesía mutua<br/>sin avance"| F4["Falla: bloqueo vivo e inanición"]

    F1 --> SOL["Peterson<br/>banderas + turno como desempate"]
    F2 --> SOL
    F3 --> SOL
    F4 --> SOL
    SOL --> OK["Cumple los cuatro requisitos<br/>para dos hilos"]
    SOL --> PAN["Panadería de Lamport<br/>generalización a N hilos"]

    style F1 fill:#5f1e1e,color:#fff
    style F2 fill:#5f1e1e,color:#fff
    style F3 fill:#5f1e1e,color:#fff
    style F4 fill:#5f1e1e,color:#fff
    style OK fill:#1e5f3a,color:#fff
    style PAN fill:#1e5f3a,color:#fff

Algoritmo de Dekker

Dekker fue el primero en resolverlo, en 1962. Combina las banderas del intento 3 con la variable de turno del intento 1, pero usando el turno sólo como desempate cuando ambos hilos están interesados.

/* Dekker — hilo i, con j = 1 - i */
bool interes[2] = { false, false };
int  turno = 0;

interes[i] = true;                    /* entrada */
while (interes[j]) {
    if (turno != i) {                 /* el turno es del otro: cedo de verdad */
        interes[i] = false;
        while (turno != i) { /* espero hasta que me toque */ }
        interes[i] = true;
    }
}
/* SECCIÓN CRÍTICA */
turno = j;                            /* salida */
interes[i] = false;

La diferencia con el intento 4 es que el hilo que cede no espera un tiempo aleatorio: espera hasta que el turno sea suyo, y el turno sólo cambia cuando el otro sale de la sección crítica. Eso convierte el bloqueo vivo en una espera con final garantizado. Cumple los cuatro requisitos, pero el protocolo de entrada tiene dos bucles anidados y su corrección no es evidente a simple vista.

Algoritmo de Peterson

En 1981 Peterson publicó una versión de una décima parte del tamaño. La idea es que el hilo cede el turno al otro inmediatamente después de declarar su interés: se declara interesado y a la vez declara que si hay empate, gana el otro.

/* peterson.c — compilar: gcc -O2 -pthread peterson.c -o peterson */
#include <pthread.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>

#define VUELTAS 200000

static atomic_bool interes[2];
static atomic_int  turno;
static long        contador = 0;   /* protegido por el algoritmo */

static void *tarea(void *arg)
{
    int yo = *(int *) arg, otro = 1 - yo;

    for (int k = 0; k < VUELTAS; k++) {
        atomic_store(&interes[yo], true);          /* entrada: quiero entrar */
        atomic_store(&turno, otro);                /* si hay empate, gana el otro */
        while (atomic_load(&interes[otro]) && atomic_load(&turno) == otro) { }

        contador = contador + 1;                   /* sección crítica */

        atomic_store(&interes[yo], false);         /* salida */
    }
    return NULL;
}

int main(void)
{
    pthread_t h[2];
    int ids[2] = { 0, 1 };

    atomic_init(&interes[0], false);
    atomic_init(&interes[1], false);
    atomic_init(&turno, 0);

    pthread_create(&h[0], NULL, tarea, &ids[0]);
    pthread_create(&h[1], NULL, tarea, &ids[1]);
    pthread_join(h[0], NULL);
    pthread_join(h[1], NULL);

    printf("Esperado: %d\nObtenido: %ld\n", 2 * VUELTAS, contador);
    return 0;
}

La condición de espera es interes[otro] && turno == otro: el hilo espera sólo si el otro quiere entrar y además el turno es del otro. Si los dos declaran interés a la vez, los dos escriben turno, pero la escritura que queda es una sola, y esa escritura decide quién espera. La asimetría la produce la memoria, no la suerte.

Sobre stdatomic.h: el algoritmo de Peterson en su formulación original supone que las lecturas y escrituras de memoria se observan en el orden en que se escribieron. Los procesadores modernos y los compiladores optimizadores no garantizan eso: pueden reordenar una escritura respecto de una lectura posterior a otra dirección. Usar atomic_store y atomic_load, que por omisión tienen consistencia secuencial, es lo que hace que el programa funcione en hardware real. Escrito con bool y int corrientes, el programa puede fallar aunque el algoritmo sea correcto sobre el papel. Este punto es importante y se retoma más abajo.

Algoritmo de la panadería de Lamport

Peterson resuelve el caso de dos hilos. Para N hilos, Lamport propuso en 1974 una solución con la metáfora de la panadería: al entrar, cada cliente toma un número, y se atiende en orden creciente.

/* Panadería — pseudocódigo para N hilos, hilo i */
bool eligiendo[N] = { false };   /* está calculando su número */
int  numero[N]    = { 0 };       /* 0 significa "no quiere entrar" */

eligiendo[i] = true;                                   /* entrada */
numero[i] = 1 + maximo_de(numero, N);
eligiendo[i] = false;

for (int j = 0; j < N; j++) {
    while (eligiendo[j]) { /* espera a que j publique su número */ }
    /* espera a que j pase primero si su par (numero, id) es menor */
    while (numero[j] != 0 &&
           (numero[j] < numero[i] || (numero[j] == numero[i] && j < i))) { }
}
/* SECCIÓN CRÍTICA */
numero[i] = 0;                                         /* salida */

Dos detalles hacen que funcione:

El cálculo del máximo no es atómico, así que dos hilos pueden obtener el mismo número. El desempate es por identificador: el par (numero[i], i) sí es único, y la comparación lexicográfica sobre ese par define un orden total.
El arreglo eligiendo cubre la ventana en la que un hilo ya empezó a calcular su número pero todavía no lo publicó. Sin él, otro hilo podría ver numero[j] == 0 y adelantarse indebidamente.

La espera limitada se cumple con una cota clara: un hilo con número n espera a lo sumo a los hilos que tomaron número antes que él. Nadie que llegue después puede adelantarlo, porque tomará un número mayor.

Comparación de las soluciones por software

Algoritmo	Hilos soportados	Exclusión mutua	Progreso	Espera limitada	Complejidad del protocolo
Turno estricto	2	Sí	No	No aplica	Trivial
Banderas, verificar primero	2	No	Sí	No	Trivial
Banderas, declarar primero	2	Sí	No (interbloqueo)	No aplica	Trivial
Ceder aleatoriamente	2	Sí	Sólo probabilístico	No	Baja
Dekker	2	Sí	Sí	Sí	Media, bucles anidados
Peterson	2 (extensible con filtro)	Sí	Sí	Sí	Baja
Panadería de Lamport	N	Sí	Sí	Sí, cota explícita	Media, O(N) por entrada

Por qué en la práctica se usa hardware

Todas las soluciones anteriores comparten dos costos:

Espera activa. El hilo que no puede entrar quema ciclos de procesador en un bucle. En un sistema con un solo núcleo esto es especialmente costoso: el hilo que espera consume su cuanto completo impidiendo que corra el hilo que está dentro de la sección crítica y que es el único que puede liberarla. Este caso concreto tiene nombre: inversión de prioridad por espera activa.

Orden de memoria. Como se vio en Peterson, los procesadores fuera de orden y los compiladores optimizadores rompen las suposiciones sobre el orden de las operaciones de memoria.

Por eso todos los procesadores modernos ofrecen instrucciones atómicas de leer-modificar-escribir, que la memoria ejecuta como una sola operación indivisible. Las dos familias principales son:

Test-and-set: escribe un valor y devuelve el anterior, en una sola operación. En x86 corresponde a xchg; en C11 se expone como atomic_flag_test_and_set.
Compare-and-swap: compara el contenido con un valor esperado y, sólo si coincide, escribe uno nuevo; devuelve si tuvo éxito. En x86 corresponde a lock cmpxchg; en C11 se expone como atomic_compare_exchange_strong.

/* cerrojo_tas.c — cerrojo con test-and-set
   compilar: gcc -O2 -pthread cerrojo_tas.c -o cerrojo_tas */
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

#define VUELTAS 200000

static atomic_flag cerrojo = ATOMIC_FLAG_INIT;
static long contador = 0;

/* test-and-set devuelve el valor previo: si era false, el cerrojo es nuestro */
static void tomar(void)  { while (atomic_flag_test_and_set(&cerrojo)) { } }
static void soltar(void) { atomic_flag_clear(&cerrojo); }

static void *tarea(void *arg)
{
    (void) arg;
    for (int k = 0; k < VUELTAS; k++) {
        tomar();
        contador = contador + 1;   /* sección crítica */
        soltar();
    }
    return NULL;
}

int main(void)   /* cuatro hilos sobre el mismo contador */
{
    pthread_t h[4];
    for (int i = 0; i < 4; i++) pthread_create(&h[i], NULL, tarea, NULL);
    for (int i = 0; i < 4; i++) pthread_join(h[i], NULL);
    printf("Esperado: %d\nObtenido: %ld\n", 4 * VUELTAS, contador);
    return 0;
}

Este cerrojo cumple exclusión mutua y progreso para cualquier número de hilos, en cuatro líneas. No cumple espera limitada: nada impide que un hilo con mala suerte pierda la carrera del test-and-set indefinidamente. Y sigue haciendo espera activa.

El paso siguiente —convertir la espera activa en bloqueo real, con el hilo fuera de la cola de listos— es el trabajo del sistema operativo mediante semáforos y mutex, y es el tema del capítulo 8.

Interbloqueo, bloqueo vivo e inanición

Los tres nombres describen situaciones donde el trabajo útil se detiene, pero por causas distintas. Distinguirlos es lo que permite elegir la corrección adecuada.

Fenómeno	Estado de los hilos	¿Consume procesador?	Causa	¿Se resuelve solo?
Interbloqueo (deadlock)	Bloqueados	No	Espera circular de recursos	Nunca
Bloqueo vivo (livelock)	Ejecutables, cambiando de estado	Sí	Reacción mutua que impide avanzar	Sólo por azar, sin garantía
Inanición (starvation)	Ejecutable, pero postergado	Sí, sin avanzar	Política de asignación injusta	Sólo si cambia la carga

Una analogía que ayuda: el interbloqueo es un cruce de calles donde cuatro autos se bloquean mutuamente y ninguno se mueve; el bloqueo vivo es dos personas en un pasillo que se esquivan hacia el mismo lado una y otra vez; la inanición es esperar en una fila donde siempre llega alguien con prioridad y te adelanta.

Las cuatro condiciones de Coffman

Coffman, Elphick y Shoshani caracterizaron en 1971 el interbloqueo con cuatro condiciones que deben cumplirse todas a la vez. Si falta una sola, no hay interbloqueo. Esto es lo que las hace útiles: dan cuatro puntos de ataque.

Condición	Enunciado	Cómo se rompe	Costo de romperla
Exclusión mutua	El recurso sólo puede ser usado por un hilo a la vez	Hacer el recurso compartible o virtualizarlo (spooling de impresora, copias de sólo lectura)	No aplica a recursos intrínsecamente exclusivos
Retención y espera	Un hilo retiene recursos mientras pide otros	Pedir todos los recursos de una vez al inicio, o soltar todo antes de pedir más	Baja utilización: se reservan recursos que quizá no se usen
No apropiación	Un recurso no puede quitarse por la fuerza a quien lo tiene	Permitir revocar el recurso y reintentar la operación	Exige poder deshacer trabajo parcial
Espera circular	Existe una cadena cerrada donde cada hilo espera un recurso del siguiente	Imponer un orden total sobre los recursos y exigir que se pidan en ese orden	Requiere conocer todos los recursos de antemano

En la práctica, la técnica más usada es romper la espera circular con un orden total de adquisición, porque no reduce la utilización y no exige deshacer trabajo. Es la que aplicaremos a los filósofos comensales.

Interbloqueo en código real

/* interbloqueo.c — compilar: gcc -O2 -pthread interbloqueo.c -o interbloqueo
   Este programa se cuelga con alta probabilidad. Interrumpir con Ctrl-C. */
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

static pthread_mutex_t cuenta_a = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t cuenta_b = PTHREAD_MUTEX_INITIALIZER;

static void *transferir_a_b(void *arg)   /* toma A, luego pide B */
{
    (void) arg;
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&cuenta_a);
        usleep(1);
        pthread_mutex_lock(&cuenta_b);
        pthread_mutex_unlock(&cuenta_b);
        pthread_mutex_unlock(&cuenta_a);
    }
    return NULL;
}

static void *transferir_b_a(void *arg)   /* toma B, luego pide A */
{
    (void) arg;
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&cuenta_b);
        usleep(1);
        pthread_mutex_lock(&cuenta_a);
        pthread_mutex_unlock(&cuenta_a);
        pthread_mutex_unlock(&cuenta_b);
    }
    return NULL;
}

int main(void)
{
    pthread_t h1, h2;
    pthread_create(&h1, NULL, transferir_a_b, NULL);
    pthread_create(&h2, NULL, transferir_b_a, NULL);
    pthread_join(h1, NULL);
    pthread_join(h2, NULL);
    puts("Terminó sin interbloqueo (poco probable)");
    return 0;
}

El grafo de asignación de recursos deja el ciclo a la vista.

flowchart LR
    H1(["Hilo 1"])
    H2(["Hilo 2"])
    RA["Recurso A<br/>mutex cuenta_a"]
    RB["Recurso B<br/>mutex cuenta_b"]

    RA -->|"asignado a"| H1
    H1 -->|"solicita"| RB
    RB -->|"asignado a"| H2
    H2 -->|"solicita"| RA

    style H1 fill:#1e3a5f,color:#fff
    style H2 fill:#1e3a5f,color:#fff
    style RA fill:#5f1e1e,color:#fff
    style RB fill:#5f1e1e,color:#fff

Con una instancia por recurso, un ciclo en este grafo es condición necesaria y suficiente de interbloqueo. La corrección es imponer un orden y respetarlo en ambas funciones:

/* Corrección: se define el orden A < B y ambos hilos piden siempre A antes que B,
   aunque la lógica de negocio del segundo hilo sea "de B hacia A". */
static void *transferir_b_a_ordenado(void *arg)
{
    (void) arg;
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&cuenta_a);
        usleep(1);
        pthread_mutex_lock(&cuenta_b);
        pthread_mutex_unlock(&cuenta_b);
        pthread_mutex_unlock(&cuenta_a);
    }
    return NULL;
}

Con este cambio, el ciclo del grafo es imposible: nadie puede tener B y pedir A, porque A siempre se pide primero.

Estrategias frente al interbloqueo

Existen cuatro posturas, y los sistemas reales combinan varias.

Estrategia	En qué consiste	Dónde se usa
Prevención	Diseñar el sistema para que alguna condición de Coffman nunca se cumpla	Orden de adquisición de cerrojos en el kernel de Linux, documentado por subsistema
Evitación	Analizar cada solicitud y concederla sólo si el sistema queda en estado seguro, según necesidades máximas declaradas	Rara en propósito general: exige declarar por adelantado el uso máximo de recursos
Detección y recuperación	Permitir el interbloqueo, detectar ciclos periódicamente y romperlos abortando o revirtiendo	Gestores de bases de datos: detectan el ciclo y abortan la transacción más barata de deshacer
Ignorar	Suponer que el interbloqueo es raro y dejar que el operador reinicie	Sistemas de propósito general para recursos donde el costo del control supera al del incidente

Los tres problemas clásicos

Estos tres problemas se estudian porque cada uno aísla un patrón de sincronización distinto, y porque casi todo problema real es una variante de alguno.

Problema	Patrón que aísla	Riesgo principal	Aparece en
Productor-consumidor	Sincronización por disponibilidad de datos y de espacio	Sobreescritura, lectura de vacío, espera activa	Colas de trabajo, tuberías, buffers de E/S
Lectores-escritores	Exclusión asimétrica: muchos leen, uno escribe	Inanición de escritores o de lectores	Cachés, índices, tablas de configuración
Filósofos comensales	Adquisición de múltiples recursos con solapamiento	Interbloqueo por espera circular	Transferencias entre cuentas, bloqueo de filas en bases de datos

Productor-consumidor con buffer acotado

Un conjunto de hilos produce elementos y los deposita en un buffer de capacidad fija; otro conjunto los retira y los procesa. Hay tres condiciones que coordinar:

Exclusión mutua sobre la estructura del buffer, para que dos operaciones no corrompan los índices.
El consumidor no puede retirar de un buffer vacío: debe esperar.
El productor no puede depositar en un buffer lleno: debe esperar.

Las dos últimas no son exclusión mutua sino sincronización condicional: esperar a que se cumpla un predicado sobre el estado compartido.

sequenceDiagram
    participant P as Productor
    participant B as Buffer — capacidad 3
    participant C as Consumidor

    Note over B: [ _ _ _ ] cantidad = 0
    C->>B: Retirar
    Note over C: barrera cantidad > 0 falsa → queda en cola
    P->>B: Depositar 10
    Note over B: [10 _ _ ] cantidad = 1
    B-->>C: barrera se abre, entrega 10
    Note over B: [ _ _ _ ] cantidad = 0
    P->>B: Depositar 20
    P->>B: Depositar 30
    P->>B: Depositar 40
    Note over B: [20 30 40] cantidad = 3, lleno
    P->>B: Depositar 50
    Note over P: barrera cantidad < 3 falsa → queda en cola
    C->>B: Retirar
    B-->>C: entrega 20
    Note over B: barrera se abre, entra el depósito pendiente
    Note over B: [30 40 50] cantidad = 3

Ada resuelve esto con objetos protegidos: una construcción del lenguaje que combina exclusión mutua automática con barreras condicionales en las entradas. Una entrada sólo se ejecuta cuando su barrera es verdadera; mientras tanto, la tarea queda encolada sin consumir procesador.

--  productor_consumidor.adb
--  compilar y ejecutar:  gnatmake productor_consumidor.adb && ./productor_consumidor
with Ada.Text_IO; use Ada.Text_IO;

procedure Productor_Consumidor is

   type Vector_Enteros is array (Natural range <>) of Integer;

   --------------------------------------------------------------------
   --  Buffer circular acotado. Las barreras "when" son la
   --  sincronizacion condicional; la exclusion mutua la garantiza
   --  el propio objeto protegido.
   --------------------------------------------------------------------
   protected type Buffer_Acotado (Capacidad : Positive) is
      entry Depositar (Item : in  Integer);
      entry Retirar   (Item : out Integer);
   private
      Datos    : Vector_Enteros (0 .. Capacidad - 1);
      Cabeza   : Natural := 0;
      Cola     : Natural := 0;
      Cantidad : Natural := 0;
   end Buffer_Acotado;

   protected body Buffer_Acotado is

      entry Depositar (Item : in Integer) when Cantidad < Capacidad is
      begin
         Datos (Cola) := Item;
         Cola     := (Cola + 1) mod Capacidad;
         Cantidad := Cantidad + 1;
      end Depositar;

      entry Retirar (Item : out Integer) when Cantidad > 0 is
      begin
         Item     := Datos (Cabeza);
         Cabeza   := (Cabeza + 1) mod Capacidad;
         Cantidad := Cantidad - 1;
      end Retirar;

   end Buffer_Acotado;

   Buffer : Buffer_Acotado (Capacidad => 3);

   Total_Items : constant := 12;

   task Productor;
   task Consumidor;

   task body Productor is
   begin
      for I in 1 .. Total_Items loop
         Buffer.Depositar (I * 10);
         Put_Line ("Produce  ->" & Integer'Image (I * 10));
      end loop;
   end Productor;

   task body Consumidor is
      Item : Integer;
   begin
      for I in 1 .. Total_Items loop
         Buffer.Retirar (Item);
         Put_Line ("   Consume <-" & Integer'Image (Item));
         delay 0.05;   --  el consumidor es mas lento: el buffer se llena
      end loop;
   end Consumidor;

begin
   null;   --  el procedimiento espera a que ambas tareas terminen
end Productor_Consumidor;

Puntos a observar en este programa:

No aparece ningún cerrojo explícito. El objeto protegido garantiza que a lo sumo una tarea ejecute una de sus operaciones a la vez.
when Cantidad < Capacidad y when Cantidad > 0 son barreras: se evalúan al llegar y cada vez que el estado del objeto cambia. Si son falsas, la tarea que llama se encola sin ejecutar espera activa.
El productor es más rápido que el consumidor, así que el buffer se llena y el productor se bloquea. Ese bloqueo es la contrapresión que evita crecimiento ilimitado de memoria.
Ada.Text_IO no está garantizado como reentrante por el estándar; en GNAT lo es. Para código portable, la salida se centraliza en una única tarea.

En Elixir el mismo problema se resuelve sin memoria compartida: el buffer es un proceso y las dos condiciones se expresan con el par {:noreply, estado} más GenServer.reply/2. Cuando un consumidor pide un dato y el buffer está vacío, el servidor no responde: guarda la identidad del solicitante en una cola interna y devuelve {:noreply, estado}. Como GenServer.call deja al llamante bloqueado esperando la respuesta, el efecto es idéntico al de una barrera de Ada, construido sólo con mensajes. Cuando llega un depósito, el servidor saca al primer consumidor de la cola y le responde con GenServer.reply/2. El caso simétrico —productor bloqueado con el buffer lleno— usa exactamente el mismo mecanismo. Este patrón aparece completo en el código de los filósofos comensales, más adelante en este mismo capítulo.

Lectores-escritores

Un dato compartido admite muchos lectores simultáneos, porque leer no modifica nada, pero un escritor necesita acceso exclusivo. Formalmente:

Pueden coexistir N lectores.
Un escritor excluye a todos los lectores y a los demás escritores.

La dificultad está en la política, no en el mecanismo. Hay tres variantes clásicas:

Variante	Regla	Consecuencia
Prioridad a lectores	Un lector entra si no hay escritor escribiendo, aunque haya escritores esperando	Con lectores frecuentes, los escritores nunca entran: inanición de escritores
Prioridad a escritores	Un lector espera si hay algún escritor esperando	Con escritores frecuentes, los lectores se postergan: inanición de lectores
Sin inanición	Se respeta el orden de llegada entre grupos	Menor concurrencia de lectura, pero espera limitada para todos

La segunda variante se implementa en Ada de manera muy directa, porque el lenguaje permite consultar el número de tareas encoladas en una entrada mediante el atributo 'Count.

--  lectores_escritores.adb
--  compilar y ejecutar:  gnatmake lectores_escritores.adb && ./lectores_escritores
with Ada.Text_IO; use Ada.Text_IO;

procedure Lectores_Escritores is

   --------------------------------------------------------------------
   --  Control de acceso con prioridad a escritores.
   --  Iniciar_Lectura sólo abre si no hay escritor activo Y no hay
   --  escritores encolados: eso impide la inanición de escritores.
   --------------------------------------------------------------------
   protected Control is
      entry     Iniciar_Lectura;
      procedure Terminar_Lectura;
      entry     Iniciar_Escritura;
      procedure Terminar_Escritura;
      function  Lectores_Activos return Natural;
   private
      Lectores    : Natural := 0;
      Escribiendo : Boolean := False;
   end Control;

   protected body Control is

      entry Iniciar_Lectura
        when not Escribiendo and Iniciar_Escritura'Count = 0 is
      begin
         Lectores := Lectores + 1;
      end Iniciar_Lectura;

      procedure Terminar_Lectura is
      begin
         Lectores := Lectores - 1;
      end Terminar_Lectura;

      entry Iniciar_Escritura when not Escribiendo and Lectores = 0 is
      begin
         Escribiendo := True;
      end Iniciar_Escritura;

      procedure Terminar_Escritura is
      begin
         Escribiendo := False;
      end Terminar_Escritura;

      function Lectores_Activos return Natural is
      begin
         return Lectores;
      end Lectores_Activos;

   end Control;

   Dato : Integer := 0;   --  recurso compartido protegido por Control

   task type Lector (Id : Positive; Vueltas : Positive);
   task type Escritor (Id : Positive; Vueltas : Positive);

   task body Lector is
      Copia : Integer;
   begin
      for K in 1 .. Vueltas loop
         Control.Iniciar_Lectura;
         Copia := Dato;
         Put_Line ("Lector" & Positive'Image (Id) & " lee" & Integer'Image (Copia)
                   & " (lectores activos:"
                   & Natural'Image (Control.Lectores_Activos) & " )");
         delay 0.02;
         Control.Terminar_Lectura;
         delay 0.03;
      end loop;
   end Lector;

   task body Escritor is
   begin
      for K in 1 .. Vueltas loop
         Control.Iniciar_Escritura;
         Dato := Dato + 1;
         Put_Line ("ESCRITOR" & Positive'Image (Id) & " escribe" & Integer'Image (Dato));
         delay 0.05;
         Control.Terminar_Escritura;
         delay 0.10;
      end loop;
   end Escritor;

begin
   declare
      L1 : Lector   (Id => 1, Vueltas => 6);
      L2 : Lector   (Id => 2, Vueltas => 6);
      L3 : Lector   (Id => 3, Vueltas => 6);
      E1 : Escritor (Id => 1, Vueltas => 3);
      E2 : Escritor (Id => 2, Vueltas => 3);
   begin
      null;   --  el bloque espera a que todas las tareas terminen
   end;
   Put_Line ("Valor final del dato:" & Integer'Image (Dato));
end Lectores_Escritores;

La línea decisiva es la barrera de Iniciar_Lectura:

when not Escribiendo and Iniciar_Escritura'Count = 0

Iniciar_Escritura'Count es el número de tareas encoladas esperando en esa entrada. Al incluirlo en la barrera de lectura, un lector nuevo no entra si hay algún escritor esperando, aunque en ese momento haya otros lectores dentro. Los lectores ya admitidos terminan, el contador llega a cero, la barrera del escritor se abre y el escritor pasa. La inanición de escritores queda descartada por construcción.

Sin ese término, la barrera sería sólo when not Escribiendo, y con tres lectores que se solapan el contador Lectores podría no llegar nunca a cero.

Filósofos comensales

Cinco filósofos alrededor de una mesa. Entre cada par hay un tenedor, cinco en total. Un filósofo alterna entre pensar y comer, y para comer necesita los dos tenedores adyacentes. El problema fue planteado por Dijkstra en 1965 como ejercicio de asignación de múltiples recursos.

flowchart TB
    subgraph MESA["Mesa: cada filósofo necesita sus dos tenedores adyacentes"]
        F0(["F0"]) --- T0["T0"] --- F1(["F1"]) --- T1["T1"] --- F2(["F2"])
        F2 --- T2["T2"] --- F3(["F3"]) --- T3["T3"] --- F4(["F4"]) --- T4["T4"] --- F0
    end

    subgraph CICLO["Espera circular: todos toman el izquierdo primero"]
        C0(["F0 tiene T0<br/>espera T4"]) --> C4(["F4 tiene T4<br/>espera T3"])
        C4 --> C3(["F3 tiene T3<br/>espera T2"])
        C3 --> C2(["F2 tiene T2<br/>espera T1"])
        C2 --> C1(["F1 tiene T1<br/>espera T0"])
        C1 --> C0
    end

    style MESA fill:#1e3a5f,color:#fff
    style CICLO fill:#5f1e1e,color:#fff

La solución ingenua —cada filósofo toma primero el tenedor de su izquierda y luego el de su derecha— cumple las cuatro condiciones de Coffman y produce interbloqueo si los cinco toman su tenedor izquierdo antes de que ninguno tome el derecho. La probabilidad no es despreciable: es el estado al que converge el sistema si todos los filósofos son igual de rápidos.

Hay varias correcciones conocidas, y cada una ataca una condición distinta de Coffman:

Solución	Condición de Coffman que rompe	Cómo
Orden total de tenedores	Espera circular	Cada filósofo toma primero el tenedor de menor identificador, sin importar si es el izquierdo o el derecho
Un filósofo zurdo	Espera circular	Cuatro filósofos toman izquierdo-derecho y uno toma derecho-izquierdo, rompiendo la simetría del ciclo
Portero o árbitro	Retención y espera	Un componente central admite a lo sumo cuatro filósofos a la mesa; con cuatro comensales y cinco tenedores siempre hay uno que puede comer
Tomar ambos o ninguno	Retención y espera	La adquisición de los dos tenedores se hace en una sola operación atómica; si no están ambos, no se toma ninguno
Revocación con reintento	No apropiación	Si el segundo tenedor no está disponible, se suelta el primero y se reintenta más tarde

La implementación siguiente usa el orden total, que es la que menos reduce la concurrencia: hasta dos filósofos comen a la vez, igual que en la versión ingenua, sin riesgo de interbloqueo.

# filosofos.exs — ejecutar: elixir filosofos.exs
# Cada tenedor es un proceso. `tomar/1` bloquea al llamante hasta que el tenedor
# esté libre: el servidor guarda al solicitante en una cola y le responde recién
# cuando el tenedor se suelta. Es una barrera construida sólo con mensajes.
defmodule Tenedor do
  use GenServer

  def start_link, do: GenServer.start_link(__MODULE__, nil)
  def tomar(pid), do: GenServer.call(pid, :tomar, :infinity)
  def soltar(pid), do: GenServer.cast(pid, :soltar)

  @impl true
  def init(_), do: {:ok, %{libre: true, cola: :queue.new()}}

  @impl true
  def handle_call(:tomar, _desde, %{libre: true} = e), do: {:reply, :ok, %{e | libre: false}}
  def handle_call(:tomar, desde, e), do: {:noreply, %{e | cola: :queue.in(desde, e.cola)}}

  @impl true
  def handle_cast(:soltar, e) do
    case :queue.out(e.cola) do
      # el tenedor pasa directo al siguiente en la cola: no se libera
      {{:value, siguiente}, resto} ->
        GenServer.reply(siguiente, :ok)
        {:noreply, %{e | cola: resto}}

      {:empty, _} ->
        {:noreply, %{e | libre: true}}
    end
  end
end

# Rompe la espera circular tomando siempre primero el tenedor de menor
# identificador. Los pid tienen un orden total en Erlang, así que `Enum.sort`
# basta: si todos respetan ese orden, no puede formarse un ciclo.
defmodule Filosofo do
  def iniciar(nombre, izq, der, rondas), do: spawn(fn -> ciclo(nombre, izq, der, rondas) end)

  defp ciclo(nombre, _izq, _der, 0), do: IO.puts("#{nombre} se retira de la mesa")

  defp ciclo(nombre, izq, der, rondas) do
    IO.puts("#{nombre} piensa")
    Process.sleep(Enum.random(20..80))

    [primero, segundo] = Enum.sort([izq, der])
    Tenedor.tomar(primero)
    Tenedor.tomar(segundo)

    IO.puts("#{nombre} COME (rondas restantes: #{rondas})")
    Process.sleep(Enum.random(20..80))

    Tenedor.soltar(segundo)
    Tenedor.soltar(primero)
    ciclo(nombre, izq, der, rondas - 1)
  end
end

# --- Programa principal ---
cantidad = 5
tenedores = Enum.map(1..cantidad, fn _ -> elem(Tenedor.start_link(), 1) end)
nombres = ["Aristoteles", "Platon", "Socrates", "Kant", "Hume"]

referencias =
  nombres
  |> Enum.with_index()
  |> Enum.map(fn {nombre, i} ->
    izq = Enum.at(tenedores, i)
    der = Enum.at(tenedores, rem(i + 1, cantidad))
    Process.monitor(Filosofo.iniciar(nombre, izq, der, 4))
  end)

# Espera a que los cinco filósofos terminen sus rondas.
Enum.each(referencias, fn ref ->
  receive do
    {:DOWN, ^ref, :process, _pid, _razon} -> :ok
  end
end)

IO.puts("La cena terminó sin interbloqueo")

Si se reemplaza la línea del orden total por la versión ingenua:

# Versión que SÍ produce interbloqueo: todos toman su izquierdo primero.
Tenedor.tomar(izq)
Process.sleep(20)      # ensancha la ventana para que el ciclo se forme
Tenedor.tomar(der)

el programa se detiene sin terminar. Ninguno de los cinco procesos consume procesador: los cinco están bloqueados en GenServer.call con :infinity, cada uno esperando un tenedor que sostiene su vecino. Este contraste es el mejor experimento del capítulo, porque muestra que el interbloqueo no produce carga ni errores: produce silencio.

Modelos de sincronización comparados

Los ejemplos anteriores usaron dos modelos distintos, y conviene ponerlos lado a lado.

Aspecto	Memoria compartida (C con hilos, Ada con objetos protegidos)	Paso de mensajes (Elixir con procesos)
Unidad de estado	Variables accesibles por todos los flujos	Estado privado de cada proceso
Comunicación	Escribir y leer la misma dirección	Enviar y recibir mensajes
Mecanismo de exclusión	Cerrojos, mutex, semáforos, objetos protegidos	Serialización natural: un proceso atiende un mensaje a la vez
Origen típico del error	Dos flujos tocando la misma dirección sin protección	Protocolo dividido en varios mensajes que deberían ser uno
Costo de una operación	Muy bajo si no hay contención	Mayor: copia del mensaje y cambio de contexto
Escala natural	Un nodo, memoria coherente	Varios nodos, red
¿Puede haber interbloqueo?	Sí	Sí: dos procesos que se llaman mutuamente y esperan respuesta
¿Puede haber condición de carrera?	Sí, sobre memoria	Sí, sobre el orden de los mensajes

La conclusión que interesa es que el paso de mensajes elimina una clase de errores —las actualizaciones perdidas sobre memoria— pero no elimina la sincronización. El error de verificar-y-actuar reaparece intacto cuando el protocolo se parte en dos mensajes, como mostró el ejemplo bancario en Elixir.

Errores comunes

Error	Causa	Cómo se manifiesta	Solución
Suponer que una línea de código es atómica	`x++` o `x = x + 1` son leer-modificar-escribir	Actualizaciones perdidas, contadores por debajo del valor real	Proteger con exclusión mutua o usar tipos atómicos del lenguaje
Reducir la ventana en lugar de cerrarla	Se agrega un `sleep` o se acorta el código entre verificar y actuar	El error baja de frecuencia y reaparece bajo carga	Convertir verificar-y-actuar en una operación indivisible
”No apareció en las pruebas, entonces está bien”	Las pruebas ejercitan unos pocos intercalados	Fallo en producción, no reproducible en desarrollo	Argumentar la corrección sobre los invariantes; usar detectores dinámicos de carreras
Depurar con `printf`	La E/S cambia los tiempos y suele estar sincronizada internamente	El error desaparece al instrumentar: Heisenbug	Registrar en buffers en memoria y volcar al final, o usar herramientas de trazado
Adquirir cerrojos en órdenes distintos	Cada función pide los recursos en el orden que le resulta natural	Interbloqueo intermitente al aumentar la concurrencia	Definir un orden total de adquisición y documentarlo
Retornar de la sección crítica sin liberar	Un `return` temprano, una excepción o un `break` salta el protocolo de salida	Interbloqueo permanente en la siguiente entrada	Un solo punto de salida, o construcciones que liberen automáticamente al salir del ámbito
Espera activa donde corresponde bloqueo	Bucle que consulta una condición sin ceder el procesador	Un núcleo al 100 % sin trabajo útil; el hilo que debe liberar no alcanza a correr	Usar primitivas de bloqueo del sistema operativo o barreras del lenguaje
Peterson con variables ordinarias	El compilador y el procesador reordenan accesos a memoria	El algoritmo falla pese a ser correcto sobre el papel	Usar tipos atómicos con consistencia secuencial, o primitivas de la biblioteca
Un cerrojo por variable en lugar de por invariante	Se protege cada campo por separado	El invariante que relaciona dos campos se observa roto entre ambos cerrojos	Proteger con un solo cerrojo todo el conjunto de datos que forma un invariante
Buffer sin límite entre productor y consumidor	Se omite la condición de “lleno” para simplificar	La memoria crece hasta agotarse si el productor es más rápido	Acotar la capacidad y bloquear al productor: la contrapresión es parte del diseño
Barrera de lectores sin considerar escritores encolados	Sólo se verifica que no haya escritor activo	Los escritores nunca entran mientras haya lectura continua	Incluir en la barrera de lectura el conteo de escritores en espera
Confundir interbloqueo con lentitud	Ambos se ven como “el programa no responde”	Se reinicia sin diagnosticar y el problema vuelve	Revisar el estado de los hilos: bloqueados indica interbloqueo, ejecutables indica bloqueo vivo o carga

Ejercicios propuestos

Los primeros ejercicios se resuelven observando y midiendo; los últimos requieren escribir y argumentar.

Ejercicio 1 — Medir la pérdida. Compila contador_roto.c con -O0 y ejecútalo veinte veces guardando cada resultado. Calcula el mínimo, el máximo y la media de incrementos perdidos. Repite con VUELTAS igual a 1000 y explica por qué el porcentaje de pérdida cambia.

Ejercicio 2 — El efecto del optimizador. Compila el mismo programa con -O2 y compara los resultados con los de -O0. Explica qué transformación del compilador puede alterar el comportamiento y por qué eso no significa que el programa sea correcto.

Ejercicio 3 — Cerrar la ventana. Modifica banco_roto.c para que el invariante fondos >= 0 se mantenga en todos los intercalados posibles, usando pthread_mutex_t. Argumenta en un párrafo por qué tu solución cubre todos los intercalados y no sólo los que observaste.

Ejercicio 4 — Refutar el intento 2. Escribe la secuencia exacta de operaciones de los dos hilos que hace que ambos entren a la sección crítica en el intento 2 de exclusión mutua. Numera cada paso indicando qué hilo lo ejecuta y qué valor lee o escribe.

Ejercicio 5 — Progreso en el intento 1. Construye un escenario concreto con el turno estricto en el que la sección crítica está libre y un hilo que la necesita no puede entrar. Identifica cuál de los cuatro requisitos se incumple y cita la cláusula precisa.

Ejercicio 6 — Peterson sin átomos. Reescribe peterson.c usando bool e int corrientes en lugar de los tipos atómicos, compila con -O2 y ejecútalo cincuenta veces. Anota cuántas veces el resultado difiere del esperado. Explica el rol del orden de memoria en lo que observaste.

Ejercicio 7 — Panadería en código. Implementa el algoritmo de la panadería en C para cuatro hilos que incrementen un contador compartido un millón de veces cada uno. Verifica el total y mide el tiempo de ejecución comparándolo con la versión que usa pthread_mutex_t.

Ejercicio 8 — Coffman aplicado. Toma interbloqueo.c y produce cuatro versiones corregidas, cada una rompiendo una condición distinta de Coffman. Para cada versión, indica qué se pierde respecto de la original en utilización, complejidad o latencia.

Ejercicio 9 — Detectar el ciclo. Dibuja en Mermaid el grafo de asignación de recursos de un escenario con tres hilos y tres mutex donde exista interbloqueo. Luego dibuja el mismo escenario con un orden total de adquisición y muestra por qué el ciclo no puede formarse.

Ejercicio 10 — Inanición medible. Modifica el programa de lectores-escritores en Ada quitando el término Iniciar_Escritura'Count = 0 de la barrera de lectura, sube a ocho lectores con delay corto y cuenta cuántas escrituras se completan en diez segundos. Compara con la versión original.

Ejercicio 11 — Contrapresión. Ejecuta productor_consumidor.adb con Capacidad => 1 y con Capacidad => 100. Mide el tiempo total en cada caso y explica qué cambia en el comportamiento del productor.

Ejercicio 12 — Provocar el interbloqueo. Modifica filosofos.exs para que cada filósofo tome siempre su tenedor izquierdo primero, con una pausa entre ambas tomas. Confirma que el programa se detiene. Usando :observer.start() o Process.info/2, verifica que los cinco procesos están bloqueados y no consumiendo procesador.

Ejercicio 13 — Portero. Implementa la variante del árbitro para los filósofos: un proceso que admite a lo sumo cuatro comensales simultáneos. Argumenta por qué cuatro es suficiente para descartar el interbloqueo y por qué tres reduciría la concurrencia sin beneficio adicional.

Ejercicio 14 — Traducir el modelo. Toma la solución de lectores-escritores en Ada y escríbela en Elixir sin usar memoria compartida ni ETS: un proceso guarda el dato y otro controla el acceso. Indica qué parte del problema desaparece y qué parte se traslada al protocolo de mensajes.

Ejercicio 15 — Carreras sin memoria compartida. Escribe un programa en Elixir donde dos procesos produzcan un resultado incorrecto por partir en dos mensajes una operación que debería ser una sola. Luego corrígelo y describe en una frase la regla general que aplicaste.

Lo que viene

Este capítulo dejó identificado el problema completo. La concurrencia introduce no determinismo, el no determinismo expone las operaciones de leer-modificar-escribir, y de ahí salen las condiciones de carrera. Delimitar el código afectado da la sección crítica, y protegerla exige exclusión mutua con cuatro requisitos: exclusión, progreso, espera limitada e independencia de la velocidad relativa. Vimos que se puede lograr sólo con memoria compartida —Dekker, Peterson, la panadería de Lamport— y por qué el hardware terminó ofreciendo instrucciones atómicas. Nombramos las tres formas de detención: interbloqueo, con sus cuatro condiciones de Coffman y sus cuatro puntos de ataque; bloqueo vivo, donde hay actividad sin avance; e inanición, donde la política de asignación posterga indefinidamente a alguien. Y resolvimos los tres problemas clásicos con objetos protegidos de Ada y procesos de Elixir.

Queda pendiente un cabo suelto importante: todas las soluciones por software de este capítulo hacen espera activa. Un hilo que no puede entrar consume su cuanto de procesador consultando una variable, y en el peor caso impide correr precisamente al hilo que liberaría el recurso. Eso no se arregla con un algoritmo más ingenioso: hace falta que el sistema operativo participe, sacando al hilo de la cola de listos mientras espera y devolviéndolo cuando la condición se cumple.

Esa primitiva existe desde 1965 y es la abstracción central de la sincronización: el semáforo. En el capítulo 8 se estudia en detalle: las operaciones wait y signal, la diferencia entre semáforo binario y contador, cómo se implementa por dentro con las instrucciones atómicas que vimos aquí, y cómo se reescriben con semáforos los tres problemas clásicos que acabamos de resolver. También veremos por qué el semáforo, siendo suficiente para todo, es difícil de usar correctamente, y qué construcciones de más alto nivel aparecieron después.

El temario completo del curso está en el índice general.