Unit 2.3 · about 3 h
242 / 324Atomic operations, compare-and-swap and memory ordering
Locks serialize contenders through the kernel; atomics let threads detect conflicts and retry in user space. This is the vocabulary behind every lock-free claim the later storage units make. It assumes programming/native-systems-literacy native-threads-atomics as background and takes it to the hardware primitive and the ordering contract.
- explain
You can now
- Explain compare-and-swap as one atomic hardware step, and write the retry loop that makes it a lock-free update.
- Use weak against strong compare-exchange correctly, and state where spurious failure is allowed.
- State what relaxed ordering does and does not guarantee, and when a counter needs nothing stronger.
Covers
- Atomic operations and compare-and-swap vocabulary
- Relaxed memory ordering beyond working vocabulary
Study, in this order
5 steps
- Test-and-set, compare-and-swap and fetch-and-addOperating Systems: Three Easy Pieces - concurrency
Sections 28.7 and 28.9 to 28.11: spin locks from test-and-set, the CAS primitive and fetch-and-add
- Compare-And-Swap (CAS)AlgoMaster Concurrency lessons
What is Compare-and-Swap; Hardware-Level Implementation (
CMPXCHG); The CAS Loop Pattern; Weak vs Strong CAS - Atomic OperationsAlgoMaster Concurrency lessons
What are Atomic Operations; Memory Ordering; Producer-Consumer Flag
Depth · Read for vocabulary; the C11 reference below is the contract.
- C11 compare-exchange and memory orderscppreference: C atomic operations
Success and failure semantics with the expected-pointer update rule; then read the linked
memory_orderpage for the six orderings and what relaxed permits - __atomic builtins for the reproduce stepGCC __atomic builtins
__atomic_compare_exchangeand__atomic_load: the expected-pointer update and the__ATOMIC_RELAXEDconstant
Focus on
- CAS compares and swaps as one hardware step (x86
CMPXCHG). Everything else, the loop, the backoff, the ABA guard, is software around it. - C11
atomic_compare_exchangewrites the observed value intoexpectedon failure. Ignoring that update turns a retry loop into an infinite loop or a lost update. - Weak compare-exchange may fail spuriously; use it only inside a retry loop. Strong is for one-shot attempts whose failure the caller treats as a definitive answer.
- Relaxed orders one location only; it does not order other memory or publish safely. A bare counter needs no more; a flag that publishes data needs release and acquire.
Reproduce closed-book
-O2 -pthread (relaxed order, weak compare-exchange): 4 times 500000 increments must total exactly 2000000, and a -fsanitize=thread build must report no races. Then replace the loop body with a plain count++ and show TSan reporting the race even when the total prints correctly. State the compiler, flags and sanitizer with the result.Traps
- A CAS success is not a lock. Two CAS loops on different locations compose no atomicity; multi-location updates still need one critical section.
- Spinning is not free. Under extreme contention the retry storm can cost more than blocking; the contention unit measures the crossover.
- A lock-backed
compareAndSethelper demonstrates the loop shape only; it adds no lock-freedom. Name which layer actually retries without blocking.
Practice
AlgoMaster: Design an Atomic Maximum With Compare-and-Swap
Implement updateAndGet as a compare-and-swap retry loop; the judge runs up to 50000 concurrent calls and requires a monotone maximum that never loses a completed proposal
Do not use a ready-made atomic max; the statement forbids it.
Self-test
-
Why does the CAS loop re-read after failure instead of retrying the same
expectedvalue?Failure means another thread changed the location, so the savedexpectedvalue is stale. C11 writes the observed value intoexpected, so the next attempt compares against current state. -
When is weak compare-exchange correct, and when must it be strong?
Weak inside a retry loop, where a spurious failure costs one more iteration. Strong for a one-shot attempt whose failure the caller treats as a definitive answer. -
A relaxed atomic counter is exact under TSan. Does relaxed also publish a message written before the increment?
No. Relaxed orders that one location only. Publication needs release on the writer and acquire on the reader. -
Where does the ABA problem bite, and why does the counter escape it?
ABA bites when a location returns to an old value between a thread's read and its CAS, so the swap succeeds on changed history, for example recycled stack nodes. The counter escapes it because addition commutes: only the value matters, not its history.
Completion criterion
Stop when
Your CAS counter totals exactly 2000000 under TSan, the atomic-max judge passes, and you can defend weak-against-strong and relaxed-against-publish choices without notes.
Mark passed, then open 2.4 Only mark this when you can do it without notes.Leads to
- 2.4 Data races, lost updates and lost wakeups A failed CAS is a detected race; an unsynchronized read-modify-write is a silent one.
- 2.8 Deterministic schedules, stress tests and contention Compare the CAS counter against the mutex counter under matched contention.
Comes after
- 2.2 Mutexes, condition variables, semaphores and barriersLocks serialize contenders; compare-and-swap retries instead. Compare the costs.
Resources for this unit
- Operating Systems: Three Easy Pieces - concurrency Read Chapters 26-33 in order: threads, thread API, locks, locked data structures, condition variables, semaphores, bugs and event-based concurrency. Write the safety and liveness invariant before reading each worked pattern.
- AlgoMaster Concurrency lessons Use the named lessons only: Processes vs Threads, Race Conditions and Critical Sections, Mutex, Condition Variables, Compare-And-Swap, Atomic Operations, Semaphores, Producer-Consumer Pattern, Bounded Buffer, Design Thread-Safe Blocking Queue, Barriers and Latches, Read-Write Locks, Coarse-grained vs Fine-grained Locking, Deadlock, Livelock, Starvation, Priority Inversion, Lost Signal/Wakeup, Spurious Wakeup, Concurrency Models and Thread Pool Pattern. Each unit names its lessons; read no other chapter for this section.
- cppreference: C atomic operations Read
atomic_compare_exchangefor success and failure semantics and the expected-pointer update rule, andmemory_orderfor the six orderings and what relaxed permits. Stop before lock-free-property macros. - GCC __atomic builtins Read
__atomic_compare_exchange,__atomic_loadand__atomic_storefor the expected-pointer update rule and the__ATOMIC_RELAXEDconstant used by the CAS reproduce step.
Also in this section
- OSTEP concurrency homework and code Use x86.py and the main, vector, condition-variable and semaphore exercises to enumerate schedules. Preserve one lost update, one deadlock and one lost wakeup as minimized tests, then repair each invariant.
- AlgoMaster Concurrency - four bounded contracts Attempt Design a Closable Bounded Queue, Design Thread-Safe Rate Limiter, Design a Deadlock-Free Two-Key Executor, Design an Atomic Maximum With Compare-and-Swap, Design Deferred Callback Executor and Design Task Scheduler with Dependencies. For each, add a changed input, a deterministic failure schedule and an independent stress test outside the platform.
- MIT 6.1810 - locks and parallelism Use Lectures 12-14 and one lock-lab exercise only after the user-space bounded queue passes. Measure the contention change and explain the invariant preserved by the revised locking scheme.
- Linux man-pages: pthreads and futex Look up the exact pthread mutex, condition variable, barrier, cancellation and timed-wait contracts plus futex(2) and pthreads(7). Read the stated pages; do not browse the whole manual.
- The Little Book of Semaphores Use the rendezvous, barrier and reader-writer puzzles as extra semaphore practice after OSTEP Chapter 31. Skip the Python event material; this section works in C with pthreads.