Mi az a lock-free programozás és a CAS? Magyarázd el az ABA problémát és azt, mikor használd.

Question

IT Interview Practice · Accepted Answer

**A lock-free programozás mutexek nélkül koordinálja a threadeket, atomi compare-and-swap (CAS) loopokat használva, így legalább egy thread mindig halad, még ha mások megakadnak is.** Egyetlen thread sem blokkolható egy másik által, amely egy lockot tart.

## CAS

A **compare-and-swap** atomilag egy új értékre állít egy helyet, csak ha az még mindig a várt régi értéket tartja; egyébként megbukik és újrapróbálod. Ez a primitív a lock-free stackek, queue-k és számlálók mögött.

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

```java
// Lock-free inkrementálás CAS retry loopon át
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // újrapróbál, ha valaki más nyert
```

## Az ABA probléma

A CAS csak azt ellenőrzi, hogy az érték még mindig a várt-e — nem azt, hogy sosem változott. Ha A → B → A ment a read és a CAS között, a CAS sikerül, de a világ elmozdult alattad (pl. egy felszabadított-és-újrahasznált node).

```text
Thread 1: read A ............... CAS(A→X) sikerül ✗ (de a lista megváltozott!)
Thread 2:      pop A, push B, push A újra
```

**Javítás**: párosítsd a pointert egy verzió-számlálóval (`AtomicStampedReference`, tagged pointerek), hogy A-with-tag-1 ≠ A-with-tag-2, vagy használj hazard pointereket / epoch reclamationt a memóriabiztonságért.

## Mikor használd

- **Használd** forró, finomszemcsés megosztott állapothoz (számlálók, single-producer queue-k), ahol a lock-versengés dominál, vagy ahol egy thread sosem blokkolhat (valós idejű, signal handlerek).
- **Kerüld** alapértelmezettként: nehéz jól csinálni, könnyű ABA és memory-ordering hibákat bevinni, és gyakran nem gyorsabb egy jó mutexnél alacsony versengés alatt.

## Miért fontos

A lock-free struktúrák haladási garanciákat adnak és elkerülik a deadlockot és a prioritásinverziót, de a helyességi léc magas. A CAS, az ABA és a reclamation probléma ismerete azt jelzi, hogy tudsz a memóriamodell szintjén érvelni — és, ami döntő, tudod, mikor *ne* nyúlj hozzá.

CAS

Az ABA probléma

Mikor használd

Miért fontos

Kapcsolódó kérdések