lock-free programming اور CAS کیا ہیں؟ ABA problem اور اسے کب استعمال کریں، کی وضاحت کریں۔

Question

IT Interview Practice · Accepted Answer

**Lock-free programming threads کو mutexes کے بغیر مربوط کرتی ہے، atomic compare-and-swap (CAS) loops استعمال کرتے ہوئے تاکہ کم از کم ایک thread ہمیشہ آگے بڑھے چاہے دوسری رک جائیں۔** کوئی thread کسی دوسری کے lock پکڑنے سے block نہیں ہو سکتی۔

## CAS

**Compare-and-swap** atomically ایک location کو ایک نئی value پر تب ہی set کرتی ہے جب وہ اب بھی متوقع پرانی value رکھتی ہو؛ ورنہ یہ ناکام ہو جاتی ہے اور آپ دوبارہ کوشش کرتے ہیں۔ یہ 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 کامیاب ہو جاتی ہے لیکن دنیا آپ کے نیچے سے کھسک گئی (مثلاً ایک free-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 کا معیار بلند ہے۔ CAS، ABA، اور reclamation problem کو جاننا اشارہ دیتا ہے کہ آپ memory-model کی سطح پر استدلال کر سکتے ہیں — اور، اہم بات یہ کہ، جانتے ہیں کہ اس کی طرف *کب نہیں* جانا۔

CAS

ABA problem

اسے کب استعمال کریں

یہ کیوں اہم ہے

متعلقہ سوالات