Atomic operations and CAS

6.1.9 · Hardware › Parallelism & Multicore

Koi Operation Atomic Kaise Hoti Hai?

KYUN yeh matter karta hai? Atomicity ke bina, ek value padhne aur usse wapas likhne ke beech ka time gap ek race condition window create karta hai jahan koi doosra thread interfere kar sakta hai, jisse lost updates, inconsistent state, ya data corruption hoti hai.

Hardware Atomicity Kaise Implement Karta Hai

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

• KAISE: LOCK instruction prefix CPU ko ek hardware signal assert karne par majboor karta hai jo doosre processors ko memory bus access karne se rokta hai
• KYUN slow: Poora bus lock ho jaata hai, jisse system-wide sab doosra memory traffic block ho jaata hai
• Kahan use hota hai: Purani architectures par complex operations ke liye

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

• KAISE: MESI/MOESI cache coherence protocols use karta hai. Processor cache line ko "Modified" ya "Exclusive" state mein le jaata hai, operation perform karta hai, phir change broadcast karta hai
• KYUN faster: Sirf specific cache line lock hoti hai, poora bus nahi
• Kahan use hota hai: Modern x86/ARM chips par zyaadatar atomic operations ke liye

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}$$ - **KAISE**: LL address ko monitoring ke liye mark karta hai. Agar SC se pehle koi doosra processor us address par likhta hai, toh reservation toot jaata hai aur SC fail ho jaata hai (0 return karta hai) - **KYUN elegant**: Koi locking nahi! Bas interference detect karo aur retry karo - **Kahan use hota hai**: Software mein higher-level atomics build karne ke liye ## Compare-And-Swap (CAS): Sabse Universal Atomic > [!definition] Compare-And-Swap > ==CAS== (jise Compare-And-Exchange, CMPXCHG bhi kehte hain) sabse powerful atomic primitive hai: $$\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}$$ **Pseudocode mein (atomic execution):** ``` bool CAS(int* addr, int expected, int new_value) { atomic { if (*addr == expected) { *addr = new_value; return true; } return false; } } ``` **KYUN CAS powerful hai?** Yeh ==Turing-complete for synchronization== hai — aap CAS akele se **koi bhi** doosri atomic operation (locks, semaphores, queues) build kar sakte hain! ![[6.1.09-Atomic-operations-and-CAS.png]] ## CAS se Lock-Free Structures Build Karna > [!example] Example 1: Atomic Increment > **Problem**: Ek shared counter ko locks ke bina increment karo. **Naive (BROKEN) approach:** ```c int counter = 0; // Thread karta hai: counter = counter + 1; // RACE! Teen alag-alag operations ``` **CAS-based solution:** ```c void atomic_increment(int* counter) { int old_val, new_val; do { old_val = *counter; // Current padhna new_val = old_val + 1; // Naya compute karna } while (!CAS(counter, old_val, new_val)); // Success tak loop } ``` **KYUN har step?** 1. **Current value padhna**: Hume jaanna hai ki hum kya increment kar rahe hain 2. **Naya value compute karna**: Update ko atomic operation ke bahar prepare karo (fast) 3. **CAS loop**: Swap karne ki koshish karo *sirf tab* jab koi doosre thread ne padhne ke baad se isse nahi badla - Agar CAS succeed kare → hum jeet gaye, hamara increment install ho gaya - Agar CAS fail kare → kisi aur ne `counter` modify kiya, hamara `old_val` stale hai, fresh value ke saath retry karo **Key insight**: Koi locks nahi chahiye! Loop naturally contention handle kar leta hai. > [!example] Example 2: Lock-Free Stack Push > **Problem**: Ek shared stack par push karo jo linked list ke roop mein represent hai. ```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; // Current top padhna new_node->next = old_top; // Naye node ko current top se link karna } while (!CAS(&stack_top, old_top, new_node)); } ``` **KYUN har step?** 1. **Node allocate karna**: Loop ke bahar hota hai (expensive operation) 2. **Current top padhna**: Stack state capture karo 3. **Naye node ko link karna**: Naye node ka `next` wahan point karo jise hum top samajh rahe hain 4. **CAS**: `stack_top` ko atomically update karo sirf tab jab woh abhi bhi `old_top` hai - Success → hamara node ab naya top hai - Failure → kisi doosre thread ne beech mein push kiya, updated `old_top` ke saath retry karo **CAS loop ka Visualization:** ``` 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 | **CAS se Fetch-And-Add banana:** ```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; // PURANI value return karo (add se pehle ki) } ``` **KYUN inhe derive karte hain?** Yeh dikhata hai ki CAS fundamental primitive hai. Hardware specialized versions provide karta hai performance ke liye (single instruction vs. loop). ## The ABA Problem > [!mistake] Deadly ABA Scenario > **Galat intuition**: "Agar CAS expected value dekhe, toh kuch nahi badla." **Trap yeh hai:** Value aapke read aur CAS ke beech A → B → A badal gayi. CAS succeed karta hai, lekin **structure** badal chuka hoga! **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! ``` **KYUN yeh sahi lagta hai par hai nahi:** CAS sirf pointer value check karta hai, yeh nahi ki woh *same* object hai ya nahi. Node_A recycle ho gaya tha! **Fix (Version Counter):** ```c struct Pointer { Node* ptr; uint64_t version; // Har modification par increment hota hai }; // 128-bit value par CAS: pointer AUR version dono match hone chahiye CAS(&stack_top, {old_ptr, old_ver}, {new_ptr, old_ver + 1}) ``` **KYUN yeh kaam karta hai:** Chahe pointer value A par wapas aa jaaye, version counter alag hoga, CAS fail ho jaayega. Isse ==double-width CAS== ya ==tagged pointers== kehte hain. > [!mnemonic] CAS Behavior Yaad Karna > **C**ompare: Check karo ki current wahi hai jo maine expect kiya tha > **A**nd: Sirf agar sach ho, toh agla action karo > **S**wap: Atomically naye value se replace karo **ABA ke liye**: "Always Be Aware" — Recycled pointers ke baare mein Aware raho! ## Memory Ordering Considerations > [!formula] Memory Barriers aur CAS > CAS operations ke ==memory ordering semantics== hote hain: $$\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}$$ **KYUN yeh matter karta hai?** Modern CPUs performance ke liye instructions reorder karte hain. Ordering guarantees ke bina: ```c data = 42; // Data likho ready = 1; // Flag set karo (CAS use karke) // Compiler/CPU inhe reorder kar sakta hai! ``` **KAISE CAS ordering provide karta hai:** x86 par, CAS ka implicit full barrier hota hai. ARM/RISC-V par, aap specify karte hain: ```c CAS_acquire(&ready, 0, 1); // Ensure karta hai ki 'data = 42' complete ho jaaye is line ke baad ke kisi bhi read se pehle ``` **Derivation**: CAS ek ==synchronization point== ki tarah: - **Acquire**: Jo bhi thread successfully CAS-acquire karta hai, woh un saari writes ko dekh sakta hai jo us thread ne ki thi jisne release kiya - **Release**: CAS-release se pehle ki saari writes us thread ko visible hoti hain jo acquire karta hai ## Performance Characteristics > [!example] Example 3: Contention Analysis > **Setup**: 8 threads ek counter ko 1 million baar increment kar rahe hain. | Method | Cache Misses | Total Time | Why? | |--------|-------------|----------|---| | Mutex Lock | ~8M | 2.5s | Lock serialization + context switches cause karta hai | | CAS Loop | ~500K | 0.8s | Threads locally retry karte hain, bus traffic kam | | Fetch-And-Add | ~100K | 0.2s | Single atomic instruction, minimal coherence traffic | **KYUN CAS locks se better hai:** 1. **Koi context switches nahi**: Failed CAS bas retry karta hai, thread block nahi hota 2. **Optimistic**: Kam contention assume karta hai (aksar sach hota hai) 3. **Cache-friendly**: Local cache copy par spin karta hai jab tak change detect na ho **KYUN Fetch-And-Add CAS se better hai:** - Single instruction (koi loop nahi) - Hardware-optimized path - Kam coherence traffic **KAB kya use karna hai:** - **Locks**: High contention, lambe critical sections, fairness chahiye - **CAS**: Low-medium contention, short operations, progress guarantees chahiye - **Fetch-And-Add**: Simple counter/accumulator updates > [!recall]- 12 saal ke bachche ko explain karo > Sochiye aap aur aapke dost ek video game high score board share kar rahe hain. Jab aap ek level beat karte hain, toh aap apna score add karna chahte hain. Lekin problem yeh hai: aap board dekhte hain (maano 100 points dikhata hai), apna naya score dimag mein calculate karte hain (100 + 25 = 125), lekin jab tak aap board par 125 likhte hain, aapke dost ne already 110 likh diya! Aapka 125 unka update erase kar deta hai — unke points kho jaate hain! Atomic operations ek jaadu ki marker ki tarah hain jo turant kaam karti hai. Jab aap ise use karte hain, score check karna aur naya likhna ek hi pal mein saath hota hai — koi beech mein ghus nahi sakta. Compare-And-Swap aur bhi smart hai: aap marker ko bolte hain "Sirf tab 125 likho jab board abhi bhi 100 dikhaye. Agar kisi ne isse badal diya, toh mujhe batao aur main naye number ke saath recalculate karoonga." Aap tab tak koshish karte rehte hain jab tak succeed na ho, lekin kisi ka bhi update kabhi nahi kho ta! ## Connections - [[Cache Coherence Protocols]] — MESI states efficient atomic operations enable karti hain - [[Memory Consistency Models]] — Atomic operations synchronization points ki tarah kaam karti hain - [[Spinlocks and Mutexes]] — CAS ya Test-And-Set ke upar build kiye jaate hain - [[Lock-Free Data Structures]] — CAS queues, stacks, hash tables ko locks ke bina enable karta hai - [[Thread Synchronization]] — Atomics locks se lower-level primitives provide karti hain - [[Memory Barriers]] — Atomic operations ke aas-paas ordering control karte hain - [[ABA Problem Solutions]] — Hazard pointers, epoch-based reclamation --- #flashcards/hardware Atomic operation kya hoti hai? :: Ek aisa operation jo doosre sabhi threads ke perspective se completely aur indivisibly execute hota hai, bina kisi observable intermediate state ke — ya toh woh poora complete hota hai ya hota hi nahi. Hardware atomic operations ke liye kya teen guarantees provide karta hai? ::: (1) Read-modify-write bina interruption ke hota hai, (2) Saare changes doosre threads ko simultaneously visible hote hain, (3) Operation ke dauran koi doosra processor memory location access nahi kar sakta. Atomicity ke liye cache locking bus locking se kaise alag hai? ::: Bus locking poora memory bus lock kar deta hai (saare processors block, slow), jabki cache locking sirf specific cache line ko MESI/MOESI protocols use karke lock karta hai (faster, kam interference). Compare-And-Swap (CAS) operation kya hai? ::: Ek atomic primitive jo ek memory location ko ek expected value se compare karta hai aur, agar match ho, ek naya value swap karta hai, success/failure return karta hai — sab ek indivisible operation ke roop mein. CAS ko synchronization ke liye Turing-complete kyun maana jaata hai? ::: Kyunki koi bhi doosri synchronization primitive (locks, semaphores, barriers) sirf CAS ko foundation ke roop mein use karke build ki ja sakti hai. CAS-based atomic increment pattern likhiye :: `do { old = *addr; new = old + 1; } while (!CAS(addr, old, new));` — Current padhte, naya compute karte, aur success tak CAS karte hue loop karo. ABA problem kya hai? ::: Jab ek value thread ke read aur CAS ke beech A se B se wapas A ho jaati hai, toh CAS succeed kar leta hai yeh sochte hue ki kuch nahi badla, lekin underlying structure modify ho chuka hoga (jaise pointer recycle ho gaya). ABA problem ko kaise solve karte hain? ::: Pointer ke saath ek version counter use karo double-width CAS mein, har modification par version increment karo taaki chahe pointer A par wapas aaye, version alag hoga. Fetch-And-Add kya hai? ::: Ek atomic operation jo atomically ek value padhta hai, delta add karta hai, wapas likhta hai, aur original value return karta hai — `do { old = *addr; new = old + delta; } while (!CAS(addr, old, new)); return old;` ke roop mein implement hota hai CAS kya memory ordering provide karta hai? ::: CAS acquire/release semantics ke saath ek synchronization point ki tarah kaam karta hai: acquire baad ke operations ko CAS se pehle move hone se rokta hai, release pehle ke operations ko CAS ke baad move hone se rokta hai. Low contention mein CAS mutex locks se faster kyun hota hai? ::: CAS context switches ya kernel involvement ke bina locally spin karta hai, optimistically kam contention assume karta hai, jabki locks mein hamesha overhead hota hai aur access serialize hota hai. Load-Link/Store-Conditional kya hai? ::: ARM/RISC-V par ek atomic pattern jahan LL ek value load karta hai aur reservation set karta hai, phir SC sirf tab store karta hai jab koi doosra processor us address par nahi likha (reservation intact hai), warna fail ho jaata hai. ## 🖼️ 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] ```