Czym jest programowanie bez blokad i CAS? Wyjaśnij problem ABA i kiedy tego używać.

Question

IT Interview Practice · Accepted Answer

**Programowanie bez blokad (lock-free) koordynuje wątki bez muteksów, używając atomowych pętli compare-and-swap (CAS), tak że przynajmniej jeden wątek zawsze robi postęp, nawet jeśli inne utkną.** Żaden wątek nie może zostać zablokowany przez inny trzymający blokadę.

## CAS

**Compare-and-swap** atomowo ustawia lokalizację na nową wartość tylko wtedy, gdy nadal zawiera oczekiwaną starą wartość; w przeciwnym razie zawodzi i ponawiasz. To prymityw stojący za stosami, kolejkami i licznikami bez blokad.

```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 sprawdza tylko, że wartość nadal jest tą oczekiwaną — a nie, że nigdy się nie zmieniła. Jeśli przeszła A → B → A między Twoim odczytem a CAS, CAS się powiedzie, ale świat pod tobą się zmienił (np. zwolniony i ponownie użyty węzeł).

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

**Poprawka**: sparuj wskaźnik z licznikiem wersji (`AtomicStampedReference`, wskaźniki z etykietą), tak by A-z-etykietą-1 ≠ A-z-etykietą-2, albo użyj wskaźników zagrożenia (hazard pointers) / odzyskiwania epokowego dla bezpieczeństwa pamięci.

## Kiedy tego używać

- **Używaj** dla gorącego, drobnoziarnistego współdzielonego stanu (liczniki, kolejki jednego producenta), gdzie dominuje rywalizacja o blokady, lub gdy wątek nigdy nie może się zablokować (czas rzeczywisty, obsługa sygnałów).
- **Unikaj** jako domyślnego wyboru: trudno to zrobić poprawnie, łatwo wprowadzić błędy ABA i kolejności pamięci, a często nie jest szybsze niż dobry muteks przy niskiej rywalizacji.

## Dlaczego to ważne

Struktury bez blokad dają gwarancje postępu oraz unikają zakleszczeń i inwersji priorytetów, ale poprzeczka poprawności jest wysoko. Znajomość CAS, ABA i problemu odzyskiwania pamięci sygnalizuje, że potrafisz rozumować na poziomie modelu pamięci — i, co kluczowe, wiesz, kiedy *nie* po nie sięgać.

CAS

Problem ABA

Kiedy tego używać

Dlaczego to ważne

Powiązane pytania