Atomic operations and CAS

What Makes an Operation Atomic?

WHY does this matter? Without atomicity, the time gap between reading a value and writing it back creates a race condition window where another thread can interfere, causing lost updates, inconsistent state, or data corruption.

How Hardware Implements Atomicity

1. Bus Locking (Legacy) $\text{LOCK prefix} \implies \text{exclusive bus ownership for entire operation}$

• HOW: The LOCK instruction prefix forces the CPU to assert a hardware signal that prevents other processors from accessing the memory bus
• WHY slow: Locks the entire bus, blocking all other memory traffic system-wide
• Used for: Complex operations on older architectures

2. Cache Locking (Modern) $\text{Cache line exclusive state} \implies \text{atomic operation on cached data}$

• HOW: Uses MESI/MOESI cache coherence protocols. The processor places the cache line in "Modified" or "Exclusive" state, performs the operation, then broadcasts the change
• WHY faster: Only the specific cache line is locked, not the entire bus
• Used for: Most atomic operations on modern x86/ARM chips

3. Load-Link/Store-Conditional (ARM, RISC-V)

\text{LL}(addr) &\implies \text{load value, set reservation} \\ \text{SC}(addr, new\_val) &\implies \begin{cases} \text{store succeds} & \text{if no interference} \\ \text{store fails} & \text{if reservation broken} \end{cases} \end{align}$$ - **HOW**: LL marks the address for monitoring. If any other processor writes to that address before SC, the reservation is broken and SC fails (returns 0) - **WHY elegant**: No locking! Just detect interference and retry - **Used for**: Building higher-level atomics in software ## Compare-And-Swap (CAS): The Universal Atomic > [!definition] Compare-And-Swap > ==CAS== (also called Compare-And-Exchange, CMPXCHG) is the most powerful atomic primitive: $$\text{CAS}(addr, expected, new) \implies \begin{cases} *addr \leftarrow new, & \text{return true if } *addr = expected \\ \text{no change}, & \text{return false if } *addr \neq expected \end{cases}$$ **In pseudocode (atomic execution):** ``` bool CAS(int* addr, int expected, int new_value) { atomic { if (*addr == expected) { *addr = new_value; return true; } return false; } } ``` **WHY is CAS powerful?** It's ==Turing-complete for synchronization== — you can build **any** other atomic operation (locks, semaphores, ques) from CAS alone! ![[6.1.09-Atomic-operations-and-CAS.png]] ## Building Lock-Free Structures with CAS > [!example] Example 1: Atomic Increment > **Problem**: Increment a shared counter without locks. **Naive (BROKEN) approach:** ```c int counter = 0; // Thread does: counter = counter + 1; // RACE! Three separate operations ``` **CAS-based solution:** ```c void atomic_increment(int* counter) { int old_val, new_val; do { old_val = *counter; // Read current new_val = old_val + 1; // Compute new } while (!CAS(counter, old_val, new_val)); // Loop until success } ``` **WHY each step?** 1. **Read current value**: We need to know what we're incrementing 2. **Compute new value**: Prepare the update outside the atomic operation (fast) 3. **CAS loop**: Attempt to swap *only if* no other thread changed it since we read - If CAS succeeds → we won, our increment is installed - If CAS fails → someone else modified `counter`, our `old_val` is stale, retry with fresh value **Key insight**: No locks needed! The loop naturally handles contention. > [!example] Example 2: Lock-Free Stack Push > **Problem**: Push onto a shared stack represented as a linked list. ```c struct Node { int data; Node* next; }; Node* stack_top = NULL; // Global stack head void push(int value) { Node* new_node = malloc(sizeof(Node)); new_node->data = value; Node* old_top; do { old_top = stack_top; // Read current top new_node->next = old_top; // Link new node to current top } while (!CAS(&stack_top, old_top, new_node)); } ``` **WHY each step?** 1. **Allocate node**: Done outside the loop (expensive operation) 2. **Read current top**: Capture the stack state 3. **Link new node**: Point new node's `next` to what we think is top 4. **CAS**: Atomically update `stack_top` only if it's still `old_top` - Success → our node is now the new top - Failure → another thread pushed meanwhile, retry with updated `old_top` **Visualization of CAS loop:** ``` Attempt 1: old_top = A → new_node.next = A → CAS(stack_top, A, new_node) Success if stack_top still equals A Attempt 2: old_top = B (someone pushed B!) → new_node.next = B → CAS again Success if stack_top now equals B ``` ## Common Atomic Operations > [!formula] Standard Atomic Primitives | Operation | Formula | Use Case | |-----------|---------|-------| | ==Fetch-And-Add== | $old \leftarrow *addr; \, *addr \leftarrow *addr + \Delta; \, \text{return } old$ | Counters, indices | | ==Test-And-Set== | $old \leftarrow *addr; \, *addr \leftarrow 1; \, \text{return } old$ | Spinlocks | | ==Swap== | $old \leftarrow *addr; \, *addr \leftarrow new; \, \text{return } old$ | Unconditional exchange | | ==CAS== | $\text{if } *addr = exp \text{ then } *addr \leftarrow new$ | Lock-free algorithms | **Derivation of Fetch-And-Add from CAS:** ```c 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; // Return the OLD value (before add) } ``` **WHY derive these?** Shows that CAS is the fundamental primitive. Hardware provides specialized versions for performance (single instruction vs. loop). ## The ABA Problem > [!mistake] The Deadly ABA Scenario > **Wrong intuition**: "If CAS sees the expected value, nothing changed." **The trap:** Value changed from A → B → A between your read and CAS. CAS succeds, but the **structure** may have changed! **Concrete example (lock-free stack pop):** ``` Initial: stack_top → Node_A → Node_B → NULL Thread 1: Thread 2: 1. old_top = Node_A 2. next = Node_A->next (B) [PREMPTED] 3. Pop A (stack_top = B) 4. Pop B (stack_top = NULL) 5. Push A (stack_top = A again!) 6. CAS(stack_top, A, B) Success! But A->next is stale, B was already freed! ``` **WHY this feels right but isn't:** CAS only checks the pointer value, not whether it's the *same* object. Node_A was recycled! **The fix (Version Counter):** ```c struct Pointer { Node* ptr; uint64_t version; // Incremented on every modification }; // CAS on 128-bit value: both pointer AND version must match CAS(&stack_top, {old_ptr, old_ver}, {new_ptr, old_ver + 1}) ``` **WHY this works:** Even if pointer value returns to A, the version counter will differ, CAS fails. This is called ==double-width CAS== or ==tagged pointers==. > [!mnemonic] Remembering CAS Behavior > **C**ompare: Check if current matches what I expected > **A**nd: Only if true, perform the next action > **S**wap: Replace with new value atomically **For ABA**: "Always Be Aware" — Be Aware of recycled pointers! ## Memory Ordering Considerations > [!formula] Memory Barriers and CAS > CAS operations have ==memory ordering semantics==: $$\text{CAS}_{acquire} \implies \text{loads/stores after CAS cannot move before it}$$ $$\text{CAS}_{release} \implies \text{loads/stores before CAS cannot move after it}$$ $$\text{CAS}_{seq\_cst} \implies \text{total ordering across all threads}$$ **WHY does this matter?** Modern CPUs reorder instructions for performance. Without ordering guarantees: ```c data = 42; // Write data ready = 1; // Set flag (using CAS) // Compiler/CPU might reorder these! ``` **HOW CAS provides ordering:** On x86, CAS has implicit full barrier. On ARM/RISC-V, you specify: ```c CAS_acquire(&ready, 0, 1); // Ensures'data = 42' completes before any reads after this line ``` **Derivation**: CAS as a ==synchronization point==: - **Acquire**: Any thread that successfully CAS-acquires sees all writes made by the thread that released - **Release**: All writes before CAS-release are visible to the thread that acquires ## Performance Characteristics > [!example] Example 3: Contention Analysis > **Setup**: 8 threads incrementing a counter 1 million times each. | Method | Cache Misses | Total Time | Why? | |--------|-------------|----------|---| | Mutex Lock | ~8M | 2.5s | Lock causes serialization + context switches | | CAS Loop | ~500K | 0.8s | Threads retry locally, reduced bus traffic | | Fetch-And-Add | ~100K | 0.2s | Single atomic instruction, minimal coherence traffic | **WHY CAS beats locks:** 1. **No context switches**: Failed CAS just retries, doesn't block thread 2. **Optimistic**: Assumes low contention (often true) 3. **Cache-friendly**: Spinning on local cache copy until change detected **WHY Fetch-And-Add beats CAS:** - Single instruction (no loop) - Hardware-optimized path - Less coherence traffic **WHEN to use each:** - **Locks**: High contention, long critical sections, need fairness - **CAS**: Low-medium contention, short operations, need progress guarantees - **Fetch-And-Add**: Simple counter/accumulator updates > [!recall]- Explain to a 12-year-old > Imagine you and your friends are sharing a video game high score board. When you beat a level, you want to add your score. But here's the problem: you look at the board (say it shows 100 points), calculate your new score in your head (100 + 25 = 125), but by the time you write125 on the board, your friend already wrote 110! Your125 erases their update — their points are lost! Atomic operations are like a magic marker that works instantly. When you use it, checking the score and writing the new one happen together in one blink — nobody can sneak in between. Compare-And-Swap is even smarter: you tell the marker "Only write125 if the board still shows 100. If someone changed it, tell me and I'll recalculate with the new number." You keep trying until you succeed, but nobody's update ever gets lost! ## Connections - [[Cache Coherence Protocols]] — MESI states enable efficient atomic operations - [[Memory Consistency Models]] — Atomic operations serve as synchronization points - [[Spinlocks and Mutexes]] — Built on top of CAS or Test-And-Set - [[Lock-Free Data Structures]] — CAS enables ques, stacks, hash tables without locks - [[Thread Synchronization]] — Atomics provide lower-level primitives than locks - [[Memory Barriers]] — Control ordering around atomic operations - [[ABA Problem Solutions]] — Hazard pointers, epoch-based reclamation --- #flashcards/hardware What is an atomic operation? :: An operation that executes completely and indivisibly from the perspective of all other threads, with no observable intermediate state — either it completes entirely or doesn't happen at all. What three guarantees does hardware provide for atomic operations? ::: (1) Read-modify-write happens without interruption, (2) All changes become visible to other threads simultaneously, (3) No other processor can access the memory location during the operation. How does cache locking differ from bus locking for atomicity? ::: Bus locking locks the entire memory bus (blocking all processors, slow), while cache locking only locks the specific cache line using MESI/MOESI protocols (faster, less interference). What is the Compare-And-Swap (CAS) operation? ::: An atomic primitive that compares a memory location to an expected value and, if they match, swaps in a new value, returning success/failure — all as one indivisible operation. Why is CAS considered Turing-complete for synchronization? ::: Because any other synchronization primitive (locks, semaphores, barriers) can be built using only CAS as the foundation. Write the CAS-based atomic increment pattern :: `do { old = *addr; new = old + 1; } while (!CAS(addr, old, new));` — Loop reading current, computing new, and CAS-ing until success. What is the ABA problem? ::: When a value changes from A to B to A between a thread's read and CAS, the CAS succeds thinking nothing changed, but the underlying structure may have been modified (e.g., pointer recycled). How do you solve the ABA problem? ::: Use a version counter alongside the pointer in a double-width CAS, incrementing the version on every modification so even if the pointer returns to A, the version will differ. What is Fetch-And-Add? ::: An atomic operation that atomically reads a value, adds a delta, writes back, and returns the original value — implemented as `do { old = *addr; new = old + delta; } while (!CAS(addr, old, new)); return old;` What memory ordering does CAS provide? ::: CAS acts as a synchronization point with acquire/release semantics: acquire prevents later operations from moving before CAS, release prevents earlier operations from moving after CAS. Why is CAS faster than mutex locks under low contention? ::: CAS spins locally without context switches or kernel involvement, assuming low contention optimistically, while locks always have overhead and serialize access. What is Load-Link/Store-Conditional? ::: An atomic pattern on ARM/RISC-V where LL loads a value and sets a reservation, then SC stores only if no other processor wrote to that address (reservation intact), failing otherwise. ## 🖼️ Concept Map ```mermaid flowchart TD RC[Race condition window] -->|causes| LU[Lost updates] AO[Atomic operation] -->|eliminates| RC AO -->|executes| IND[Indivisible read-modify-write] AO -->|implemented by| BL[Bus locking legacy] AO -->|implemented by| CL[Cache locking modern] AO -->|implemented by| LLSC[Load-Link Store-Conditional] BL -->|uses| LOCK[LOCK prefix locks whole bus] CL -->|uses| MESI[MESI cache coherence] LLSC -->|detects interference then| RETRY[Retry no locking] CAS[Compare-And-Swap] -->|is| UNIV[Universal atomic primitive] CAS -->|built from| AO CAS -->|swaps if| EXP[value equals expected] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > ![[audio/6.1.09-Atomic-operations-and-CAS.mp3]] ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Dekho, socho do threads ek hi counter ko padh rahe hain jiska value 10 hai. Dono usko 11 banake wapas likhte hain — tumhe 12 chahiye tha, par mila 11! Ek increment lost ho gaya. Yeh problem tab aati hai jab read, modify, aur write ke beech mein doosra thread ghus jaata hai. Isko hi hum ==race condition== kehte hain. Atomic operations yeh guarantee dete hain ki poora read-modify-write ek saath, bina beech mein rukavat ke, complete hoga — bilkul ek transaction ki tarah jo interrupt nahi ho sakta. Beech ka koi state doosre thread ko dikhta hi nahi. > > Ab hardware yeh atomicity deta kaise hai? Purane systems mein **bus locking** hota tha — LOCK prefix se poora memory bus lock ho jaata, par yeh slow hai kyunki baaki sabka traffic bhi ruk jaata. Modern chips **cache locking** use karte hain jahan sirf ek cache line lock hoti hai (MESI protocol se), toh yeh fast hai. ARM aur RISC-V mein ek elegant tareeka hai — **Load-Link/Store-Conditional**: LL address ko monitor karta hai, aur agar beech mein koi aur us address ko likh de toh SC fail ho jaata hai aur tum retry kar lete ho. Koi locking hi nahi, bas interference detect karo! > > Sabse important cheez hai **CAS (Compare-And-Swap)**. Yeh bolta hai: "Agar address pe abhi bhi wahi expected value hai jo maine socha tha, tabhi naya value likho, warna mat likho." Iski beauty yeh hai ki CAS ==synchronization ke liye Turing-complete== hai — matlab sirf CAS se tum locks, semaphores, queues, sab kuch bana sakte ho! Atomic increment ka loop dekho: tum old value padhte ho, new compute karte ho, aur CAS try karte ho — agar beech mein kisi ne badla toh CAS fail hoga aur tum wapas try karoge jab tak success na mile. Yeh why-it-matters isliye hai kyunki modern multicore programming, lock-free data structures, aur high-performance concurrent code sab CAS pe hi tike hain — bina iske reliable parallel code likhna namumkin hai.