Mitä on lukkovapaa (lock-free) ohjelmointi ja CAS? Selitä ABA-ongelma ja milloin sitä käytetään.

Question

IT Interview Practice · Accepted Answer

**Lukkovapaa ohjelmointi koordinoi säikeitä ilman mutexeja käyttäen atomisia compare-and-swap (CAS) -silmukoita niin, että ainakin yksi säie etenee aina vaikka toiset jumittuisivat.** Mikään säie ei voi olla toisen lukkoa pitävän säikeen estämä.

## CAS

**Compare-and-swap** asettaa muistipaikan uuteen arvoon atomisesti vain, jos se yhä pitää odotettua vanhaa arvoa; muuten se epäonnistuu ja yrität uudelleen. Se on lukkovapaiden pinojen, jonojen ja laskureiden takana oleva primitiivi.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atominen, jakamaton
  else: return false
```

```java
// Lukkovapaa lisäys CAS-uudelleenyrityssilmukalla
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // yritä uudelleen jos joku muu voitti
```

## ABA-ongelma

CAS tarkistaa vain, että arvo on yhä odotettu — ei että se ei koskaan muuttunut. Jos se kävi A → B → A lukusi ja CAS:in välillä, CAS onnistuu mutta maailma liikkui allasi (esim. vapautettu-ja-uudelleenkäytetty solmu).

```text
Säie 1: lue A ............... CAS(A→X) onnistuu ✗ (mutta lista muuttui!)
Säie 2:      pop A, push B, push A uudelleen
```

**Korjaus**: paritta osoitin versiolaskurin kanssa (`AtomicStampedReference`, tagatut osoittimet) niin että A-tagilla-1 ≠ A-tagilla-2, tai käytä hazard-osoittimia / epoch-vapautusta muistiturvallisuuteen.

## Milloin käyttää sitä

- **Käytä** kuumaan, hienojakoiseen jaettuun tilaan (laskurit, single-producer-jonot), missä lukkokilpailu hallitsee, tai missä säie ei saa koskaan estyä (reaaliaika, signaalikäsittelijät).
- **Vältä** oletuksena: sitä on vaikea saada oikein, helppo tuoda ABA- ja muistijärjestysbugit, ja usein ei nopeampi kuin hyvä mutex matalan kilpailun alla.

## Miksi se on tärkeää

Lukkovapaat rakenteet antavat etenemistakuita ja välttävät lukkiuman ja prioriteetti-inversion, mutta korrektisuusrima on korkea. CAS:in, ABA:n ja vapautusongelman tunteminen viestii, että osaat päätellä muistimallitasolla — ja mikä ratkaisevaa, tiedät milloin *olla* tarttumatta siihen.

CAS

ABA-ongelma

Milloin käyttää sitä

Miksi se on tärkeää

Aiheeseen liittyvät kysymykset