Wat is lock-free programming en CAS? Leg het ABA-probleem uit en wanneer je het gebruikt.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming coördineert threads zonder mutexes, met atomic compare-and-swap (CAS)-lussen zodat ten minste één thread altijd vooruitgang boekt, zelfs als anderen stilvallen.** Geen enkele thread kan geblokkeerd worden door een ander die een lock vasthoudt.

## CAS

**Compare-and-swap** zet een locatie atomair op een nieuwe waarde alleen als hij nog steeds de verwachte oude waarde bevat; anders faalt hij en probeer je opnieuw. Het is het primitief achter lock-free stacks, queues en counters.

```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
```

## Het ABA-probleem

CAS controleert alleen dat de waarde nog steeds de verwachte is — niet dat hij nooit veranderde. Als hij tussen je read en de CAS van A → B → A ging, slaagt de CAS maar is de wereld onder je verschoven (bijv. een vrijgegeven en hergebruikte node).

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

**Fix**: koppel de pointer aan een version counter (`AtomicStampedReference`, tagged pointers) zodat A-met-tag-1 ≠ A-met-tag-2, of gebruik hazard pointers / epoch reclamation voor memory safety.

## Wanneer je het gebruikt

- **Gebruik** het voor hete, fijnkorrelige gedeelde state (counters, single-producer queues) waar lock-contentie domineert, of waar een thread nooit mag blokkeren (real-time, signal handlers).
- **Vermijd** het als standaard: het is moeilijk om goed te krijgen, gemakkelijk om ABA- en memory-ordering-bugs te introduceren, en vaak niet sneller dan een goede mutex onder lage contentie.

## Waarom het belangrijk is

Lock-free structuren geven progress-garanties en vermijden deadlock en priority inversion, maar de correctheidslat ligt hoog. CAS, ABA en het reclamation-probleem kennen signaleert dat je op memory-model-niveau kunt redeneren — en, cruciaal, weet wanneer je er *niet* naar moet grijpen.

CAS

Het ABA-probleem

Wanneer je het gebruikt

Waarom het belangrijk is

Gerelateerde vragen