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** ਇੱਕ location ਨੂੰ atomic ਤੌਰ 'ਤੇ ਇੱਕ ਨਵੇਂ value ਉੱਤੇ ਸੈੱਟ ਕਰਦਾ ਹੈ ਸਿਰਫ਼ ਤਾਂ ਜੇ ਇਹ ਅਜੇ ਵੀ ਉਮੀਦ ਕੀਤਾ ਪੁਰਾਣਾ 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 ਸਫਲ ਹੋ ਜਾਂਦਾ ਹੈ ਪਰ ਦੁਨੀਆ ਤੁਹਾਡੇ ਹੇਠੋਂ ਹਿੱਲ ਗਈ (ਜਿਵੇਂ ਇੱਕ 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 ਪੇਸ਼ ਕਰਨਾ ਆਸਾਨ, ਅਤੇ ਅਕਸਰ low contention ਹੇਠ ਇੱਕ ਚੰਗੇ mutex ਤੋਂ ਤੇਜ਼ ਨਹੀਂ।

## ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

Lock-free structures progress ਗਾਰੰਟੀਆਂ ਦਿੰਦੀਆਂ ਹਨ ਅਤੇ deadlock ਅਤੇ priority inversion ਤੋਂ ਬਚਦੀਆਂ ਹਨ, ਪਰ correctness ਦੀ ਹੱਦ ਉੱਚੀ ਹੈ। CAS, ABA, ਅਤੇ reclamation ਸਮੱਸਿਆ ਨੂੰ ਜਾਣਨਾ ਸੰਕੇਤ ਦਿੰਦਾ ਹੈ ਕਿ ਤੁਸੀਂ memory-model ਪੱਧਰ 'ਤੇ ਤਰਕ ਕਰ ਸਕਦੇ ਹੋ — ਅਤੇ, ਖ਼ਾਸ ਤੌਰ 'ਤੇ, ਜਾਣਦੇ ਹੋ ਕਿ ਇਸ ਵੱਲ *ਕਦੋਂ ਨਹੀਂ* ਜਾਣਾ।

CAS

ABA problem

ਕਦੋਂ ਵਰਤੀਏ

ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

ਸੰਬੰਧਿਤ ਸਵਾਲ