lock-free programming અને CAS શું છે? ABA problem અને તેને ક્યારે વાપરવું તે સમજાવો.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming threads ને mutexes વગર coordinate કરે છે, atomic compare-and-swap (CAS) loops વાપરીને જેથી ઓછામાં ઓછો એક thread હંમેશા આગળ વધે ભલે બીજાં અટકે.** કોઈ thread lock ધરાવતા બીજા દ્વારા block થઈ શકતું નથી.

## CAS

**Compare-and-swap** atomically એક location ને નવી value પર ત્યારે જ set કરે છે જ્યારે તે હજુ અપેક્ષિત જૂની value ધરાવે છે; નહીંતર તે fail થાય છે અને તમે retry કરો છો. તે lock-free stacks, queues, અને counters પાછળનું primitive છે.

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

CAS ફક્ત એ ચકાસે છે કે value હજુ અપેક્ષિત છે — એ નહીં કે તે ક્યારેય બદલાયું નથી. જો તમારા read અને CAS વચ્ચે તે A → B → A ગયું, તો CAS succeed થાય છે પણ દુનિયા તમારી નીચે ખસી ગઈ (દા.ત. freed-and-reused node).

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

**ઉકેલ**: pointer ને version counter સાથે જોડો (`AtomicStampedReference`, tagged pointers) જેથી A-with-tag-1 ≠ A-with-tag-2, કે memory safety માટે hazard pointers / epoch reclamation વાપરો.

## ક્યારે વાપરવું

- **વાપરો** hot, fine-grained shared state (counters, single-producer queues) માટે જ્યાં lock contention પ્રભુત્વ ધરાવે છે, કે જ્યાં thread ક્યારેય block ન થવું જોઈએ (real-time, signal handlers).
- **ટાળો** default તરીકે: તે બરાબર કરવું અઘરું છે, ABA અને memory-ordering bugs દાખલ કરવા સહેલા છે, અને ઓછા contention હેઠળ ઘણી વાર સારા mutex કરતાં વધુ ઝડપી નથી.

## આ શા માટે મહત્વનું છે

Lock-free structures progress ની ખાતરીઓ આપે છે અને deadlock તથા priority inversion ટાળે છે, પણ correctness નો bar ઊંચો છે. CAS, ABA, અને reclamation problem જાણવું સૂચવે છે કે તમે memory-model સ્તરે તર્ક કરી શકો છો — અને, નિર્ણાયક રીતે, ક્યારે તેને *ન* વાપરવું તે જાણો છો.

CAS

ABA problem

ક્યારે વાપરવું

આ શા માટે મહત્વનું છે

સંબંધિત પ્રશ્નો