Atomic operations and CAS: Question bank — Hinglish deep dive

6.1.9 · D5 · Hardware › Parallelism & Multicore › Atomic operations and CAS

Yeh ek self-test page hai. Har line ek question ::: answer reveal hai. Answer ko cover karo, usse zor se argue karo, phir check karo. Goal facts memorise karna nahi hai balki un specific misconceptions ko khatam karna hai jo CAS invite karta hai. Har answer mein reasoning diya gaya hai, sirf haan/na nahi.

Shuru karne se pehle, ek vocabulary reminder taaki neeche koi aisa term use na ho jo tumne abhi earn nahi kiya:

Related deep material yahan hai: Lock-Free Data Structures, Spinlocks and Mutexes, Memory Barriers, ABA Problem Solutions, Cache Coherence Protocols aur Memory Consistency Models.

True or false — justify karo

CAS jo false return karta hai uska matlab memory corrupt ho gayi.

False. false ka sirf itna matlab hai ki address par value woh nahi thi jo tum expect kar rahe the — yeh bilkul normal, healthy signal hai ki doosra thread pehle pahunch gaya. Bas re-read karo aur retry karo.

Ek single CAS instruction kabhi fail nahi ho sakta agar sirf ek thread chal raha ho.

Effect mein True — koi doosra writer nahi hoga toh tumhara padha hua value wahi rehta hai, isliye expected hamesha CAS run hone par match karta hai. Failure ke liye concurrent writer chahiye (ya koi interrupt/signal handler jo same word ko touch kare).

CAS atomic hai, isliye read + CAS se bana increment bhi atomic hai.

False. CAS khud atomic hai, lekin aas-paas ka read-compute-CAS sequence ek indivisible unit nahi hai — isliye hum ise retry loop mein wrap karte hain. Doosra thread hamari read aur CAS ke beech value badal sakta hai.

Agar CAS expected value dekhta hai, toh jabse maine padha tab se kuch nahi badla.

False — yeh ABA trap hai. Value A → B → A ho sakti thi. CAS bits compare karta hai, history nahi, isliye woh ek value jo kabhi nahi hili aur ek jo wापस aayi, dono mein fark nahi bata sakta.

Lock-free algorithm guarantee karta hai ki har thread bounded time mein khatam hoga.

False. Lock-free sirf guarantee karta hai ki koi thread system-wide progress karega; ek individually unlucky thread apna CAS forever retry karta reh sakta hai. Yeh stronger property "har thread khatam hoga" ko wait-free kehte hain.

Test-And-Set aur CAS arbitrary synchronization banane ke liye equally powerful hain.

False. Test-And-Set ek lock bana sakta hai, lekin CAS universal hai (synchronization ke liye Turing-complete): tum CAS se koi bhi atomic object implement kar sakte ho, jo sirf Test-And-Set se possible nahi hai.

Load-Link/Store-Conditional (LL/SC) ABA problem ko free mein solve karta hai.

Spirit mein True — SC fail hota hai agar koi bhi write reserved address ko touch kare, chahe A → B → A hi kyun na ho, kyunki reservation value comparison se nahi balki beech mein aayi writes se toot jaati hai. (Caveat: real LL/SC spuriously bhi fail ho sakta hai cache-line events par.)

LOCK bus prefix aur cache-line locking same performance dete hain.

False. Bus locking saari memory traffic ko system-wide freeze karta hai; cache locking (MESI/MOESI ke through) sirf ek cache line ko freeze karta hai, isliye unrelated kaam jaari rehta hai.

memory_order_relaxed ke saath successful CAS phir bhi aas-paas ke loads aur stores ko order karta hai.

False. relaxed swap ki atomicity guarantee karta hai lekin nearby memory operations par koi ordering impose nahi karta — Memory Barriers dekho. Doosre threads tumhari surrounding writes ko ajeeb order mein dekh sakte hain.

Error dhundo

while (CAS(addr, old, new)); — is retry loop mein kya galat hai?

Condition ulti hai. CAS success par true return karta hai, toh yeh succeeding hote hue loop karta hai aur failure par rukta hai — intent ka ulta. Hona chahiye while (!CAS(...)).

atomic_increment mein, ek coder old_val = *counter; ko loop ke bahar move karta hai "ek read bachane ke liye". Yeh bug kyun hai?

Failed CAS par old_val stale ho jaata hai — yahi reason hai ki hum retry karte hain. Loop ke bahar ek baar padhne ka matlab hai ki har retry same galat expected use karti hai, toh CAS hamesha fail karta rehta hai (ya worse, spin livelocked ho jaata hai).

Lock-free push: koi new_node->next = stack_top; ek baar loop se pehle likhta hai jo sirf CAS retry karta hai. Yeh galat kyun hai?

new_node->next ko har retry par current top ke saath re-link karna padta hai. Agar kisi doosre thread ne beech mein push kiya, toh next stale top ko point karta hai aur CAS-then-succeed ek broken chain install karta hai jo nodes drop kar deta hai.

CAS(&top, A, B) ek pop mein succeed karta hai, toh hum A safely return karte hain. Author kya bhool gaya?

Woh bhool gaya ki A free aur recycle ho chuka ho sakta hai (ABA). Pointer value A ka match karna yeh nahi kehta ki A->next abhi bhi valid hai, toh B garbage ho sakta hai. Version tag ya hazard pointer chahiye.

Ek programmer ek busy 64-thread server par 32-bit version counter use karta hai "taaki yeh kabhi wrap na ho". Flaw kahan hai?

32-bit counter heavy contention mein seconds mein wrap kar sakta hai, exactly wahi {ptr, version} pair dobara create karke aur ABA hole phir se khol ke. Kaafi wide counter use karo (aksar 64-bit pointer ke saath 64-bit, double-width CAS ke through).

fetch_and_add CAS loop ke baad new_val return karta hai. Galti kya hai?

Fetch-And-Add ko woh value return karni chahiye jo addition se pehle thi. new_val return karna post-increment value return karta hai, un callers ko tod ke jo purani value par rely karte hain (jaise ek unique array index claim karna).

Why questions

Hum new_val ko CAS ke bahar kyun compute karte hain ek locked region ke andar nahi?

Kyunki heavy arithmetic concurrently aur cheaply chal sakti hai; CAS ko sirf validate aur commit karna hai. Isse atomic footprint ek single compare-and-swap tak chhota ho jaata hai, cache-line contention minimize karte hue.

CAS loop naturally contention ko bina kisi explicit lock ke kyun handle karta hai?

Har thread optimistically ek update prepare karta hai aur commit karta hai sirf tabhi jab duniya nahi badli. Jo haare woh simply reality re-read karte hain aur dobara try karte hain, toh contention blocking ke bajaye retries ban jaati hai — yahi lock-free design ka essence hai.

CAS ko "universal" atomic primitive kyun kehte hain?

Sirf CAS se tum koi bhi atomic operation construct kar sakte ho — Fetch-And-Add, Swap, locks, queues, poore data structures — read-compute step ko CAS retry loop mein wrap karke. Koi doosra single primitive finite consensus number ke saath isse match nahi karta.

CAS operations ko attached memory-ordering semantics ki zaroorat kyun hai?

Kyunki CPUs independent loads/stores ko speed ke liye reorder karte hain. acquire/release/seq_cst tags ke bina, doosra thread tumhara published pointer us data se pehle dekh sakta hai jise woh point karta hai, half-built state expose karte hue — Memory Consistency Models dekho.

Heavy CAS contention actually ek mutex se slower kyun ho sakta hai?

Fierce contention mein bahut saare threads failed CAS loops retry karne mein cycles burn karte hain, aur har attempt cache line ko cores ke beech bounce karta hai. Ek mutex jo losers ko park karta hai woh kam energy aur cache traffic waste kar sakta hai.

LL/SC "interference detect karta hai aur retry karta hai" lock karne ke bajaye kyun?

LL address par reservation set karta hai; SC sirf tabhi commit karta hai jab woh reservation intact ho. Interference sirf reservation todta hai aur SC fail karta hai — koi doosra core kabhi block nahi hota, toh yeh bus locking se better scale karta hai.

Edge cases

Kya hota hai agar do threads literally ek hi instant par same location par CAS chalayein?

Hardware unhe serialize karta hai: exactly ek jeetता hai aur uska CAS true return karta hai; doosra ab-changed value dekhta hai aur false return karta hai. Kabhi tie nahi hota — yahi atomic ka matlab hai.

CAS kya karta hai jab expected value se equal ho lekin new bhi us se equal ho (value ko khud se swap karo)?

Yeh succeed karta hai aur same bits wापस likhta hai — ek no-op store. Value ke liye harmless, lekin note karo ki yeh abhi bhi ek "write" count hota hai jo doosre thread ki LL/SC reservation tod sakta hai aur cache line ko Modified state mein bump kar sakta hai.

Kya ek empty stack par push (stack_top == NULL) ek special case hai jo CAS loop todta hai?

Nahi. old_top simply NULL hai, new_node->next = NULL hai, aur CAS(&stack_top, NULL, new_node) pehla node normally install karta hai. NULL case same code se bina kisi branch ke handle ho jaata hai.

Agar ek thread CAS retry loop ke andar poore ek second ke liye preempted ho jaaye, kya correctness kabhi violate hoti hai?

Nahi — correctness hold karti hai; sirf us thread ki progress ruk jaati hai. Resume hone par woh current value re-read karta hai aur retry karta hai. Isliye lock-free system-wide progress guarantee karta hai lekin per-thread timing nahi.

Kya delta = 0 ke saath Fetch-And-Add kabhi useful ho sakta hai?

Haan — yeh current value ka atomic read ban jaata hai jo memory-ordering fence mein bhi participate karta hai, tumhe ek counter ko same ordering guarantees ke saath sample karne deta hai jaise ek real update.

Recall Jaane se pehle ek-line self-check

Agar CAS true return karta hai, kya yeh prove karta hai ki jabse maine padha tab se kuch nahi badla? ::: Nahi — yeh sirf prove karta hai ki value match ki; object ki identity ya history (ABA) verify nahi hoti.