Što je lock-free programiranje i CAS? Objasnite ABA problem i kada ga koristiti.

Question

IT Interview Practice · Accepted Answer

**Lock-free programiranje koordinira niti bez mutexa, koristeći atomske compare-and-swap (CAS) petlje tako da barem jedna nit uvijek napreduje čak i ako druge zapnu.** Nijedna nit ne može biti blokirana od strane druge koja drži zaključavanje.

## CAS

**Compare-and-swap** atomski postavlja lokaciju na novu vrijednost samo ako još drži očekivanu staru vrijednost; inače ne uspije i vi ponovite. To je primitiv iza lock-free stogova, redova i brojača.

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

```java
// Lock-free inkrement preko CAS petlje ponovnog pokušaja
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // ponovi ako je netko drugi pobijedio
```

## ABA problem

CAS samo provjerava je li vrijednost još uvijek očekivana — ne i da se nikada nije promijenila. Ako je prešla A → B → A između vašeg čitanja i CAS-a, CAS uspijeva, ali svijet se pomaknuo ispod vas (npr. oslobođen i ponovno korišten čvor).

```text
Nit 1: čita A ............... CAS(A→X) uspijeva ✗ (ali lista se promijenila!)
Nit 2:      pop A, push B, push A ponovno
```

**Popravak**: uparite pokazivač s brojačem verzije (`AtomicStampedReference`, tagirani pokazivači) tako da A-s-tagom-1 ≠ A-s-tagom-2, ili koristite hazard pointere / epoch reclamation za sigurnost memorije.

## Kada ga koristiti

- **Koristite** za vruće, fino-granulirano dijeljeno stanje (brojači, single-producer redovi) gdje dominira natjecanje za zaključavanjem, ili gdje nit nikada ne smije blokirati (real-time, signal handleri).
- **Izbjegavajte** kao zadano: teško ga je ispravno napraviti, lako uvesti ABA i bugove redoslijeda memorije, i često nije brži od dobrog mutexa pod niskim natjecanjem.

## Zašto je to važno

Lock-free strukture daju jamstva napretka i izbjegavaju deadlock i inverziju prioriteta, ali je ljestvica ispravnosti visoka. Znanje CAS-a, ABA-e i problema reklamacije signalizira da možete rasuđivati na razini memorijskog modela — i, ključno, znate kada *ne* posegnuti za tim.

CAS

ABA problem

Kada ga koristiti

Zašto je to važno

Povezana pitanja