Lock-free programming आणि CAS म्हणजे काय? ABA समस्या आणि ते कधी वापरावे हे समजावून सांगा.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming mutexes शिवाय threads समन्वयित करते, atomic compare-and-swap (CAS) loops वापरून जेणेकरून इतर अडकले तरी किमान एक thread नेहमी प्रगती करतो.** कोणत्याही thread ला lock धरून ठेवणाऱ्या दुसऱ्याकडून block करता येत नाही.

## CAS

**Compare-and-swap** एका location ला atomically नवीन value वर सेट करते फक्त जर तिच्यात अजूनही अपेक्षित जुनी value असेल तर; अन्यथा ते fail होते आणि तुम्ही पुन्हा प्रयत्न करता. हे 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 समस्या

CAS फक्त value अजूनही अपेक्षित तीच आहे का हे तपासते — ती कधीही बदलली नाही हे नाही. जर तुमच्या read आणि CAS दरम्यान ती A → B → A अशी गेली, तर CAS यशस्वी होते पण जग तुमच्या पायाखालून सरकले (उदा. एक free-केलेला-आणि-पुन्हा-वापरलेला 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 वापरा.

## ते कधी वापरावे

- जिथे lock contention प्रबळ असते अशा hot, fine-grained shared state साठी (counters, single-producer queues), किंवा जिथे thread कधीही block होऊ नये (real-time, signal handlers) तिथे **वापरा**.
- default म्हणून **टाळा**: ते बरोबर करणे कठीण आहे, ABA आणि memory-ordering bugs आणणे सोपे आहे, आणि low contention खाली अनेकदा चांगल्या mutex पेक्षा वेगवान नसते.

## हे का महत्त्वाचे आहे

Lock-free structures progress हमी देतात आणि deadlock व priority inversion टाळतात, पण correctness ची पातळी उच्च असते. CAS, ABA, आणि reclamation समस्या जाणणे हे दर्शवते की तुम्ही memory-model पातळीवर तर्क करू शकता — आणि, महत्त्वाचे म्हणजे, ते *कधी* वापरू नये हे जाणता.

CAS

ABA समस्या

ते कधी वापरावे

हे का महत्त्वाचे आहे

संबंधित प्रश्न