Hvad er lock-free-programmering og CAS? Forklar ABA-problemet, og hvornår man skal bruge det.

Question

IT Interview Practice · Accepted Answer

**Lock-free-programmering koordinerer tråde uden mutexes ved at bruge atomiske compare-and-swap-løkker (CAS), så mindst én tråd altid gør fremskridt, selv hvis andre går i stå.** Ingen tråd kan blive blokeret af en anden, der holder en lock.

## CAS

**Compare-and-swap** sætter atomisk en placering til en ny værdi kun, hvis den stadig holder den forventede gamle værdi; ellers fejler den, og du prøver igen. Det er primitiven bag lock-free stacks, queues og tællere.

```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 tjekker kun, at værdien stadig er den forventede — ikke at den aldrig ændrede sig. Hvis den gik A → B → A mellem din læsning og din CAS, lykkes CAS'en, men verden flyttede sig under dig (f.eks. en node, der blev frigivet og genbrugt).

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

**Rettelse**: par pointeren med en versionstæller (`AtomicStampedReference`, tagged pointers), så A-med-tag-1 ≠ A-med-tag-2, eller brug hazard pointers / epoch reclamation for hukommelsessikkerhed.

## Hvornår man skal bruge det

- **Brug** det til hot, finkornet delt state (tællere, single-producer queues), hvor lock-contention dominerer, eller hvor en tråd aldrig må blokere (real-time, signal handlers).
- **Undgå** det som default: det er svært at få rigtigt, nemt at introducere ABA- og memory-ordering-bugs, og ofte ikke hurtigere end en god mutex under lav contention.

## Hvorfor det betyder noget

Lock-free-strukturer giver progress-garantier og undgår deadlock og priority inversion, men korrekthedskravet er højt. At kende CAS, ABA og reclamation-problemet signalerer, at du kan ræsonnere på memory-model-niveau — og, afgørende, ved, hvornår man *ikke* skal gribe efter det.

CAS

ABA-problemet

Hvornår man skal bruge det

Hvorfor det betyder noget

Relaterede spørgsmål