Lock-free programming na CAS ni nini? Eleza tatizo la ABA na lini uitumie.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming huratibu threads bila mutexes, ikitumia atomic compare-and-swap (CAS) loops ili angalau thread moja daima ipige hatua hata kama nyingine zinakwama.** Hakuna thread inayoweza kuzuiwa na nyingine iliyoshikilia lock.

## CAS

**Compare-and-swap** kwa njia ya atomic huweka location kwa thamani mpya tu ikiwa bado inashikilia thamani ya zamani iliyotarajiwa; vinginevyo inashindwa na unajaribu tena. Ni primitive iliyo nyuma ya lock-free stacks, queues, na counters.

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

## Tatizo la ABA

CAS huangalia tu kwamba thamani bado ni ile iliyotarajiwa — siyo kwamba haikubadilika kamwe. Ikiwa ilienda A → B → A kati ya read yako na CAS, CAS inafanikiwa lakini dunia imesogea chini yako (mfano node iliyoachiliwa-na-kutumika-tena).

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

**Suluhisho**: unganisha pointer na version counter (`AtomicStampedReference`, tagged pointers) ili A-yenye-tag-1 ≠ A-yenye-tag-2, au tumia hazard pointers / epoch reclamation kwa usalama wa memory.

## Lini uitumie

- **Tumia** kwa shared state yenye shughuli nyingi na fine-grained (counters, single-producer queues) ambapo lock contention inatawala, au ambapo thread lazima kamwe isizuiwe (real-time, signal handlers).
- **Epuka** kama chaguo-msingi: ni ngumu kuifanya sawa, rahisi kuingiza ABA na memory-ordering bugs, na mara nyingi si haraka zaidi ya mutex nzuri chini ya contention ndogo.

## Kwa nini ni muhimu

Lock-free structures hutoa uhakikisho wa maendeleo na kuepuka deadlock na priority inversion, lakini kiwango cha usahihi ni cha juu. Kujua CAS, ABA, na tatizo la reclamation kunaashiria unaweza kufikiri katika kiwango cha memory-model — na, muhimu zaidi, kujua *lini usiitumie*.

CAS

Tatizo la ABA

Lini uitumie

Kwa nini ni muhimu

Maswali yanayohusiana