Co je lock-free programování a CAS? Vysvětlete ABA problém a kdy jej použít.

Question

IT Interview Practice · Accepted Answer

**Lock-free programování koordinuje vlákna bez mutexů pomocí atomických compare-and-swap (CAS) smyček, takže alespoň jedno vlákno vždy postupuje, i když ostatní uváznou.** Žádné vlákno nemůže být zablokováno jiným, které drží zámek.

## CAS

**Compare-and-swap** atomicky nastaví umístění na novou hodnotu jen tehdy, pokud stále drží očekávanou starou hodnotu; jinak selže a vy opakujete. Je to primitivum za lock-free zásobníky, frontami a čítači.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomické, nedělitelné
  else: return false
```

```java
// Lock-free increment přes CAS retry smyčku
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // opakuj, pokud vyhrál někdo jiný
```

## ABA problém

CAS kontroluje jen to, že hodnota je stále očekávaná — ne že se nikdy nezměnila. Pokud přešla A → B → A mezi vaším čtením a CAS, CAS uspěje, ale svět se pod vámi pohnul (např. uvolněný a znovupoužitý uzel).

```text
Vlákno 1: čte A ............... CAS(A→X) uspěje ✗ (ale seznam se změnil!)
Vlákno 2:      pop A, push B, push A znovu
```

**Oprava**: spárujte ukazatel s čítačem verze (`AtomicStampedReference`, tagované ukazatele), aby A-s-tagem-1 ≠ A-s-tagem-2, nebo použijte hazard pointers / epoch reclamation pro paměťovou bezpečnost.

## Kdy jej použít

- **Použijte** pro horký, jemně zrnitý sdílený stav (čítače, single-producer fronty), kde dominuje soupeření o zámky, nebo kde vlákno nikdy nesmí blokovat (real-time, signal handlery).
- **Vyhněte se** jako výchozí volbě: je těžké jej správně napsat, snadné zavést ABA a chyby pořadí paměti a často není rychlejší než dobrý mutex při nízkém soupeření.

## Proč je to důležité

Lock-free struktury dávají záruky postupu a vyhýbají se deadlocku a inverzi priorit, ale laťka správnosti je vysoká. Znalost CAS, ABA a problému reklamace paměti signalizuje, že umíte uvažovat na úrovni paměťového modelu — a, což je klíčové, vědět, kdy po tom *nesáhnout*.

CAS

ABA problém

Kdy jej použít

Proč je to důležité

Související otázky