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 coordinates threads without mutexes, using atomic compare-and-swap (CAS) loops so at least one thread always makes progress even if others stall.** No thread can be blocked by another holding a lock.

## CAS

**Compare-and-swap** atomically sets a location to a new value only if it still holds the expected old value; otherwise it fails and you retry. It's the primitive behind lock-free stacks, queues, and counters.

```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
```

## The ABA problem

CAS only checks the value is still the expected one — not that it never changed. If it went A → B → A between your read and CAS, the CAS succeeds but the world moved underneath you (e.g. a 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**: pair the pointer with a version counter (`AtomicStampedReference`, tagged pointers) so A-with-tag-1 ≠ A-with-tag-2, or use hazard pointers / epoch reclamation for memory safety.

## When to use it

- **Use** for hot, fine-grained shared state (counters, single-producer queues) where lock contention dominates, or where a thread must never block (real-time, signal handlers).
- **Avoid** as a default: it's hard to get right, easy to introduce ABA and memory-ordering bugs, and often no faster than a good mutex under low contention.

## Why it matters

Lock-free structures give progress guarantees and avoid deadlock and priority inversion, but the correctness bar is high. Knowing CAS, ABA, and the reclamation problem signals you can reason at the memory-model level — and, crucially, know when *not* to reach for it.

CAS

The ABA problem

When to use it

Why it matters

Related questions