std - atomic — lock-free operations: Question bank

5.2.26 · D5 · Coding › C++ Programming › std - atomic — lock-free operations

Picture 1 — race window (kyun plain `x++` counts kho deta hai)

Neeche wali figure ek timeline hai: time left se right flow karta hai, har thread ke liye ek row hai. Red overlap band dekho — yahi woh "race window" hai jahan dono threads ne ek hi value load kar li hai jab tak kisi ne bhi store nahi kiya.

Figure — std - atomic — lock-free operations

Picture 2 — acquire/release ek one-way gate ki tarah

Yeh figure dikhata hai ki kyun memory order matter karta hai. Har thread ke paas operations ka ek ordered stack hai; arrows dikhate hain ki compiler/CPU ko allowed hain kaunse reorderings (green = slide karne ke liye allowed, red = gate se blocked).

True ya false — justify karo

Kisi variable ko std::atomic<int> mark karna statement a = a + 1; ko ek single atomic step bana deta hai.

False. a + 1 ek atomic load hai, phir a = ... ek alag atomic store hai — do operations ke beech ek gap hai jahan koi doosra thread ghus sakta hai (bilkul Picture 1 ka race window). Ek indivisible read-modify-write ke liye a.fetch_add(1) ya ++a use karo.

std::atomic hamesha lock lene se bachta hai.

False. Lock-free hardware instructions sirf un operand sizes ke liye exist karti hain jo CPU ek baar mein handle kar sake (typically pointer/word tak, kabhi kabhi double-word via CMPXCHG16B). Kisi std::atomic<BigStruct> ke liye, maan lo 40 bytes ka, koi single instruction nahi hai jo use atomically swap kar sake, isliye library ek internal mutex chhupa leti hai. Sirf woh types jahan is_always_lock_free true ho (ya is_lock_free() runtime par true return kare) lock-free guaranteed hain.

Ek lock-free algorithm guarantee karta hai ki har thread progress karta hai.

False. Lock-free guarantee karta hai ki system-wide koi na koi thread progress kare; ek individual thread starve ho sakta hai, uska CAS har baar fail ho sakta hai kyunki tez threads value ko badle jaate hain. Woh stronger property jahan har thread bounded steps mein finish ho wait-free kehlaati hai.

Heavy contention mein ek lock-free counter hamesha mutex-protected counter se better hota hai.

False. Ek CAS loop kai baar spin kar sakta hai jab bahut saare threads collide karein, aur har retry ek cache line ko re-fetch karta hai jo cores ke beech bounce ho rahi hai — CPU jalata hai. High contention par ek mutex (jo waiters ko spin karne ki jagah park karta hai) actually jeet sakta hai — hamesha measure karo.

memory_order_relaxed kisi operation ki atomicity ko kamzor karta hai.

False. Relaxed operation ko fully atomic rakhta hai (koi torn ya lost values nahi); yeh sirf doosri memory locations ke relative ordering guarantees chhod deta hai. Counting abhi bhi correct rahti hai.

Atomic operations ka default memory order relaxed hai.

False. Default memory_order_seq_cst (sequentially consistent) hai — sabse safe aur sabse slow. Aapko relaxed mein opt in karna padta hai.

compare_exchange_weak buggy hai kyunki yeh fail kar sakta hai jab values match karti hain.

False. Uski spurious failure intentional hai: kuch CPUs par (jaise ARM ka load-linked/store-conditional pair) store-conditional fail kar sakta hai agar cache line sirf touch hui ho, aur re-check force karna extra cost lagata. Spurious failure allow karna compiler ko sasta single attempt emit karne deta hai, isliye weak ek retry loop ke andar rehna chahiye.

Ek release store akele do threads ko synchronize karta hai.

False. Synchronization ko ek pair chahiye: ek release store jo publish kare aur doosre thread par ek matching acquire load jo same value read kare (Picture 2 mein diagonal edge). Ek half akele koi happens-before edge nahi banata.

memory_order_consume sirf acquire ka ek sasta synonym hai.

False. consume sirf un operations ko order karta hai jo loaded value par data-dependent hain (jaise abhi load kiye pointer ko dereference karna), na ki acquire ki tarah baad ke sabhi reads/writes. Yeh weakly-ordered CPUs par pointer-chasing ke liye tha, lekin ise sahi se specify karna itna mushkil hai ki current compilers ise acquire tak promote karte hain, isliye aaj practical mein isse koi speedup nahi milta.

Do threads jo ek plain int par counter++ karte hain hamesha correct total denge, bas slowly.

False. Plain int increments apne load–add–store steps mein interleave ho sakte hain (Picture 1), isliye updates silently lost ho jaate hain — final total aksar expected se kam hota hai, sirf late nahi. Yeh formally undefined behaviour bhi hai.

is_lock_free() aur is_always_lock_free ek hi cheez ka matlab hai.

False (subtly). is_always_lock_free us platform par us type ke liye ek compile-time constant hai; is_lock_free() ek specific object par runtime check hai, jo over-aligned ya unusual instances ke liye matter kar sakta hai.

Error dhundo

std::atomic<int> a{0};
a = a + 1;   // "atomic increment"

::: Comment jhooth bolta hai. Yeh a ka ek load hai plus a mein ek alag store, inke beech ek race window ke saath (Picture 1). a.fetch_add(1) ya ++a se replace karo.

std::atomic<bool> ready{false};
int data = 0;
// producer
ready.store(true, std::memory_order_relaxed);
data = 42;

::: Do bugs hain: publish relaxed use karta hai (koi ordering nahi, isliye consumer ready==true dekh sakta hai data==42 se pehle), aur data = 42 flag ke baad likha gaya hai. Flag ek release store hona chahiye jo data write ke baad rakha jaye.

Node* n = new Node{v, head.load()};
head.compare_exchange_weak(n->next, n);   // no loop

::: compare_exchange_weak spuriously fail kar sakta hai aur real contention par bhi fail kar sakta hai, isliye ek single call silently push nahi kar sakta. Ise while(!head.compare_exchange_weak(n->next, n)){} mein wrap karna zaroori hai.

std::atomic<int> a{0};
if (a.compare_exchange_strong(expected, 5)) { /* ... */ }
// expected was never initialized

::: expected ko call se pehle us value se seed karna zaroori hai jo aap sochte ho a mein hai. Uninitialized hone par, compare meaningless hai; aur failure par CAS expected ko a ki current value se overwrite kar deta hai, jise phir aapko use karna hota hai.

std::atomic<int> x{0}, y{0};
// thread A
x.fetch_add(1, std::memory_order_relaxed);
y.fetch_add(1, std::memory_order_relaxed);
// thread B expects: if it sees y==1 then x==1

::: relaxed ke saath, threads ke beech do atomics ke beech koi ordering nahi hai — B y==1 observe kar sakta hai jab bhi x==0 dekh raha ho. Agar B us ordering par rely karta hai, toh release/acquire (ya seq_cst) use karo.

Why questions

Kyun LOCK prefix (jaise LOCK XADD) kisi increment ko bina kisi software lock ke atomic banata hai?

Yeh cache-coherency protocol ko kehta hai ki poore load-add-store ke liye cache line ki exclusive ownership rakhe, isliye koi doosra core mid-instruction mein use read ya write nahi kar sakta — hardware khud indivisibility provide karta hai.

Kyun ek single CAS instruction koi bhi read-modify-write banane ke liye enough hai?

Kyunki aap koi bhi RMW aise express kar sakte ho: purani value read karo, nayi compute karo, aur CAS sirf tab karo jab kisi ne ise tabtak badla nahi; failure par re-read karo aur recompute karo. Yeh "optimistic" retry loop CAS ko ek universal primitive bana deta hai.

Kyun relaxed ek pure statistics counter ke liye sahi choice hai?

Aapko sirf itni chinta hai ki total correct ho, na ki woh doosre variables ke relative kaisi order kare. Atomicity (koi lost updates nahi) relaxed ke under preserve hoti hai; aap sirf woh expensive cross-variable ordering drop karte ho jo aapko chahiye nahi.

Kyun consumer ka flag-read ek acquire load hona chahiye?

Ek acquire load baad ke reads/writes ko usse pehle reorder hone se rokta hai (Picture 2 mein ceiling), isliye jab woh published value observe karta hai toh yeh guaranteed hai ki producer ne apne release store se pehle jo kuch bhi likha woh bhi dikhega.

Kyun ek release store kabhi bhi earlier writes ko uske baad "leak" nahi hone de sakta?

Ek release store ek one-way gate hai: program order mein usse pehle aane wala koi read ya write uske baad move nahi ho sakta (Picture 2 mein floor). Yahi cheez use publish karne se pehle prior writes ka "package seal" karne deti hai.

Kyun memory_order_consume kuch hardware par acquire se tez hone ka iraada tha?

Weakly-ordered CPUs par, ek full acquire ko saari following operations ko order karne ke liye ek fence chahiye, lekin consume sirf natural data-dependency chain respect karna chahta hai (CPU already ek pointer dereference ko us load se pehle reorder nahi karega jisne pointer produce kiya). Woh fence-free path intended win tha — practically undelivered kyunki compilers abhi consume ko acquire tak upgrade karte hain.

Kyun compare_exchange failure par expected ko update karta hai usse akela chhodne ki jagah?

Taaki aapke retry loop ko ek alag reload ki zaroorat na pade — current value seedha aapko expected mein wapas di jaati hai, desired value recompute karne ke liye ready.

Kyun ek lock-free stack phir bhi performance problems suffer kar sakta hai jab bhi yeh kabhi block nahi karta?

Contention CAS retries cause karta hai, aur threads jo same head pointer par hammer karte hain woh cache line ko cores ke beech bounce karate hain — yeh cache-line ping-pong (False Sharing ka cousin) cost dominate kar sakta hai.

Edge cases

Kya hota hai agar do threads ek saath CAS-loop stack par push call karein?

Ek thread ka compare_exchange succeed karta hai; doosre ka fail hota hai kyunki head badal gaya, isliye n->next naye head se refresh hota hai aur woh retry karta hai. Dono pushes eventually land ho jaate hain — koi update lost nahi hota.

Ek while(!head.compare_exchange_weak(n->next, n)){} push loop mein, kya hoga agar CPU pehli try par hi compare_exchange_weak ko spuriously fail kara de jab bhi kuch nahi badla?

Koi problem nahi. Loop simply retry karta hai; n->next (unchanged) head se refresh hota hai aur agla attempt succeed karta hai. Yahi reason hai ki weak form ek loop ke andar belong karta hai — loop spurious failures ko free mein absorb kar leta hai.

Kya std::atomic<double> fetch_add support karta hai?

C++20 mein haan (floating-point atomics add kiye gaye the); C++20 se pehle, fetch_add floating types ke liye provided nahi tha, isliye aapko ise ek CAS loop se emulate karna padta tha.

Kya is_lock_free() kisi real platform par std::atomic<int> ke liye false return kar sakta hai?

Mainstream CPUs par almost kabhi nahi — word-sized integers har jagah modern par lock-free hain. Lekin standard ise permit karta hai (imagine karo ek chota CPU bina atomic add instruction ke), isliye portable code ko ise assume nahi karna chahiye; jab matter kare tab check karo.

Kya hoga agar compare_exchange_strong mein expected a ke barabar ho lekin a briefly kisi doosri value mein badla aur wapas aa gaya?

CAS sirf current value dekhta hai, history nahi — yeh succeed karta hai kyunki value abhi match karti hai. Yeh classic ABA problem hai; isse guard karne ke liye tagged pointers ya hazard pointers chahiye.

Aapko kya ordering milti hai agar aap a.load() ko bina kisi memory-order argument ke call karein?

Aapko memory_order_seq_cst milta hai — sabse strong, ek single global total order mein participate karta hai. Correct hai lekin potentially slower than acquire agar bas wahi aapko chahiye tha.

Kya std::atomic<int> par ++a (member operator) a = a + 1 ke barabar hai?

Nahi. ++a ek single atomic fetch_add hai; a = a + 1 ek alag atomic load aur atomic store hai jiske beech ek race window hai. Operator ya fetch_add prefer karo.

Recall Page band karne se pehle ek-line self-test

"Atomic" aur "ordered" ke beech ek asli difference batao. ::: Atomic = operation indivisible hai (koi torn/lost value nahi); ordered = uske aas-paas doosri memory writes kaisi visible hoti hain. Relaxed pehla rakhta hai, doosra drop kar deta hai.

Dekho bhi: Mutex and Lock · std::thread and std::async · Memory Model (C++) · Compare-And-Swap · False Sharing