Atomic operations and CAS: Question bank — Hardware deep dive

This is a self-test page. Each line is a question ::: answer reveal. Cover the answer, argue it out loud, then check. The goal is not memorising facts but killing the specific misconceptions that CAS invites. Every answer gives reasoning, never a bare yes/no.

Before you start, one vocabulary reminder so nothing below uses a term you haven't earned:

Related deep material lives in Lock-Free Data Structures, Spinlocks and Mutexes, Memory Barriers, ABA Problem Solutions, Cache Coherence Protocols and Memory Consistency Models.

True or false — justify

A CAS that returns false means the memory was corrupted.

False. false just means the value at the address was not what you expected — a totally normal, healthy signal that another thread got there first. You simply re-read and retry.

A single CAS instruction can never fail if there is only one thread running.

True in effect — with no other writer, the value you read stays put, so expected always still matches when CAS runs. Failure requires a concurrent writer (or an interrupt/signal handler touching the same word).

CAS is atomic, therefore an increment built from read + CAS is also atomic.

False. The CAS itself is atomic, but the surrounding read-compute-CAS sequence is not one indivisible unit — that's exactly why we wrap it in a retry loop. Another thread may change the value between our read and our CAS.

If CAS sees the expected value, then nothing changed since I read it.

False — this is the ABA trap. The value could have gone A → B → A. CAS compares the bits, not the history, so it cannot tell a value that never moved from one that came back.

A lock-free algorithm guarantees every thread finishes in bounded time.

False. Lock-free only guarantees some thread makes progress system-wide; an individual unlucky thread can retry its CAS forever. The stronger property "every thread finishes" is called wait-free.

Test-And-Set and CAS are equally powerful for building arbitrary synchronization.

False. Test-And-Set can build a lock, but CAS is universal (Turing-complete for synchronization): you can implement any atomic object from CAS, which is not true of Test-And-Set alone.

Load-Link/Store-Conditional (LL/SC) solves the ABA problem for free.

True in spirit — SC fails if any write touched the reserved address, even A → B → A, because the reservation is broken by the intervening writes, not by a value comparison. (Caveat: real LL/SC may also fail spuriously on cache-line events.)

The LOCK bus prefix and cache-line locking give the same performance.

False. Bus locking freezes all memory traffic system-wide; cache locking (via MESI/MOESI) freezes only one cache line, so unrelated work continues.

A successful CAS with memory_order_relaxed still orders surrounding loads and stores.

False. relaxed guarantees atomicity of the swap but imposes no ordering on nearby memory operations — see Memory Barriers. Other threads may see your surrounding writes in a surprising order.

Spot the error

while (CAS(addr, old, new)); — what's wrong with this retry loop?

The condition is inverted. CAS returns true on success, so this loops while succeeding and stops on failure — the opposite of intent. It should be while (!CAS(...)).

In atomic_increment, a coder moves old_val = *counter; outside the loop to "save a read". Why is that a bug?

On a failed CAS the old_val is stale — that's the whole reason we retry. Reading once outside the loop means every retry uses the same wrong expected, so CAS keeps failing forever (or worse, spins livelocked).

Lock-free push: someone writes new_node->next = stack_top; once before a loop that only retries the CAS. Why is that wrong?

new_node->next must be re-linked to the current top on every retry. If another thread pushed in between, next points at a stale top and the CAS-then-succeed installs a broken chain that drops nodes.

CAS(&top, A, B) succeeds in a pop, so we return A safely. What did the author forget?

They forgot that A may have been freed and recycled (ABA). The pointer value A matching says nothing about whether A->next is still valid, so B may be garbage. Needs a version tag or hazard pointer.

A programmer uses a 32-bit version counter on a busy 64-thread server "so it never wraps". Where's the flaw?

A 32-bit counter can wrap in seconds under heavy contention, re-creating the exact {ptr, version} pair and reopening the ABA hole. Use a wide-enough counter (often 64-bit paired with a 64-bit pointer via double-width CAS).

fetch_and_add returns new_val after the CAS loop. What's the mistake?

Fetch-And-Add must return the value before the addition. Returning new_val returns the post-increment value, breaking callers who rely on the old value (e.g. claiming a unique array index).

Why questions

Why do we compute new_val outside the atomic CAS instead of inside a locked region?

Because the heavy arithmetic can run concurrently and cheaply; the CAS only needs to validate and commit. This shrinks the atomic footprint to a single compare-and-swap, minimising cache-line contention.

Why does a CAS loop naturally handle contention without any explicit lock?

Each thread optimistically prepares an update and commits only if the world hasn't changed. Losers simply re-read reality and try again, so contention becomes retries rather than blocking — the essence of lock-free design.

Why is CAS called the "universal" atomic primitive?

From CAS alone you can construct any atomic operation — Fetch-And-Add, Swap, locks, queues, whole data structures — by wrapping the read-compute step in a CAS retry loop. No other single primitive with a finite consensus number matches it.

Why do CAS operations need attached memory-ordering semantics at all?

Because CPUs reorder independent loads/stores for speed. Without acquire/release/seq_cst tags, another thread could see your published pointer before the data it points to, exposing half-built state — see Memory Consistency Models.

Why can heavy CAS contention actually be slower than a mutex?

Under fierce contention many threads burn cycles retrying failed CAS loops, and each attempt bounces the cache line between cores. A mutex that parks losers can waste less energy and cache traffic.

Why does LL/SC "detect interference and retry" instead of locking?

LL sets a reservation on the address; SC commits only if that reservation is still intact. Interference merely breaks the reservation and fails the SC — no other core is ever blocked, so it scales better than bus locking.

Edge cases

What happens if two threads run CAS on the same location at literally the same instant?

The hardware serialises them: exactly one wins and its CAS returns true; the other sees the now-changed value and returns false. There is never a tie — that's what atomic means.

What does CAS do when expected equals the value but new also equals it (swap a value with itself)?

It succeeds and writes the same bits back — a no-op store. Harmless for the value, but note it still counts as a "write" that can break another thread's LL/SC reservation and bump a cache line to Modified state.

Is a push onto an empty stack (stack_top == NULL) a special case that breaks the CAS loop?

No. old_top is simply NULL, new_node->next = NULL, and CAS(&stack_top, NULL, new_node) installs the first node normally. The NULL case is handled by the same code with no branch.

If a thread is preempted for a full second inside a CAS retry loop, is correctness ever violated?

No — correctness holds; only that thread's progress stalls. When it resumes it re-reads the current value and retries. This is why lock-free guarantees system-wide progress but not per-thread timing.

Can Fetch-And-Add with delta = 0 ever be useful?

Yes — it becomes an atomic read of the current value that also participates in the memory-ordering fence, letting you sample a counter with the same ordering guarantees as a real update.

Recall One-line self-check before you leave

If CAS returns true, does that prove nothing changed since I read? ::: No — it only proves the value matched; the object's identity or history (ABA) is not verified.