Qu'est-ce que la programmation lock-free et le CAS ? Expliquez le problème ABA et quand y recourir.

Question

IT Interview Practice · Accepted Answer

**La programmation lock-free coordonne les threads sans mutex, à l'aide de boucles atomiques de compare-and-swap (CAS) pour qu'au moins un thread progresse toujours même si les autres s'arrêtent.** Aucun thread ne peut être bloqué par un autre qui détiendrait un verrou.

## CAS

Le **compare-and-swap** affecte atomiquement une nouvelle valeur à un emplacement seulement s'il contient encore l'ancienne valeur attendue ; sinon il échoue et vous réessayez. C'est la primitive derrière les stacks, queues et compteurs lock-free.

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

```java
// Incrément lock-free via une boucle de réessai CAS
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // réessaie si quelqu'un d'autre l'a emporté
```

## Le problème ABA

Le CAS vérifie seulement que la valeur est toujours celle attendue — pas qu'elle n'a jamais changé. Si elle est passée par A → B → A entre votre lecture et le CAS, le CAS réussit mais le monde a bougé sous vos pieds (par ex. un nœud libéré puis réutilisé).

```text
Thread 1: lit A ................ CAS(A→X) réussit ✗ (mais la liste a changé !)
Thread 2:      pop A, push B, push A à nouveau
```

**Correctif** : associez au pointeur un compteur de version (`AtomicStampedReference`, pointeurs tagués) pour que A-avec-tag-1 ≠ A-avec-tag-2, ou utilisez des hazard pointers / une récupération par époques (epoch reclamation) pour la sûreté mémoire.

## Quand y recourir

- **Utilisez-la** pour un état partagé chaud et à grain fin (compteurs, queues à producteur unique) où la contention sur les verrous domine, ou lorsqu'un thread ne doit jamais bloquer (temps réel, gestionnaires de signaux).
- **Évitez-la** par défaut : elle est difficile à réussir, introduit facilement des bugs d'ABA et d'ordonnancement mémoire, et n'est souvent pas plus rapide qu'un bon mutex en faible contention.

## Pourquoi c'est important

Les structures lock-free offrent des garanties de progression et évitent le deadlock et l'inversion de priorité, mais le niveau d'exigence sur la justesse est élevé. Connaître le CAS, l'ABA et le problème de récupération mémoire montre que vous savez raisonner au niveau du modèle mémoire — et, surtout, savoir quand *ne pas* y recourir.

CAS

Le problème ABA

Quand y recourir

Pourquoi c'est important

Questions connexes