Was ist lock-freie Programmierung und CAS? Erkläre das ABA-Problem und wann man es einsetzt.

Question

IT Interview Practice · Accepted Answer

**Lock-freie Programmierung koordiniert Threads ohne Mutexe, indem sie atomare Compare-and-Swap-Schleifen (CAS) nutzt, sodass mindestens ein Thread immer Fortschritt macht, selbst wenn andere ins Stocken geraten.** Kein Thread kann durch einen anderen, der ein Lock hält, blockiert werden.

## CAS

**Compare-and-Swap** setzt eine Stelle atomar auf einen neuen Wert, aber nur, wenn sie noch den erwarteten alten Wert enthält; andernfalls schlägt es fehl und du versuchst es erneut. Es ist das Primitiv hinter lock-freien Stacks, Queues und Zählern.

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

## Das ABA-Problem

CAS prüft nur, dass der Wert noch der erwartete ist — nicht, dass er sich nie geändert hat. Ging er zwischen deinem Lesen und dem CAS von A → B → A, gelingt das CAS, aber die Welt hat sich unter dir bewegt (z. B. ein freigegebener und wiederverwendeter Knoten).

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

**Lösung**: Kopple den Zeiger mit einem Versionszähler (`AtomicStampedReference`, getaggte Zeiger), sodass A-mit-Tag-1 ≠ A-mit-Tag-2, oder nutze Hazard Pointer / Epoch Reclamation für Speichersicherheit.

## Wann man es einsetzt

- **Einsetzen** für heißen, feingranularen gemeinsamen Zustand (Zähler, Single-Producer-Queues), wo Lock-Contention dominiert, oder wo ein Thread niemals blockieren darf (Echtzeit, Signal-Handler).
- **Vermeiden** als Standard: Es ist schwer richtig hinzubekommen, leicht führt es ABA- und Speicherreihenfolge-Fehler ein und ist bei geringer Contention oft nicht schneller als ein guter Mutex.

## Warum es wichtig ist

Lock-freie Strukturen geben Fortschrittsgarantien und vermeiden Deadlock und Prioritätsinversion, aber die Korrektheitslatte ist hoch. CAS, ABA und das Reclamation-Problem zu kennen signalisiert, dass du auf Speichermodell-Ebene argumentieren kannst — und, entscheidend, weißt, wann du *nicht* dazu greifen solltest.

CAS

Das ABA-Problem

Wann man es einsetzt

Warum es wichtig ist

Ähnliche Fragen