Ce este programarea lock-free și CAS? Explică problema ABA și când să o folosești.

Question

IT Interview Practice · Accepted Answer

**Programarea lock-free coordonează thread-urile fără mutex-uri, folosind bucle atomice de compare-and-swap (CAS) astfel încât cel puțin un thread să progreseze mereu, chiar dacă altele stagnează.** Niciun thread nu poate fi blocat de altul care ține un lock.

## CAS

**Compare-and-swap** setează atomic o locație la o valoare nouă doar dacă ea încă deține valoarea veche așteptată; altfel eșuează și reîncerci. Este primitiva din spatele stivelor, cozilor și contoarelor lock-free.

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

```java
// Increment lock-free printr-o buclă de retry CAS
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // reîncearcă dacă altcineva a câștigat
```

## Problema ABA

CAS verifică doar că valoarea este încă cea așteptată — nu că nu s-a schimbat niciodată. Dacă a mers A → B → A între citirea ta și CAS, CAS reușește, dar lumea s-a mișcat pe dedesubt (ex. un nod eliberat și reutilizat).

```text
Thread 1: read A ............... CAS(A→X) reușește ✗ (dar lista s-a schimbat!)
Thread 2:      pop A, push B, push A din nou
```

**Remediere**: împerechează pointer-ul cu un contor de versiune (`AtomicStampedReference`, tagged pointers) astfel încât A-cu-tag-1 ≠ A-cu-tag-2, sau folosește hazard pointers / epoch reclamation pentru siguranța memoriei.

## Când s-o folosești

- **Folosește** pentru stare partajată fierbinte, cu granularitate fină (contoare, cozi single-producer) unde contenția pe lock-uri domină, sau unde un thread nu trebuie să se blocheze niciodată (real-time, signal handlers).
- **Evită** ca opțiune implicită: este greu de făcut corect, ușor de introdus bug-uri ABA și de ordonare a memoriei, și adesea nu mai rapid decât un mutex bun sub contenție redusă.

## De ce contează

Structurile lock-free oferă garanții de progres și evită deadlock-ul și inversarea de prioritate, dar bara de corectitudine este ridicată. Cunoașterea CAS, ABA și a problemei de reclamare semnalează că poți raționa la nivelul modelului de memorie — și, esențial, știi când *să nu* apelezi la ea.

CAS

Problema ABA

Când s-o folosești

De ce contează

Întrebări conexe