Menene lock-free programming da CAS? Bayyana matsalar ABA da lokacin amfani da shi.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming yana daidaita threads ba tare da mutexes ba, yana amfani da atomic compare-and-swap (CAS) loops domin aƙalla thread ɗaya ko da yaushe yana ci gaba ko da wasu suka tsaya.** Babu thread da wani mai riƙe lock zai iya toshe shi.

## CAS

**Compare-and-swap** atomically yana saita wuri zuwa sabuwar daraja kawai idan har yanzu yana riƙe darajar da ake tsammani ta gargajiya; in ba haka ba yana kasawa kuma ka retry. Shine primitive a bayan lock-free stacks, queues, da 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
```

## Matsalar ABA

CAS kawai yana duba darajar har yanzu ita ce ake tsammani — ba cewa bai taɓa canzawa ba. Idan ya tafi A → B → A tsakanin read ɗinka da CAS, CAS yana samun nasara amma duniya ta motsa a ƙarƙashinka (misali node da aka 'yanta kuma aka sāke amfani da shi).

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

**Gyara**: haɗa pointer da version counter (`AtomicStampedReference`, tagged pointers) domin A-da-tag-1 ≠ A-da-tag-2, ko yi amfani da hazard pointers / epoch reclamation don amincin memory.

## Lokacin amfani da shi

- **Yi amfani** ga shared state mai zafi, fine-grained (counters, single-producer queues) inda takara na lock ke rinjaye, ko inda thread ba dole ya taɓa toshewa ba (real-time, signal handlers).
- **Guji** a matsayin tsoho: yana da wahalar samun daidai, mai sauƙin gabatar da ABA da kwarin memory-ordering, kuma sau da yawa ba ya fi sauri fiye da mutex mai kyau a ƙarƙashin ƙarancin takara.

## Me ya sa yake da muhimmanci

Lock-free structures suna ba da tabbacin ci gaba kuma suna kauce wa deadlock da priority inversion, amma matsayin daidaito yana da tsayi. Sanin CAS, ABA, da matsalar reclamation yana nuna kana iya tunani a matakin memory-model — kuma, mafi muhimmanci, sanin lokacin da *ba* za a juya zuwa gare shi ba.

CAS

Matsalar ABA

Lokacin amfani da shi

Me ya sa yake da muhimmanci

Tambayoyi masu alaƙa