lock-free programming এবং CAS কী? ABA সমস্যা এবং কখন এটি ব্যবহার করবেন ব্যাখ্যা করুন।

Question

IT Interview Practice · Accepted Answer

**Lock-free programming mutex ছাড়াই thread সমন্বয় করে, atomic compare-and-swap (CAS) loop ব্যবহার করে যাতে অন্যরা থমকে গেলেও অন্তত একটি thread সবসময় অগ্রগতি করে।** কোনো thread একটি lock ধরে রাখা অন্যটি দ্বারা block হতে পারে না।

## CAS

**Compare-and-swap** একটি location-কে একটি নতুন মানে atomically সেট করে কেবল যদি এটি এখনও প্রত্যাশিত পুরনো মান ধরে রাখে; অন্যথায় এটি fail করে এবং আপনি retry করেন। এটি lock-free stack, queue, এবং counter-এর পিছনের 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 pointer)-এর সাথে জোড়া দিন যাতে A-with-tag-1 ≠ A-with-tag-2, অথবা memory safety-র জন্য hazard pointer / epoch reclamation ব্যবহার করুন।

## কখন এটি ব্যবহার করবেন

- **ব্যবহার করুন** hot, fine-grained shared state (counter, single-producer queue)-এর জন্য যেখানে lock contention প্রাধান্য পায়, বা যেখানে একটি thread কখনো block করা উচিত নয় (real-time, signal handler)।
- **এড়িয়ে চলুন** একটি ডিফল্ট হিসেবে: এটি সঠিক করা কঠিন, ABA ও memory-ordering bug আনা সহজ, এবং low contention-এর অধীনে প্রায়ই একটি ভালো mutex-এর চেয়ে দ্রুত নয়।

## এটি কেন গুরুত্বপূর্ণ

Lock-free structure অগ্রগতির guarantee দেয় এবং deadlock ও priority inversion এড়ায়, কিন্তু correctness-এর মান উঁচু। CAS, ABA, এবং reclamation সমস্যা জানা সংকেত দেয় আপনি memory-model স্তরে যুক্তি দিতে পারেন — এবং, গুরুত্বপূর্ণভাবে, কখন এটির দিকে হাত *না* বাড়াতে হবে তা জানেন।

CAS

ABA সমস্যা

কখন এটি ব্যবহার করবেন

এটি কেন গুরুত্বপূর্ণ

সম্পর্কিত প্রশ্ন