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 सेट गर्छ यदि यसमा अझै अपेक्षित पुरानो मान छ भने मात्र; नत्र यो 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 समस्या

CAS ले मान अझै अपेक्षित नै छ कि भनेर मात्र जाँच्छ — यो कहिल्यै बदलिएन भन्ने होइन। यदि यो तपाईंको read र CAS बीच A → B → A भयो भने, CAS सफल हुन्छ तर संसार तपाईंमुनि सर्‍यो (जस्तै 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 साझा state (counters, single-producer queues) का लागि जहाँ lock contention हावी हुन्छ, वा जहाँ thread कहिल्यै block हुनु हुँदैन (real-time, signal handlers)।
- **टार्नुहोस्** डिफल्टका रूपमा: यो सही पार्न गाह्रो छ, ABA र memory-ordering bugs सजिलै ल्याउँछ, र प्रायः low contention मा राम्रो mutex भन्दा छिटो हुँदैन।

## यो किन महत्त्वपूर्ण छ

Lock-free structures ले progress guarantees दिन्छन् र deadlock अनि priority inversion टार्छन्, तर correctness को स्तर उच्च छ। CAS, ABA, र reclamation समस्या जान्नुले तपाईं memory-model तहमा तर्क गर्न सक्नुहुन्छ — र, महत्त्वपूर्ण कुरा, यो *कहिले नरोज्ने* भन्ने पनि जान्नुहुन्छ भन्ने संकेत गर्छ।

CAS

ABA समस्या

कहिले प्रयोग गर्ने

यो किन महत्त्वपूर्ण छ

सम्बन्धित प्रश्नहरू