Hva er lock-free-programmering og CAS? Forklar ABA-problemet og når du bør bruke det.

Question

IT Interview Practice · Accepted Answer

**Lock-free-programmering koordinerer tråder uten mutexes, ved hjelp av atomiske compare-and-swap (CAS)-løkker slik at minst én tråd alltid gjør fremgang selv om andre stopper opp.** Ingen tråd kan blokkeres av en annen som holder en lås.

## CAS

**Compare-and-swap** setter atomisk en lokasjon til en ny verdi bare hvis den fortsatt holder den forventede gamle verdien; ellers feiler den og du prøver på nytt. Det er primitivet bak lock-free stacks, køer og tellere.

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

## ABA-problemet

CAS sjekker bare at verdien fortsatt er den forventede — ikke at den aldri endret seg. Hvis den gikk A → B → A mellom lesingen din og CAS-en, lykkes CAS-en, men verden flyttet seg under føttene dine (f.eks. en node som ble frigjort og gjenbrukt).

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

**Løsning**: par pekeren med en versjonsteller (`AtomicStampedReference`, tagged pointers) slik at A-med-tag-1 ≠ A-med-tag-2, eller bruk hazard pointers / epoch reclamation for minnesikkerhet.

## Når du bør bruke det

- **Bruk** det for het, finkornet delt tilstand (tellere, single-producer-køer) der lock contention dominerer, eller der en tråd aldri må blokkere (sanntid, signalhåndterere).
- **Unngå** det som standardvalg: det er vanskelig å få riktig, lett å introdusere ABA- og memory-ordering-feil, og ofte ikke raskere enn en god mutex under lav kamp om ressurser.

## Hvorfor det er viktig

Lock-free-strukturer gir fremgangsgarantier og unngår deadlock og prioritetsinversjon, men kravet til korrekthet er høyt. Å kunne CAS, ABA og reclamation-problemet signaliserer at du kan resonnere på minnemodellnivå — og, avgjørende, vite når du *ikke* bør gripe til det.

CAS

ABA-problemet

Når du bør bruke det

Hvorfor det er viktig

Relaterte spørsmål