std - atomic — lock-free operations — Hinglish notes

5.2.26 · Coding › C++ Programming

WHAT is the problem we are solving?

Worked example The classic lost-update bug

int counter = 0;                    // plain int — NOT safe
// two threads each run:
for (int i = 0; i < 100000; ++i) counter++;
// expected: 200000.  actual: often LESS.

Yeh step kyun hai (counts kyun lose hote hain)? counter++ asal mein teen machine steps hain:

counter ko ek register mein load karo
add 1
register ko wapas store karo

Thread A 5 load karta hai, Thread B 5 load karta hai, dono add karte hain → dono 6 store karte hain. Do increments, ek hi net effect. Yeh teen-step sequence ek read-modify-write (RMW) hai, aur atomics isi cheez ko indivisible banate hain.

HOW does the hardware make RMW atomic?

Woh fundamental primitive jis par baaki sab kuch bana hai woh hai Compare-And-Swap (CAS):

Formula Compare-And-Swap — the universal primitive

compare_exchange_strong(expected, desired) atomically yeh karta hai: $if (a == expected) {a \leftarrow desired; return true}$ $else {expected \leftarrow a; return false}$

Derivation of WHY CAS is enough: koi bhi RMW ek retry loop ke roop mein likha ja sakta hai:

T old = a.load();
while (!a.compare_exchange_weak(old, f(old))) { /* old updated, retry */ }

Yeh kyun kaam karta hai: CAS tab hi write karta hai jab humne use read kiya tab se a mein kisi ne bhi badlaav na kiya ho. Agar kisine kiya, toh old current value se refresh hota hai aur hum f(old) recompute karte hain. Aakhirkar ek thread jeet jaata hai → progress guaranteed hai → lock-free. Yeh hai optimistic concurrency: conflict nahi hoga assume karo, write time par verify karo.

Figure — std - atomic — lock-free operations

Memory ordering — the second guarantee

Atomicity torn values ko rokti hai. Memory order control karta hai ki atomic op ke around doosre writes kab visible hote hain.

Worked example Producer / consumer flag

std::atomic<bool> ready{false};
int data = 0;
// producer
data = 42;                              // (1) ordinary write
ready.store(true, std::memory_order_release);  // (2) publish
// consumer
while (!ready.load(std::memory_order_acquire)) {}  // (3) wait
assert(data == 42);                      // (4) guaranteed!

Step (2) release kyun hona chahiye: yeh write (1) ko pin karta hai ki woh flag dikhne se pehle ho. Step (3) acquire kyun hona chahiye: ek baar jab yeh true observe kar le, toh yeh write (1) bhi guaranteed dekh lega. In orders ke bina, data abhi bhi 0 read ho sakta tha.

Worked example: a lock-free counter

Worked example Atomic increment

std::atomic<int> counter{0};
// each thread:
for (int i = 0; i < 100000; ++i)
    counter.fetch_add(1, std::memory_order_relaxed);
// result is EXACTLY 200000.

fetch_add kyun? Yeh ek atomic RMW hai → koi lost updates nahi. relaxed yahan theek kyun hai: hume sirf count correct hone ki parwah hai, na ki isse doosre variables ke relative order karne ki. Atomicity order se independent preserve hoti hai; sirf cross-variable visibility drop hoti hai. Yeh sabse sasta correct choice hai — ek key 80/20 optimization.

Worked example Lock-free stack push (CAS loop)

struct Node { int v; Node* next; };
std::atomic<Node*> head{nullptr};
void push(int v){
    Node* n = new Node{v, head.load()};
    while(!head.compare_exchange_weak(n->next, n)) {}
}

CAS loop kyun: agar hamari load aur store ke beech kisi doosre thread ne push kiya, toh CAS fail hoga, n->next ko naye head se refresh karega, aur retry karega. Koi mutex nahi, koi blocking nahi.

Common mistake Steel-manned traps

1. "atomic poore expression ko safe banata hai." Lagta hai sahi hai kyunki a atomic hai. Lekin atomic<int> par a = a + 1; do alag atomic ops hain (pehle load phir store) — ek RMW nahi! a.fetch_add(1) ya ++a (member operator) use karo. Fix: sirf member functions / overloaded operators atomic hain, arbitrary expressions nahi.

2. "lock-free matlab wait-free / hamesha faster." Lock-free guarantee karta hai ki koi thread progress karega, har thread nahi, aur heavy contention mein ek CAS loop kai baar spin kar sakta hai. High contention mein ek mutex bhi jeet sakta hai. Fix: measure karo; lock-free low–medium contention par shine karta hai.

3. "default relaxed theek hai." Default seq_cst hai, aur relaxed woh ordering drop kar deta hai jis par tum rely karte ho. Fix: relaxed tab hi use karo jab koi doosra variable is op ki ordering par depend na karta ho.

4. compare_exchange_weak "buggy hai" kyunki yeh spuriously fail karta hai. Yeh tab bhi fail kar sakta hai jab values match karti hain (kuch CPUs par sasta) — yeh by design hai loops ke andar use ke liye. Single, non-looped checks ke liye _strong use karo.

Recall Feynman: explain to a 12-year-old

Socho ek shared piggy bank hai aur do bacche dono ek coin add kar rahe hain. Agar dono andar jhaanken ("5 coins"), har ek sochta hai "ab 6", aur dono label par 6 likhte hain — ek coin ka count gum ho gaya. Ek atomic operation ek magical haath ki tarah hai jo ek blink mein pakadta, ginata, aur update karta hai taaki beech mein koi jhaank na sake. Lock-free matlab humein bank par padlock nahi lagana (koi line mein wait nahi) — magic bank mein hi built-in hai. Aur memory order woh rule hai jo kehta hai: agar main box par ek note chhod deta hoon "main ho gaya", jo bhi woh note padhega woh sab kuch bhi dekhega jo maine andar pack kiya tha.

Flashcards

std::atomic<T> kya guarantee karta hai jo plain T nahi karta?

Operations indivisible (atomic) hain aur ek chosen memory order follow karte hain, threads ke across torn reads aur lost updates prevent hote hain.

Plain counter++ threads ke across unsafe kyun hai?

Yeh ek load–add–store sequence hai; threads steps ke beech interleave ho sakte hain aur updates lose ho sakte hain.

"lock-free" define karo.

Ek operation jo OS mutex acquire kiye bina bounded steps mein complete ho jaata hai, usually ek CPU instruction ke zariye (LOCK XADD / CMPXCHG).

compare_exchange_strong(expected, desired) kya karta hai?

Atomically: agar value==expected toh use desired set karo aur true return karo; warna current value ko expected mein load karo aur false return karo.

Arbitrary RMW ke liye CAS loop kyun use karte hain?

Yeh tab hi write karta hai jab read ke baad se kisi ne value nahi badli; failure par refresh karta hai aur retry karta hai, lock-free progress deta hai.

compare_exchange_weak aur _strong mein kya farq hai?

weak spuriously fail ho sakta hai (sasta, loops ke andar use karo); strong spuriously fail nahi hoga (single non-looped checks ke liye use karo).

Kaunsa pairing ek synchronizes-with edge banata hai?

Ek thread mein ek release store jo doosre thread mein ek acquire load ke zariye observe kiya jaaye.

memory_order_relaxed kab appropriate hai?

Jab tumhe sirf atomicity chahiye (jaise ek counter) aur koi doosra variable is op ki ordering par depend nahi karta.

Trap: kya atomic<int> a ke liye a = a + 1 atomic hai?

Nahi — yeh ek alag atomic load phir atomic store hai; a.fetch_add(1) ya ++a use karo.

Compile time par lock-freedom kaise check karte hain?

std::atomic<T>::is_always_lock_free (ya runtime par is_lock_free()).

Agar unspecified ho toh default memory order kya hai?

memory_order_seq_cst (sequentially consistent, sabse safe, sabse slow).

Connections

Mutex and Lock — lock-free atomics ka blocking alternative
Memory Model (C++) — happens-before, synchronizes-with
Cache Coherency MESI — kyun LOCK-prefixed instructions ek cache line cost karti hain
std::thread and std::async — jahaan yeh races paida hoti hain
Compare-And-Swap — lock-free data structures ke liye universal primitive
False Sharing — same cache line par atomics ka performance trap