Sin bloqueos: compare-and-swap, ABA y por qué casi nunca

Programar sin bloqueos tiene una reputación que no se corresponde con lo que es. No es la técnica de los expertos ni el escalón final de la concurrencia: es una familia de estructuras de datos con una garantía de progreso concreta, un coste de diseño altísimo y un problema sin solución elegante en un lenguaje sin recolector de basura. Esta lección la enseña entera para que sepas exactamente por qué casi nunca deberías usarla.

Comparar e intercambiar: la primitiva universal

Toda la programación sin bloqueos descansa sobre una única operación del hardware: leer una posición, comprobar que sigue valiendo lo que esperabas y, solo entonces, escribir el valor nuevo, todo indivisiblemente.

bool atomic_compare_exchange_strong(A *obj, C *esperado, C deseado);

La firma tiene un detalle que despista a todo el mundo la primera vez: esperado es un puntero de entrada y salida. Si la comparación falla, la función sobrescribe esperado con el valor que realmente había. Eso no es un capricho, es lo que hace que el bucle de reintento no necesite releer:

void sumar_maximo(atomic_int *m, int candidato) {
    int actual = atomic_load_explicit(m, memory_order_relaxed);
    while (candidato > actual &&
           !atomic_compare_exchange_weak_explicit(
               m, &actual, candidato,
               memory_order_release, memory_order_relaxed))
        ;                       /* si falla, actual ya trae el valor fresco */
}

La versión weak puede fallar espuriamente aunque el valor coincida, porque en arquitecturas con carga enlazada y almacén condicional —ARM, POWER, RISC-V— una interrupción o un fallo de caché rompe el enlace. A cambio genera código más corto. La regla: dentro de un bucle usa siempre weak; solo fuera de un bucle tiene sentido strong.

Las variantes explícitas llevan dos órdenes de memoria, uno para el éxito y otro para el fallo. El de fallo no puede ser más fuerte que el de éxito ni puede ser release ni acq_rel, porque en el fallo no hay escritura que publicar. Que el reintento sea relaxed es lo habitual y lo correcto: solo la iteración que triunfa necesita publicar algo.

Que esta operación sea universal es un resultado formal, no una metáfora: Herlihy demostró en 1991 que el comparar e intercambiar tiene número de consenso infinito, es decir, que con él se puede construir una versión sin esperas de cualquier objeto concurrente para cualquier número de hilos. Con solo lectura y escritura atómicas, no. Por eso está en todos los procesadores.

Una pila sin bloqueos

La pila de Treiber es el ejemplo canónico porque cabe en una pantalla y contiene todos los problemas del campo.

typedef struct Nodo Nodo;
struct Nodo { _Atomic(Nodo *) siguiente; int valor; };

static _Atomic(Nodo *) cabeza = nullptr;

void apilar(Nodo *n) {
    Nodo *vieja = atomic_load_explicit(&cabeza, memory_order_relaxed);
    do {
        atomic_store_explicit(&n->siguiente, vieja, memory_order_relaxed);
    } while (!atomic_compare_exchange_weak_explicit(
                 &cabeza, &vieja, n,
                 memory_order_release, memory_order_relaxed));
}

Nodo *desapilar(void) {
    Nodo *arriba = atomic_load_explicit(&cabeza, memory_order_acquire);
    while (arriba &&
           !atomic_compare_exchange_weak_explicit(
               &cabeza, &arriba,
               atomic_load_explicit(&arriba->siguiente, memory_order_relaxed),
               memory_order_acquire, memory_order_acquire))
        ;
    return arriba;
}

Los órdenes están elegidos, no puestos por defecto. El release de apilar publica el nodo completamente escrito antes de que otro hilo pueda alcanzarlo; el acquire de desapilar garantiza que quien lo saca ve ese contenido. Cambiar cualquiera de los dos por relaxed compila, pasa los tests y falla en producción sobre AArch64.

Y ahora la parte incómoda. Ese desapilar es incorrecto, aunque parezca perfecto y funcione en tus pruebas. Lee arriba y luego lee arriba->siguiente, y entre ambas lecturas otro hilo puede haber sacado ese mismo nodo y haberlo liberado. Estás dereferenciando memoria liberada. Ese es el verdadero problema del campo y no tiene solución dentro de la propia estructura.

ABA y el muro de la recuperación de memoria

El fallo tiene nombre propio y es más sutil que un simple uso tras liberar.

flowchart TD
A[Hilo 1 lee cabeza igual a A y siguiente igual a B] --> B[Hilo 1 se detiene]
B --> C[Hilo 2 desapila A y desapila B]
C --> D[Hilo 2 libera B y reutiliza A]
D --> E[Hilo 2 vuelve a apilar A]
E --> F[Hilo 1 despierta y su CAS triunfa]
F --> G[La cabeza pasa a apuntar a B ya liberado]
style G fill:#f38ba8,color:#11111b

El comparar e intercambiar respondió que sí porque la cabeza volvía a valer A, pero el mundo había cambiado entero por debajo. La operación compara valores, no historias; y como los asignadores reutilizan direcciones con entusiasmo, un puntero es un valor especialmente propenso a repetirse.

La defensa clásica es adjuntar un contador al puntero y comparar los dos juntos, de modo que la reaparición de la misma dirección venga con una etiqueta distinta:

typedef struct { Nodo *ptr; uintptr_t etiqueta; } Etiquetado;
static _Atomic(Etiquetado) cabeza;      /* necesita CAS de doble ancho */

Esto exige que el hardware ofrezca un comparar e intercambiar de dieciséis bytes —cmpxchg16b en x86-64, que hay que habilitar con -mcx16— y aun así solo pospone el problema: el contador da la vuelta, y sobre todo no arregla la dereferencia de memoria liberada, solo el falso positivo del CAS.

El problema real, del que ABA es un síntoma, es este: no puedes liberar un nodo mientras otro hilo pueda estar leyéndolo, y no tienes forma barata de saber cuándo deja de poder. Las tres respuestas serias del estado del arte:

Ninguna de las cuatro cabe en una pantalla, todas añaden estado global, y las tres primeras son más difíciles de escribir correctamente que la estructura de datos que pretendían proteger.

Por qué casi nunca deberías

Conviene ser exacto con la terminología, porque la palabra promete algo distinto de lo que entrega. Sin bloqueos no significa sin esperas ni significa rápido: es una garantía de progreso. Bloqueante significa que un hilo detenido puede detener a los demás. Sin bloqueos significa que, entre todos, alguno progresa siempre, aunque uno concreto reintente eternamente. Sin esperas significa que cada hilo termina en un número acotado de pasos, y es tan caro de conseguir que casi nadie lo implementa.

Esa garantía vale oro exactamente en tres sitios: cuando el hilo puede morir o ser suspendido en mitad de la operación, cuando hay una restricción de tiempo real duro, y cuando la operación ocurre en un contexto donde dormir es ilegal, como un manejador de señal o una rutina de interrupción. Fuera de esos tres casos, lo que buscas es rendimiento, y ahí la evidencia es mucho menos favorable de lo que sugiere la reputación.

Bajo contención, el bucle de reintento es trabajo desperdiciado a pleno consumo de energía, y la línea de caché que contiene la cabeza rebota entre núcleos en cada intento: un tráfico de coherencia que escala peor que la espera. Un mutex bien implementado gira brevemente y después aparca el hilo con futex, cediendo el núcleo a alguien que sí avanza. La comparación honesta rara vez la gana la versión sin bloqueos, y cuando la gana suele ser porque el diseño reparte los datos, no por la ausencia de candado.

/* La respuesta correcta al 95 % de los casos, por este orden: */
/* 1. No compartir: particionar los datos por hilo.            */
/* 2. Comunicar por mensajes: una cola con mutex y condicion.  */
/* 3. Un contador atomico suelto: relaxed y listo.             */
/* 4. Un mutex sobre la estructura entera.                     */
/* 5. Solo entonces, y con TSan, una estructura sin bloqueos.  */