Kas yra programavimas be užraktų (lock-free) ir CAS? Paaiškinkite ABA problemą ir kada tai naudoti.

Question

IT Interview Practice · Accepted Answer

**Programavimas be užraktų koordinuoja gijas be mutex'ų, naudodamas atominius compare-and-swap (CAS) ciklus, kad bent viena gija visada darytų pažangą, net jei kitos užstringa.** Jokia gija negali būti blokuojama kitos, laikančios užraktą.

## CAS

**Compare-and-swap** atomiškai nustato vietą į naują reikšmę tik tada, jei ji vis dar laiko tikėtiną seną reikšmę; kitaip jis nepavyksta ir jūs kartojate. Tai primityvas už be užraktų dėklų, eilių ir skaitiklių.

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

CAS tik tikrina, ar reikšmė vis dar yra tikėtoji — ne tai, kad ji niekada nesikeitė. Jei ji perėjo A → B → A tarp jūsų skaitymo ir CAS, CAS pavyksta, bet pasaulis pasislinko po jumis (pvz. atlaisvintas ir pakartotinai panaudotas mazgas).

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

**Sprendimas**: suporuokite rodyklę su versijos skaitikliu (`AtomicStampedReference`, žymėtos rodyklės), kad A-su-žyme-1 ≠ A-su-žyme-2, arba naudokite pavojingumo rodykles (hazard pointers) / epochų atgavimą atminties saugumui.

## Kada tai naudoti

- **Naudokite** karštai, smulkiadetaliai bendrai būsenai (skaitikliai, vieno gamintojo eilės), kur užraktų konkurencija dominuoja, arba kur gija niekada neturi blokuotis (realaus laiko, signalų tvarkyklės).
- **Venkite** kaip numatytojo: sunku padaryti teisingai, lengva įvesti ABA ir atminties tvarkos klaidas, ir dažnai ne greitesnis nei geras mutex esant mažai konkurencijai.

## Kodėl tai svarbu

Be užraktų struktūros suteikia pažangos garantijas ir išvengia aklaviečių bei prioritetų inversijos, bet teisingumo kartelė aukšta. CAS, ABA ir atgavimo problemos žinojimas signalizuoja, kad galite samprotauti atminties modelio lygmenyje — ir, kas svarbiausia, žinote, kada *ne*griebti jo.

CAS

ABA problema

Kada tai naudoti

Kodėl tai svarbu

Susiję klausimai