Worked examples — Atomic operations and CAS

Before we start, one promise: every symbol is earned. Let us fix the vocabulary with a picture.

Look at the figure: the mailbox holds a value, you hold two cards — an expected card and a new card. CAS compares your expected card to what is inside. Match → it swaps in your new card. Mismatch → it slaps your hand away and tells you the real value so you can try again.

We will write memory contents using $\ast addr$, read aloud as “the value stored at that address” (the star means “look inside the box”). So $\ast addr=10$ means the box currently holds 10.

The scenario matrix

Every CAS story falls into one of these cells. The examples below are labelled with the cell they hit, and together they cover all of them.

Example A — CAS succeeds on the first try

Forecast: guess return value and final box contents before reading on.

1. Read the current value. $\ast addr=42$. Why this step? CAS internally compares $\ast addr$ against $exp$; we must know $\ast addr$ to reason about it.
2. Compare $exp$ to $\ast addr$. Is $exp=42$ equal to $\ast addr=42$? Yes. Why this step? This equality is the entire decision CAS makes.
3. Swap in $new$. Since they match, $\ast addr\leftarrow 99$ and CAS returns true. Why this step? A matching guess is CAS's licence to write.

Verify: final $\ast addr=99$, return $=$ true. Sanity check: exactly one thread, no interference, so of course the guess held.

Example B — CAS fails once, then retries and wins

void atomic_increment(int* counter) {
    int old_val, new_val;
    do {
        old_val = *counter;
        new_val = old_val + 1;
    } while (!CAS(counter, old_val, new_val));
}

Forecast: how many times does Thread 1 call CAS, and what is the final value after both threads finish?

1. Attempt 1 — read. Thread 1 reads $old\_val=5$, computes $new\_val=6$. Why this step? We must snapshot the value we intend to modify.
2. Interleave. Thread 2 runs first, does $\text{CAS}(counter,5,6)$ → success. Now $\ast counter=6$. Why this step? This is the race we are stress-testing — the box changed under Thread 1's feet.
3. Attempt 1 — CAS. Thread 1 calls $\text{CAS}(counter,5,6)$. But $\ast counter=6\ne 5$. Returns false. Loop repeats. Why this step? Thread 1's guess (5) is now stale; strong CAS's false here means a genuine mismatch — it correctly refuses to clobber Thread 2's work.
4. Attempt 2 — read. Thread 1 re-reads $old\_val=6$, computes $new\_val=7$. Why this step? Fresh read = fresh, correct guess.
5. Attempt 2 — CAS. $\text{CAS}(counter,6,7)$ → success. $\ast counter=7$.

Verify: two increments starting from 5 must give $5+1+1=7$. Final value 7 ✓ — no update was lost, which is the whole point. Thread 1 called CAS twice. Contrast with the lost-update bug where both threads would have written 6.

Example C — CAS that must fail (only-if update)

Forecast: true or false? Does the box change?

1. Compare. $exp=0$ vs $\ast addr=1$. Not equal. Why this step? The programmer wants the write to happen only from state 0; a mismatch means the precondition is not met.
2. No write. CAS leaves $\ast addr=1$ untouched and returns false. Why this step? This is CAS as a guarded write — the guard failed, so nothing happens. This is exactly how test-and-set spinlocks avoid stomping a held lock.

Verify: box unchanged at 1, return false. Sanity: with strong CAS a false definitively means "condition not met" (not a spurious lie). The caller decides whether to retry, wait, or abort.

Example D — Deriving Fetch-And-Add, and the return-old subtlety

int fetch_and_add(int* addr, int delta) {
    int old_val, new_val;
    do {
        old_val = *addr;
        new_val = old_val + delta;
    } while (!CAS(addr, old_val, new_val));
    return old_val;   // OLD value, not new!
}

Forecast: returned value and final box value — they are different; predict both.

1. Read. $old\_val=10$. Why this step? We need the pre-increment value both to compute the sum and to return it.
2. Compute. $new\_val=old\_val+\Delta =10+3=13$. Why this step? Do the arithmetic outside the atomic step so the atomic part stays a single cheap compare-swap.
3. CAS. $\text{CAS}(addr,10,13)$ → success (no contention). $\ast addr=13$.
4. Return. Return $old\_val=10$. Why this step? Fetch-and-add's contract is "give me the value before my add." That is what makes it useful for handing out unique indices — each caller gets a distinct old value.

Verify: returns 10, box becomes 13. Check: $\text{return}+\Delta =10+3=13=\ast addr$ ✓. This is the invariant $new=old+\Delta$.

Example E — Degenerate inputs

Forecast: does E1 change anything? Does E2 dereference NULL and crash?

E1 — zero delta:

1. Compute. $new\_val=7+0=7$. Why this step? $\Delta =0$ is the identity for addition — new equals old.
2. CAS. $\text{CAS}(addr,7,7)$ succeeds (7 equals 7), writes 7 over 7 (a no-op write). Why this step? CAS still succeeds; it just writes the same value. Return is $7$.

Verify E1: returns 7, box stays 7. A zero-delta fetch-and-add is a valid atomic read — a legitimate idiom.

E2 — pop from empty stack:

Node* pop() {
    Node* old_top;
    Node* new_top;
    do {
        old_top = stack_top;
        if (old_top == NULL) return NULL;   // guard FIRST
        new_top = old_top->next;
    } while (!CAS(&stack_top, old_top, new_top));
    return old_top;
}

1. Read top. $old\_top=\text{NULL}$. Why this step? Snapshot before touching anything.
2. Guard. Since $old\_top$ is NULL, return NULL immediately — never dereference NULL. Why this step? Skipping the guard would do NULL->next, a crash. Every real lock-free structure needs this degenerate check.

Verify E2: returns NULL, no dereference, no CAS attempted. Correct empty-stack behaviour.

Example F — Limiting behaviour: high contention & livelock

Forecast: does the CAS loop deadlock, livelock, or just slow down?

1. No deadlock. At every instant at least one thread's CAS succeeds (whoever's guess matches the current value). Why this step? CAS is lock-free: system-wide progress is guaranteed because a failing CAS means someone else made progress.
2. But possible starvation. A specific unlucky thread can keep losing races and retry indefinitely — that is livelock for that thread, not the system. Why this step? Lock-freedom guarantees some thread progresses, not every thread. Fairness needs extra work (see Lock-Free Data Structures).
3. Throughput saturates. Each successful CAS invalidates the cache line on all other cores (see Cache Coherence Protocols), so more threads → more coherence traffic → the line "ping-pongs." Throughput plateaus and can even drop. Why this step? The limiting cost is cache-line bouncing, not CPU arithmetic.

Verify: limiting case reasoning — with $N$ increments total the final value is always $\text{start}+N$ regardless of interleaving; correctness never breaks, only speed. E.g. start $0$, $N=1000$ threads each +1 once → final $1000$.

Example G — The ABA trap fires

Forecast: Thread 1's CAS — does it succeed? Is that success correct?

1. T1 reads. $old\_top=A$, plans $new\_top=A\text{->}next=B$. Then T1 is preempted. Why this step? T1's guess "top is A, next is B" is now frozen in time.
2. T2 pops A. $stack\_top\to B\to \text{NULL}$. Node $A$ is freed.
3. T2 pops B. $stack\_top=\text{NULL}$. Node $B$ is freed.
4. T2 pushes A back (memory allocator reused the freed block). $stack\_top\to A\to \text{NULL}$. Why this step? The pointer value $A$ returned, but $A\text{->}next$ is now NULL, not $B$.
5. T1 resumes CAS. $\text{CAS}(\&stack\_top,A,B)$. Current top is $A$, so strong CAS succeeds — and sets $stack\_top=B$. Why this step? Disaster: $B$ was freed in step 3. The stack now points into reclaimed memory. Note this is not a spurious failure issue — CAS did exactly what strong CAS promises; the flaw is that value-equality is not identity-equality.

Verify: CAS returned true (pointer matched) yet the result is corrupt. The bug is that CAS compares the bits of the pointer, not the identity of the object. This is the ABA problem.

Example H — ABA fixed with a version counter

Forecast: does T1's CAS succeed this time?

1. T1 reads. $old=\{A,7\}$, plans $new=\{B,8\}$. Preempted. Why this step? T1 captures both the pointer and the version at read time.
2. T2 pops A → $\{B,8\}$. Pops B → $\{\text{NULL},9\}$. Pushes A → $\{A,10\}$. Why this step? Three successful modifications bumped the version three times: $7\to 10$.
3. T1 resumes CAS. $\text{CAS}(\&stack\_top,\{A,7\},\{B,8\})$. Current is $\{A,10\}$. Pointer matches, but $version10\ne 7$ → CAS fails. Why this step? The version acts as a "generation stamp." Even though the pointer wrecked its way back to $A$, the world moved on and the stamp proves it.
4. T1 retries with a fresh read of $\{A,10\}$ — safe now.

Verify: CAS returns false, corruption avoided. Sanity check on versions: 3 modifications ⇒ version increased by exactly 3, $7+3=10\ne 7$. This needs double-width CAS (128-bit on x86: CMPXCHG16B). See Memory Barriers for why the version write and pointer write must be one indivisible unit.

Example I — Real-world word problem: ticket dispenser

Forecast: the three seat numbers and the final counter.

1. Request 1. fetch_and_add(counter,1) returns the old value $100$; counter → $101$. Why this step? Fetch-and-add returns the pre-increment value — that is the assigned seat, guaranteeing uniqueness.
2. Request 2. fetch_and_add(counter,1) returns $101$; counter → $102$. Why this step? Whatever the interleaving, atomicity means no two requests can read the same old value — each caller sees a distinct snapshot, so no seat is handed out twice.
3. Request 3. fetch_and_add(counter,1) returns $102$; counter → $103$. Why this step? The third caller likewise gets its own unique pre-increment value, completing the batch of three distinct seats.

Verify: seats assigned $\{100,101,102\}$ — all distinct ✓. Final counter $=100+3=103$ ✓ (start $+$ number of requests). No double-booking, no locks. This is why fetch-and-add is the go-to primitive for ID/seat generation.

Example J — Exam twist: weak vs strong CAS (spurious failure)

Forecast: bug, or legal behaviour?

1. Recognise the mechanism. On ARM/RISC-V, CAS is built from Load-Link / Store-Conditional. The SC can fail because the reservation was broken by an unrelated event (an interrupt, a context switch, another access to the same cache line). Why this step? The parent note's LL/SC section is the key: SC "fails if the reservation is broken," and a reservation can break for reasons having nothing to do with the value — this is exactly the spurious failure defined at the top of the page.
2. Weak CAS forwards that spurious failure. ${\text{CAS}}_{weak}$ may return false even when $\ast addr=exp$. This is legal and documented behaviour, not a hardware fault. Why this step? Exposing spurious failure lets the compiler emit a single LL/SC pair (fast) instead of an internal retry loop.
3. Strong CAS hides it. ${\text{CAS}}_{strong}$ retries internally so it only returns false on a genuine value mismatch — but costs an inner loop. This is why every earlier example on this page assumed strong CAS: their "false always means real mismatch" reasoning only holds for the strong variant. Why this step? Choose weak inside a loop you already retry (increment, push); choose strong for a one-shot conditional update (Example C).

Verify: returning false with $\ast addr$ unchanged is correct for weak CAS — not a bug. The programmer's outer loop simply retries: on the next iteration $\ast addr$ still reads $5$, the guess still matches, and (assuming no further spurious break) the increment lands $5\to 6$. Same final result as strong CAS, e.g. box ends at $6$. This trade-off is tied to memory ordering semantics.