What is lock-free programming and CAS? Explain the ABA problem and when to use it.

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 ను ఒక new value కు atomic గా set చేస్తుంది, అది ఇప్పటికీ ఆశించిన old 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
```

**Fix**: 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 ను ప్రవేశపెట్టడం సులభం, మరియు తక్కువ contention కింద తరచుగా మంచి mutex కంటే వేగంగా ఉండదు.

## ఇది ఎందుకు ముఖ్యం

Lock-free structures progress హామీలను ఇస్తాయి మరియు deadlock మరియు priority inversion ను నివారిస్తాయి, కానీ correctness బార్ ఎక్కువ. CAS, ABA, మరియు reclamation problem ను తెలుసుకోవడం, మీరు memory-model స్థాయిలో వివరించగలరని — మరియు, ముఖ్యంగా, దాన్ని ఎప్పుడు *వాడకూడదో* తెలుసునని సూచిస్తుంది.

CAS

ABA problem

దాన్ని ఎప్పుడు ఉపయోగించాలి

ఇది ఎందుకు ముఖ్యం

సంబంధిత ప్రశ్నలు