¿Qué es la programación lock-free y CAS? Explica el problema ABA y cuándo usarlo.

Question

IT Interview Practice · Accepted Answer

**La programación lock-free coordina hilos sin mutexes, usando bucles atómicos de compare-and-swap (CAS) para que al menos un hilo siempre avance aunque otros se estanquen.** Ningún hilo puede ser bloqueado por otro que retenga un lock.

## CAS

**Compare-and-swap** fija atómicamente una posición a un nuevo valor solo si todavía contiene el valor antiguo esperado; en caso contrario falla y reintentas. Es la primitiva detrás de pilas, colas y contadores lock-free.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false
```

```java
// Lock-free increment via CAS retry loop
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // retry if someone else won
```

## El problema ABA

CAS solo comprueba que el valor sigue siendo el esperado — no que nunca cambió. Si pasó de A → B → A entre tu lectura y el CAS, el CAS tiene éxito pero el mundo se movió bajo tus pies (p. ej. un nodo liberado y reutilizado).

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (but list changed!)
Thread 2:      pop A, push B, push A again
```

**Solución**: empareja el puntero con un contador de versión (`AtomicStampedReference`, punteros etiquetados) para que A-con-etiqueta-1 ≠ A-con-etiqueta-2, o usa hazard pointers / recuperación por épocas para la seguridad de memoria.

## Cuándo usarlo

- **Úsalo** para estado compartido caliente y de grano fino (contadores, colas de un solo productor) donde domina la contención de locks, o donde un hilo nunca debe bloquearse (tiempo real, manejadores de señales).
- **Evítalo** por defecto: es difícil de acertar, fácil de introducir bugs de ABA y de ordenamiento de memoria, y a menudo no es más rápido que un buen mutex bajo baja contención.

## Por qué es importante

Las estructuras lock-free dan garantías de progreso y evitan el deadlock y la inversión de prioridades, pero el listón de correctitud es alto. Conocer CAS, ABA y el problema de recuperación indica que puedes razonar al nivel del modelo de memoria — y, lo crucial, saber cuándo *no* recurrir a ello.

CAS

El problema ABA

Cuándo usarlo

Por qué es importante

Preguntas relacionadas