Cos'è la programmazione lock-free e il CAS? Spiega il problema ABA e quando usarlo.

Question

IT Interview Practice · Accepted Answer

**La programmazione lock-free coordina i thread senza mutex, usando loop atomici di compare-and-swap (CAS) così che almeno un thread faccia sempre progressi anche se gli altri si bloccano.** Nessun thread può essere bloccato da un altro che detiene un lock.

## CAS

**Compare-and-swap** imposta atomicamente una locazione a un nuovo valore solo se contiene ancora il vecchio valore atteso; altrimenti fallisce e devi riprovare. È la primitiva alla base di stack, code e contatori lock-free.

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

```java
// Incremento lock-free tramite loop di retry CAS
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // riprova se qualcun altro ha vinto
```

## Il problema ABA

Il CAS controlla solo che il valore sia ancora quello atteso — non che non sia mai cambiato. Se è passato da A → B → A tra la tua lettura e il CAS, il CAS riesce ma il mondo si è mosso sotto di te (es. un nodo liberato e riutilizzato).

```text
Thread 1: legge A ............... CAS(A→X) riesce ✗ (ma la lista è cambiata!)
Thread 2:      pop A, push B, push A di nuovo
```

**Soluzione**: abbina il puntatore a un version counter (`AtomicStampedReference`, tagged pointer) così che A-con-tag-1 ≠ A-con-tag-2, oppure usa hazard pointer / epoch reclamation per la sicurezza della memoria.

## Quando usarlo

- **Usalo** per stato condiviso caldo e a grana fine (contatori, code single-producer) dove la contesa sui lock domina, o dove un thread non deve mai bloccarsi (real-time, signal handler).
- **Evitalo** come default: è difficile da fare bene, facile introdurre bug di ABA e di ordinamento della memoria, e spesso non è più veloce di un buon mutex sotto bassa contesa.

## Perché è importante

Le strutture lock-free danno garanzie di progresso ed evitano deadlock e priority inversion, ma l'asticella della correttezza è alta. Conoscere CAS, ABA e il problema della reclamation segnala che sai ragionare a livello di memory model — e, cosa cruciale, sai quando *non* ricorrervi.

CAS

Il problema ABA

Quando usarlo

Perché è importante

Domande correlate