Vad är lock-free-programmering och CAS? Förklara ABA-problemet och när det ska användas.

Question

IT Interview Practice · Accepted Answer

**Lock-free-programmering koordinerar trådar utan mutexar, med atomära compare-and-swap (CAS)-loopar så att minst en tråd alltid gör framsteg även om andra stannar.** Ingen tråd kan blockeras av en annan som håller ett lås.

## CAS

**Compare-and-swap** sätter atomärt en plats till ett nytt värde endast om den fortfarande håller det förväntade gamla värdet; annars misslyckas den och du försöker igen. Det är primitiven bakom lock-free-stackar, -köer och -räknare.

```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 kontrollerar bara att värdet fortfarande är det förväntade — inte att det aldrig ändrades. Om det gick A → B → A mellan din läsning och CAS lyckas CAS men världen rörde sig under dig (t.ex. en frigjord-och-återanvänd nod).

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

**Fix**: para pekaren med en versionsräknare (`AtomicStampedReference`, taggade pekare) så att A-med-tagg-1 ≠ A-med-tagg-2, eller använd hazard pointers / epoch reclamation för minnessäkerhet.

## När det ska användas

- **Använd** för hett, finkornigt delat tillstånd (räknare, single-producer-köer) där låskonkurrens dominerar, eller där en tråd aldrig får blockera (realtid, signalhanterare).
- **Undvik** som standardval: det är svårt att få rätt, lätt att införa ABA- och minnesordningsbuggar, och ofta inte snabbare än en bra mutex under låg konkurrens.

## Varför det är viktigt

Lock-free-strukturer ger framstegsgarantier och undviker deadlock och prioritetsinversion, men kravnivån för korrekthet är hög. Att känna till CAS, ABA och reclamation-problemet signalerar att du kan resonera på minnesmodellsnivå — och, avgörande, veta när du *inte* ska ta till det.

CAS

ABA-problemet

När det ska användas

Varför det är viktigt

Relaterade frågor