Atomics & Compare-And-Swap (CAS)

Locking without locks

A lock fixes the counter race, but blocking threads is expensive and risks deadlock. For a single shared variable there is a faster tool: atomic types backed by Compare-And-Swap (CAS), a hardware instruction (CMPXCHG on x86) that does a read-check-write as one indivisible step.

What CAS actually does

compareAndSet(expected, newValue): atomically — if the current value still equals expected, set it to newValue and return true; otherwise change nothing and return false.

That boolean is the whole trick. If CAS returns false, another thread changed the value in between, so you re-read and try again. Compare this to the race condition: a plain count++ blindly overwrites; CAS detects the conflict and retries, so no update is lost.

The retry loop, traced

#	Thread	Action	counter
1	T1	read → 0	0
2	T2	read → 0	0
3	T1	CAS(0→1) ✓	1
4	T2	CAS(0→1) ✗ (value is 1, not 0)	1
5	T2	re-read → 1	1
6	T2	CAS(1→2) ✓	2

incrementAndGet() is exactly this loop, hidden:

// what AtomicInteger.incrementAndGet() does internally
int v;
do {
    v = get();                  // read current
} while (!compareAndSet(v, v + 1));   // retry until our read was still valid
return v + 1;

Lock-free vs locked — when to use which

	Atomic / CAS	Lock
Scope	One variable	Any multi-step critical section
Blocking	No — spins & retries	Yes — threads park
Best when	Counter, flag, single reference; low–moderate contention	Multiple fields must change together; high contention
Risk	Wasted CPU on retries under heavy contention	Deadlock, lock convoy

The classic gotcha: the ABA problem

CAS only checks the value, not whether it changed and changed back. If a value goes A→B→A, a CAS expecting A succeeds — even though the world moved underneath it (common with reused nodes in lock-free stacks). Fix with a version stamp: AtomicStampedReference compares (value, stamp).

Takeaways

• CAS = atomic "set to new only if still equal to expected"; the failure path is a retry.
• Unlike count++, CAS detects a concurrent change instead of clobbering it.
• Atomics shine for single-variable, low-contention updates; locks for compound critical sections.
• Beware ABA — use a stamped/versioned reference when identity matters.

---

Re-authored for this guide; CAS retry diagram hand-authored as SVG. Follows Java Concurrency in Practice (ch. 15) and Jenkov's non-blocking-algorithms tutorial. See also: Race Conditions, and Memory Model & Visibility.

I just read a lesson on **Atomics & Compare-And-Swap (CAS)** (Concurrency) and want to truly understand it. Explain Atomics & Compare-And-Swap (CAS) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Atomics & Compare-And-Swap (CAS)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Atomics & Compare-And-Swap (CAS)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Atomics & Compare-And-Swap (CAS)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.