Kaj je programiranje brez zaklepov (lock-free) in CAS? Razložite problem ABA in kdaj ga uporabiti.

Question

IT Interview Practice · Accepted Answer

**Programiranje brez zaklepov usklajuje niti brez mutexov, z uporabo atomarnih zank compare-and-swap (CAS), tako da vsaj ena nit vedno napreduje, tudi če druge obtičijo.** Nobena nit ne more biti blokirana z drugo, ki drži zaklep.

## CAS

**Compare-and-swap** atomarno nastavi lokacijo na novo vrednost le, če ta še vedno vsebuje pričakovano staro vrednost; sicer spodleti in poskusite znova. To je gradnik za sklade, vrste in števce brez zaklepov.

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

## Problem ABA

CAS preveri le, da je vrednost še vedno pričakovana — ne pa, da se nikoli ni spremenila. Če je šla A → B → A med vašim branjem in CAS, CAS uspe, a svet se je pod vami premaknil (npr. sproščen in ponovno uporabljen vozel).

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

**Popravek**: kazalec sparite s števcem različic (`AtomicStampedReference`, označeni kazalci), tako da A-z-oznako-1 ≠ A-z-oznako-2, ali uporabite hazard pointers / epoch reclamation za pomnilniško varnost.

## Kdaj ga uporabiti

- **Uporabite** ga za vroče, drobnozrnato deljeno stanje (števci, vrste z enim proizvajalcem), kjer prevladuje tekmovanje za zaklepe, ali kjer nit nikoli ne sme blokirati (realni čas, obravnavalniki signalov).
- **Izogibajte** se mu kot privzeti izbiri: težko ga je pravilno izvesti, lahko uvede ABA in napake vrstnega reda pomnilnika ter pogosto ni nič hitrejši od dobrega muteksa pri nizkem tekmovanju.

## Zakaj je to pomembno

Strukture brez zaklepov dajejo jamstva napredka ter se izognejo mrtvim zankam in prednostni inverziji, a je lestvica pravilnosti visoka. Poznavanje CAS, ABA in problema ponovne pridobitve pomnilnika (reclamation) signalizira, da znate razmišljati na ravni pomnilniškega modela — in, kar je ključno, veste, kdaj po njem *ne* poseči.

CAS

Problem ABA

Kdaj ga uporabiti

Zakaj je to pomembno

Povezana vprašanja