Atomic Operations & CAS Loops — Progress Guarantees
Atomics are indivisible read-modify-write on one word. CAS loops build lock-free algorithms and accidental spinlocks. This page is the operations, the retry shape, and the progress words.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does compare-and-swap do?
Answer
If the word still equals the expected value, store the desired value and report success. Otherwise leave it and report the mismatch.
L2
Why must the function inside the loop be pure?
Answer
A failed CAS retries. Side effects that assumed success, including I/O, run twice or not at all.
L3
Is fetch-add wait-free?
Answer
When it is one hardware RMW with bounded latency, treat it as wait-free for practical purposes. Cache-line contention still delays it.
L4
Why is a CAS loop usually not wait-free?
Answer
One thread can lose every attempt while others keep succeeding. The system makes progress. That thread may starve.
L5
What is compare_exchange_weak allowed to do?
Answer
Fail spuriously on some hardware, especially LL/SC machines. The loop must retry. Use strong when a spurious failure is hard to tell from a real one.
L6
Is a mutex implemented with a CAS still a lock?
Answer
The fast path is a CAS. The slow path parks. If a thread can wait on the holder, the algorithm is blocking, even though the first instruction was atomic.
L7
What do you do when the CAS fail rate climbs?
Answer
Pause, exponential backoff with jitter, shard the word, or fall back to a mutex. A tighter spin makes the cache line worse.
Failure modes
Side effect before a successful CAS
The thread sends the RPC, then loses the CAS, then retries and sends it again.
Spin with no backoff
Failing CAS loops keep the line exclusive-invalid. Latency and CPU both climb.
Weak CAS treated as a logic failure
A spurious failure aborts the operation instead of retrying, and a correct update is dropped.
Calling the fast path lock-free
The CAS misses and the code takes a mutex. Progress is now blocking. The docs still say lock-free.
Misconceptions
CAS is wait-free because the instruction is one instruction.
The instruction is atomic. The loop is not bounded for each thread. Fetch-add is the usual wait-free case.
Two threads cannot livelock a CAS.
Lock-free promises that some thread succeeds, not that a given thread does. Backoff is how you keep the promise kind.
LL/SC removes ABA.
It can build CAS, and it can fail spuriously. ABA is about reusing the bits the compare looks at. That is the structures page.
Interviewer traps
Implementing a Michael-Scott queue when the question was the CAS loop.
Write load, compute, CAS, retry. Point at the structures page for the queue.
Saying the algorithm is lock-free because no mutex appears in the snippet.
Ask what a failed CAS implies. If the answer is 'we wait,' it is blocking.
Design scenario
Same prompt for every reader.
Requirements
Tickets must be unique. The state word must not run a side effect twice. A hot state word must back off or fall back instead of spinning forever.
Traffic / scale
Ticket increments are the common path. The state word is contended in bursts of tens of threads.
Latency
Ticket issue should stay one RMW. State transitions may take a short park under the burst.
Consistency
A ticket is issued once. A transition runs its effect only after the CAS that commits it.
Availability
A stalled thread must not freeze ticket issue. It may stall only the state it was trying to claim.
Failure assumptions
- The state CAS fails most of the time during the burst.
- Someone will put a network call between the load and the CAS.
- The hardware is allowed to fail a weak CAS spuriously.
Constraints
- Do not hold a lock while issuing tickets.
- Do not claim the state machine is wait-free.
Prompt
A process keeps a monotonic ticket counter and a small state word that several workers CAS from empty to busy. Under a load test the ticket counter is fine and the state word burns a core.
API
Which operation is fetch-add, and which is a CAS loop?
Data
What is computed before the CAS, and why is it safe to recompute?
Architecture
After how many failures do you park, and who still makes progress?
Which RMW to reach for
Prefer
Fetch-add for a counter, CAS for a protocol
If the new value is old plus a delta, use the hardware RMW. If the new value depends on a check, CAS and be ready to retry.
- Fetch-add returns the previous ticket, which callers usually need.
- CAS publishes only when the expected word is still there.
- Both are one word. Neither updates two fields.
Alternative
Load, add, store, and hope
The gap between the load and the store is where the other thread commits. Both stores write the same sum.
- Each half can be atomic and the increment is still lost.
- A lock around the pair works and is not lock-free.
- A CAS loop around the pair is the atomic version of the same idea.
The only CAS loop shape to memorize
Retry is the algorithm. The work before a successful CAS must be disposable.
- 1
Load the current word
That value is the expected input. Do not keep a copy from before you decided to try. - 2
Compute the next value with no side effects
No I/O, no unlock of something else, no message send. You may run this twice. - 3
CAS expected to next
Success means you published. Failure means another thread published. Read again. - 4
Back off if failure is the common case
A pause, jittered backoff, a shard, or a mutex. A tighter loop is not a strategy.
Overview
Atomics give you an indivisible update of a machine word. The set you should be able to map across languages:
| Operation | Meaning | Typical use |
|---|---|---|
| Load / store | Atomic read or write of the word | Flags and pointers, with an order |
| Exchange | Write the new value, return the old | Hand off a pointer |
| Compare-and-swap | Store only if the word still equals expected | Protocols, try-lock, stacks |
| Fetch-add / sub | Add and return the previous value | Counters, ticket locks |
| Fetch-or / and / xor | Bitwise RMW | Flags packed in one word |
The same idea shows up as AtomicInteger and AtomicReference in Java, std::atomic in C++, atomic.Int64 and CompareAndSwap in Go, AtomicUsize in Rust, and Atomics.compareExchange on a shared typed array in JavaScript. The memory order on each call is the next page. This page is the operation and the progress claim.
The loop
current = atomic.load()
next = f(current) # pure; safe if this attempt loses
if CAS(current -> next): # success
done
else:
retry or abort # someone else committedf must be safe to recompute. If you send a message between the load and the CAS, a lost race sends it twice. Do the side effect after the successful CAS, or make it idempotent and accept the retry.
A CAS loop is lock-free when a failing CAS implies that another thread succeeded at the same operation. It is not wait-free if one thread can lose forever. It is blocking if the failure path waits on a lock.
Decisions
- 1
Load the current word
- nextCompute next, no side effects
- 2
Compute next, no side effects
- nextCAS expected to next?
- ?
CAS expected to next?
- YesThis attempt published
- NoSomeone else won. Retry
- 4
This attempt published
- 5
Someone else won. Retry
Lesson map
Atomic Operations & CAS Loops — Progress Guarantees
Atomics are indivisible read-modify-write on one word. CAS loops build lock-free algorithms and accidental spinlocks. This page is the operations, the retry shape, and the progress words.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["Load the current word"] b["Compute next, no side effects"] c["CAS expected to next?"] d["This attempt published"] a -->|Load the current word| b b -->|Compute next, no side effects| c c -->|Yes| d
Progress
| Class | Promise | What it means in practice |
|---|---|---|
| Wait-free | Every thread finishes in bounded steps | Hardware fetch-add. Rare for a whole structure |
| Lock-free | Some thread finishes in finite steps | A CAS loop where failure means another success |
| Obstruction-free | A thread finishes if the others pause | Weaker. Uncommon in production libraries |
| Blocking | A thread may wait forever for a holder | Mutex and condition variable |
Flow
- 1
Wait-free: every thread bounded
- nextLock-free: some thread progresses
- 2
Lock-free: some thread progresses
- nextObstruction-free: progress if alone
- 3
Obstruction-free: progress if alone
- nextBlocking: may wait on a lock
- 4
Blocking: may wait on a lock
Fetch-add on hardware that implements it as one RMW is treated as wait-free. It can still wait on a cache line. That delay is contention, not a lock. A CAS loop that keeps missing is lock-free only while those misses are other successes. Two threads can in theory fail each other forever. Practical code adds backoff. Lock-free does not mean fair.
Weak CAS, LL/SC, and the mutex fast path
compare_exchange_weak may fail even when the word matches, because some machines implement CAS with load-linked / store-conditional and the reservation can clear. The loop retries. compare_exchange_strong hides that. Use strong when you cannot tell a spurious miss from a real one, and weak inside a loop that retries anyway.
ARM's LL/SC does not solve ABA. ABA is about the bits meaning a new era. That story is lock-free structures.
Many mutexes CAS an atomic flag on the fast path and park with a futex on the slow path. That CAS does not make the mutex lock-free. A thread that misses the flag can wait for the holder. It is a blocking lock with an atomic fast path.
Contention
Blind spinning burns the core and makes the line bounce harder.
- Pause.
pause/yield/ the language's spin hint. - Exponential backoff with jitter. Sleep grows. Do not synchronize the sleepers.
- Shard. Per-core counters, merged later, instead of one hot word.
- Fall back to a lock. A few CAS attempts, then the mutex. That hybrid is when locks win, and it is no longer a lock-free claim.
Sandbox
The Python type is a lock in spirit only so the CAS rule is visible on one thread: a second CAS with a stale expected value fails, and fetch-add retries until it commits. The TypeScript snippet is the same rule without a shared buffer.
ExpectedThe counter reaches 100. The stale CAS returns false and leaves 2.
Press Run. Snippets must be self-contained — no network, files, or native modules.
ExpectedThe split increment loses an update. The CAS-shaped counter keeps both.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
Is fetch-add wait-free?
Answer
When the machine does it as one RMW, yes for practical purposes: every caller finishes in a bounded number of its own instructions. The cache line can still be slow. A software retry loop around a load and a CAS is not that instruction.
Why return the old value from fetch-add?
Answer
Callers need the ticket or the slot they were given, not only the new total. A CAS loop needs the same observed value so the next attempt computes from fresh bits.
Can a CAS loop livelock?
Answer
Lock-free means the system makes progress, not that your thread does. Two threads can keep invalidating each other. Backoff and sharding are how you avoid living in that corner. Wait-free would bound your thread too.
Is a try-lock built from CAS a lock-free algorithm?
Answer
The successful fast path does not wait. If the failure path parks on a futex until the holder unlocks, threads can block. Call it a mutex. Do not put it in a lock-free proof.
What belongs inside the loop?
Answer
A pure function of the observed word. Allocation you can abandon is sometimes acceptable. A network call is not, unless the call is idempotent and you meant to risk a retry.
Weak or strong CAS?
Answer
Weak inside a retry loop, because a spurious failure just spins again. Strong when you will treat failure as "the value changed" and take a different path. LL/SC hardware is why weak exists.
Does a successful CAS establish a memory order by itself?
Answer
The instruction is atomic. The order you pass (relaxed, acquire, release, acq_rel, seq_cst) is a separate argument. A relaxed CAS on a flag does not publish a payload. That is the next page.
When is CAS the wrong tool?
Answer
When the update spans two words, when the thread must sleep, when the fail rate is high and a mutex would park, or when the team wanted a counter and fetch-add would do. Multi-word updates need a lock, a redesign, or hardware that actually has a double-word CAS you have measured.
Pitfalls
- Sending work before the CAS commits.
- Treating a spurious weak failure as a permanent no.
- Advertising lock-free for a function that takes a mutex on the slow path.
- Spinning harder when the line is already hot.
- Starting a queue implementation before you can say the progress class. The queue is the next lesson after ordering, on lock-free structures.
Write a counter with fetch-add and the same counter with a CAS loop. Then move a "charge the customer" step to just before the CAS and explain the double charge. Put it after the successful CAS and explain the crash window that remains.
Go Deeper
- Java AtomicInteger and
compareAndSeton the same types. - C++ std::atomic, including weak and strong compare-exchange.
- Rust Ordering and Go sync/atomic.
- LLVM's atomics guide for what the hardware actually does with the loop.
- Herlihy and Shavit, The Art of Multiprocessor Programming, for consensus numbers. Use a copy you own. The structures we ship are still the reviewed ones.
Next: Memory ordering.