Estructuras sin bloqueos

1. Qué es una estructura sin bloqueos

Una estructura sin bloqueos (lock-free data structure) es una estructura de datos que se puede acceder concurrentemente por múltiples hilos sin usar mutex ni otros mecanismos de bloqueo. Usa operaciones atómicas (especialmente CAS) para garantizar la consistencia.

Las estructuras lock-free son no bloqueantes: un hilo que accede a la estructura nunca se bloquea. Si otro hilo está modificando la estructura, el hilo reintenta la operación hasta que tenga éxito.

Las propiedades de las estructuras lock-free son:

• Lock-free: al menos un hilo progresa en un número finito de pasos.
• Wait-free: todos los hilos progresan en un número finito de pasos (más fuerte que lock-free).
• Obstruction-free: un hilo progresa si ejecuta solo (más débil que lock-free).

2. Ventajas y desventajas

3. Contador lock-free

El contador lock-free más simple usa atomic_fetch_add:

#include <stdatomic.h>

atomic_int counter = 0;

void incrementar(void) {
    atomic_fetch_add(&counter, 1);  /* atómico, sin lock */
}

int leer(void) {
    return atomic_load(&counter);
}

Este contador es lock-free porque usa una operación atómica. No hay mutex, no hay bloqueo, no hay deadlock.

4. Pila lock-free

Una pila lock-free se implementa con CAS. El tope de la pila se actualiza atómicamente:

typedef struct nodo {
    int valor;
    struct nodo *siguiente;
} nodo_t;

typedef struct {
    _Atomic(nodo_t *) tope;
} pila_t;

void pila_push(pila_t *p, int valor) {
    nodo_t *nuevo = malloc(sizeof(nodo_t));
    nuevo->valor = valor;
    nodo_t *viejo;
    do {
        viejo = atomic_load(&p->tope);
        nuevo->siguiente = viejo;
    } while (!atomic_compare_exchange_weak(&p->tope, &viejo, nuevo));
}

int pila_pop(pila_t *p) {
    nodo_t *viejo;
    nodo_t *nuevo;
    do {
        viejo = atomic_load(&p->tope);
        if (viejo == NULL) return -1;  /* pila vacía */
        nuevo = viejo->siguiente;
    } while (!atomic_compare_exchange_weak(&p->tope, &viejo, nuevo));
    int valor = viejo->valor;
    /* Liberar memoria (con cuidado: problema ABA). */
    return valor;
}

La pila usa CAS para actualizar el tope de forma atómica. Si otro hilo modifica el tope entre la lectura y el CAS, el CAS falla y se reintenta.

5. El problema ABA

El problema ABA es el principal problema de las estructuras lock-free. Ocurre cuando un valor cambia de A a B y vuelve a A, engañando a un CAS:

1. La pila tiene [A, B, C]. El tope es A. inicial
2. Hilo 1 lee el tope (A) y el siguiente (B). Va a hacer CAS para cambiar el tope de A a B. leer
3. Hilo 2 saca A y B de la pila. La pila queda [C]. sacar
4. Hilo 2 mete A de nuevo. La pila queda [A, C]. meter
5. Hilo 1 hace CAS: compara tope con A, es igual, cambia a B. Pero B ya no está en la pila. La pila queda corrupta. corrupción

El problema ABA es sutil y peligroso: el CAS tiene éxito porque el valor es el esperado, pero el estado intermedio se perdió.

6. Soluciones al ABA

La solución más común en C es el contador de versión: se empaqueta el puntero y un contador en una palabra de 64 bits (usando los bits altos para el contador) y se usa CAS sobre la palabra completa.

7. Cuándo no vale la pena

Las estructuras lock-free no siempre son mejores que los mutexes:

• Baja contención: si la contención es baja, un mutex es más rápido (fast path sin entrar al núcleo).
• Alta contención: los reintentos de CAS pueden ser costosos.
• Complejidad: el código lock-free es difícil de escribir y verificar.
• ABA: el problema ABA añade complejidad adicional.

La regla práctica es: usar mutex por defecto, y lock-free solo cuando el rendimiento lo justifique y se pueda verificar correctamente.

8. Estructuras lock-free en Linux

Linux usa estructuras lock-free extensivamente:

• Listas lock-free: el núcleo usa listas enlazadas lock-free para la cola de ejecución.
• Contadores atómicos: atomic_t se usa para contadores de referencia.
• RCU: Read-Copy-Update es la técnica lock-free más usada en Linux.
• Hazard pointers: se usan en algunos subsistemas.

RCU es especialmente importante: permite que los lectores no se bloqueen y los escritores creen una copia. Es la técnica que hace que Linux sea escalable en sistemas con muchos núcleos.

9. Simulador interactivo

Este simulador muestra cómo funciona una pila lock-free con CAS:

10. Resumen

• Las estructuras lock-free usan operaciones atómicas (CAS) en lugar de mutex.
• Garantizan que al menos un hilo progresa (lock-free).
• El contador lock-free usa atomic_fetch_add.
• La pila lock-free usa CAS para actualizar el tope.
• El problema ABA ocurre cuando un valor cambia y vuelve al original.
• Las soluciones al ABA incluyen contador de versión, hazard pointers y RCU.
• Lock-free no siempre es más rápido que un mutex.
• Linux usa estructuras lock-free extensivamente (RCU, contadores atómicos).

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa un contador lock-free con atomic_fetch_add.
2. Implementa una pila lock-free con CAS.
3. Diseña un escenario donde ocurra el problema ABA.
4. Implementa la solución con contador de versión.
5. Compara el rendimiento de una pila lock-free con una protegida por mutex.
6. Investiga cómo se implementa RCU en el núcleo de Linux.