Memory model — happens-before, acquire-release semantics: Exercises

5.2.27 · D4 · Coding › C++ Programming › Memory model — happens-before, acquire-release semantics

Intuition Is page ko kaise use karein

Har problem ek chota sa C++ scenario batata hai. Pehle khud try karo, phir collapsible solution kholo. Hum ladder pe upar chadh rahe hain: L1 Recognition (rule ka naam batao) → L2 Application (output predict karo) → L3 Analysis (bug dhundho) → L4 Synthesis (fix karo / design karo) → L5 Mastery (edge cases aur proofs). Sab kuch parent note pe build karta hai; agar koi term unfamiliar lage, pehle woh padh lo.

Is page par notation convention: code blocks mein hum memory orders hamesha full likhte hain — std::memory_order_relaxed, std::memory_order_acquire, std::memory_order_release, std::memory_order_acq_rel, std::memory_order_seq_cst — taaki har snippet as-is compile ho sake. Prose mein, jab hum concept discuss karte hain na ki code likhte hain, hum relaxed / acquire / release / acq_rel / seq_cst short form use karte hain. Same values hain, bas discussion mein kam characters.

Ek chota vocabulary reminder, kyunki hum isko har solution mein use karte hain:

hb matlab happens-before — woh ordering jo visibility guarantee karta hai.
sw matlab synchronizes-with — cross-thread edge jo ek release/acquire pair banata hai.
sb matlab sequenced-before — ek hi thread ke andar plain program order.
release sequence matlab woh chain jo ek release-store se shuru hoti hai aur same atomic par read-modify-write operations se continue hoti hai (chahe relaxed wale bhi hon). Is chain ki koi bhi value padhna phir bhi original release-store ke saath synchronizes-with karta hai. Isko hum exercise L5.2 (Level 5 — Mastery, isi page par aage) mein prove karte hain — abhi bas itna jaano ki acquire-load ko exact stored value padhna zaruri nahi, is chain ki koi bhi value chalega.

Level 1 — Recognition

L1.1

Har memory_order tag ke liye batao ki woh upward barrier hai (baad ki ops ko upar jane se rokta hai), downward barrier hai (pehle ki ops ko neeche jane se rokta hai), dono, ya kuch nahi: relaxed, acquire, release, acq_rel, seq_cst.

Recall Solution

relaxed → neither (atomicity only, baaki memory ki koi ordering nahi).
acquire → upward (ek load; iske baad kuch bhi upar float nahi kar sakta).
release → downward (ek store; iske pehle kuch bhi neeche sink nahi kar sakta).
acq_rel → both (read-modify-write jaise fetch_add par use hota hai).
seq_cst → both + ek single global total order jis par saare seq_cst ops agree karte hain.

Neeche ka figure yeh draw karta hai: left side par, ek release store ek yellow "floor" line ke saath — earlier ops ke liye blue arrows uski taraf neeche point karte hain, aur ek dashed pink arrow X ke saath dikhata hai ki earlier op forbidden hai neeche sink karne se. Right side par, ek acquire load ek yellow "ceiling" line ke saath — later ops ke liye blue arrows uski taraf upar point karte hain, aur ek dashed pink X dikhata hai ki later op forbidden hai upar float karne se.

Figure — Memory model — happens-before, acquire-release semantics

Figure — Release past ke neeche ek floor hai (iske pehle kuch bhi neeche move nahi kar sakta); acquire future ke upar ek ceiling hai (iske baad kuch bhi upar move nahi kar sakta).

L1.2

Do threads ek hi non-atomic int x padhte hain. Thread A x likhta bhi hai. Unke beech koi atomic/mutex nahi hai. Is situation ke liye exact term batao aur iska C++ consequence kya hai.

Recall Solution

Yeh ek data race hai: same memory location, kam se kam ek write, koi happens-before ordering nahi. Consequence: undefined behavior — standard bilkul kuch promise nahi karta, yahan tak ki ek "reasonable" garbage value bhi nahi.

L1.3

Message-passing pattern mein, release-store ek hb edge acquire-load tak banata hai sirf ek condition ke under. Woh condition batao.

Recall Solution

Sirf tab jab acquire-load actually woh value padhta hai jo release-store ne likhi thi (ya us store ki release sequence mein koi baad ki value — woh chain jo vocabulary list mein upar define ki gayi hai aur isi page par exercise L5.2 mein prove ki jaayegi). Matching value nahi padi ⇒ koi sw edge nahi ⇒ koi hb nahi.

Level 2 — Application

L2.1

int data = 0;
std::atomic<bool> ready{false};
 
// Thread 1
data = 7;                                      // (1)
ready.store(true, std::memory_order_release);  // (2)
 
// Thread 2
while (!ready.load(std::memory_order_acquire)) // (3)
    ;
int r = data;                                  // (4)

Loop exit hone par r mein kaun si value(s) ho sakti hain? hb chain ke saath justify karo.

Recall Solution

r sirf 7 ho sakta hai.

(1) sb (2) hai — same thread, aur release (1) ko (2) ke neeche sink karne se rokta hai.
(2) sw (3) — acquire-load loop tab exit karta hai jab true padhta hai, woh value jo release-store ne likhi thi.
(3) sb (4) hai.
Transitive chain: $(1) hb (2) hb (3) hb (4)$ , toh (1) hb (4). Thread 2 data = 7 write dekhta hai. Koi aur value possible nahi hai.

L2.2

Same code lekin dono tags std::memory_order_relaxed ho jaate hain. Ab r ki possible values list karo.

Recall Solution

Koi sw edge nahi hone ke karan, data ek non-atomic location hai jise do threads koi happens-before ordering ke bina touch karte hain — yeh ek data race hai, jo undefined behavior hai. Technically, standard kuch bhi permit karta hai: program 0 padh sakta hai, 7 padh sakta hai, ek torn/garbage value padh sakta hai, crash ho sakta hai, ya poora loop optimize ho ke hat sakta hai. Intuitive, non-adversarial outcome jo log expect karte hain woh 0 ya 7 hai: relaxed sirf atomicity deta hai, toh loop ready == true dekh sakta hai data write visible hone se pehle, jisse stale 0 milta hai. Lekin yeh mat samjho ki "0 ya 7" ek guarantee hai — ek baar UB ho gaya, toh "0 ya 7" sirf sabse friendly possibility hai, koi standard-promised bound nahi.

L2.3

std::atomic<int> cnt{0};
// 3 threads each run once:
cnt.fetch_add(1, std::memory_order_relaxed);
// main thread, after joining all three:
int total = cnt.load(std::memory_order_relaxed);

Kya relaxed yahan enough hai? total kya hai? Aur kyun ek relaxed load, join() ke baad, phir bhi teenon increments dekhta hai?

Recall Solution

Haan, relaxed enough hai. total hamesha 3 hoga.

Part A — koi increment lost nahi hota (baaki memory order kiye bina bhi). Har fetch_add ek atomic read-modify-write hai. Atomicity aur modification-order consistency (ek single atomic ke saare writes ek total order mein hote hain jis par sab agree karte hain) guarantee karte hain ki har RMW us order mein immediately preceding value padhta hai aur ek add karta hai. Same atomic par teen RMWs isliye 1, 2, 3 values produce karte hain kisi order mein — koi doosre ko overwrite nahi kar sakta. Humein yahan doosri memory ki koi ordering chahiye nahi, toh relaxed sahi aur sabse sasta hai.

Part B — kyun final relaxed load teenon dekhta hai (join() hb chain). Load relaxed hai, toh apne aap se iske paas koi acquire barrier nahi hai. Jo hamein bachata hai woh hai std::thread::join(): standard specify karta hai ki ek thread ki completion us join() ke return ke saath synchronizes-with hoti hai jo uski wait karta hai. Yeh ek genuine sw edge hai — same kind ka edge jo acquire/release banata hai, lekin join() se free mein milta hai. Ek worker thread T1 ke liye trace karo:

T1 mein cnt.fetch_add(1) T1 ke execution ke end se sb hai (program order — yeh last cheez hai jo T1 karta hai).
T1 ka end main mein T1.join() ke return ke saath sw karta hai (upar wala join rule).
T1.join() ka return main mein cnt.load(...) se sb hai (main mein program order — hum load se pehle join karte hain).
Transitivity: fetch_add (T1) hb load (main). T2 aur T3 ke liye same argument.

Toh teenon increments load se pehle happen-before karte hain, aur visibility guarantee ke karan load unhe observe karta hai → 3. Load par relaxed tag irrelevant hai kyunki join() ne pehle se hi ordering provide kar di — yeh exactly wahi "kaun se do events ko ordering chahiye, aur kaun sa edge woh provide karta hai?" waala sawaal hai, acquire ki jagah join() ne answer diya.

Figure — teen worker threads mein se har ek relaxed fetch_add karta hai; har thread-end apne join() ke saath main mein synchronizes-with karta hai; woh sw edges (sb ke through) hb mein chain ho jaate hain, toh final relaxed load teenon increments dekhta hai = 3.

Level 3 — Analysis

L3.1

int payload = 0;
std::atomic<bool> ready{false};
 
// Producer
ready.store(true, std::memory_order_release);  // (A)
payload = 99;                                   // (B)
 
// Consumer
while (!ready.load(std::memory_order_acquire)); // (C)
use(payload);                                    // (D)

Producer ne release use kiya. Phir bhi consumer payload == 0 kyun padh sakta hai?

Recall Solution

Kyunki payload = 99 write release-store ke baad hai program order mein. Release ek downward barrier hai: woh un operations ko rokta hai jo iske pehle aate hain neeche sink karne se. Iske baad waali operations ke liye yeh kuch nahi karta. Toh (B) ko (A) publish nahi karta; consumer ka acquire (A) se pehle ki sab cheez inherit karta hai, jisme (B) nahi hai. Bug: signal data likhne se pehle raise hua. Order inverted hai. Fix: pehle payload likho, phir release karo:

payload = 99;
ready.store(true, std::memory_order_release);

L3.2

std::atomic<int> a{0}, b{0};
 
// Thread 1
a.store(1, std::memory_order_release);
int x = b.load(std::memory_order_acquire);
 
// Thread 2
b.store(1, std::memory_order_release);
int y = a.load(std::memory_order_acquire);
 
// Can x == 0 && y == 0 ?

acquire/release ke under, kya dono loads 0 padh sakte hain? seq_cst ke under?

Recall Solution

acquire/release ke under: ==haan, x == 0 && y == 0 possible hai==. Har thread ek alag atomic mein store karta hai; do threads ke beech koi value travel nahi karti, toh koi sw edge nahi banta. Acquire/release memory ko sirf ek synchronizes-with chain ke along order karta hai — yahan koi chain nahi hai, toh do stores ek doosre ke liye un-ordered appear ho sakte hain. seq_cst ke under: nahi. seq_cst saare seq_cst ops par ek single global total order S force karta hai. S mein ek store pehle hai; woh thread jiska load us store ke baad S mein aata hai use 1 dekhna hi padega. Toh dono ka 0 padhna impossible hai. Yeh Dekker / store-buffer scenario hai.

Neeche ka figure dikhata hai kyun: har thread ki store pehle apne khud ke store buffer (ek per-core queue) mein jaati hai aur globally visible nahi hoti, toh har thread doosra flag abhi bhi 0 padhta hai, jisse (0, 0) milta hai. seq_cst isko pehle ek store flush karke ek global order force karke forbid karta hai.

Figure — Do threads, do flags: acq_rel ke under har write apne store buffer mein chhupta hai, toh dono loads 0 padh sakte hain; seq_cst ek global order impose karke (0,0) forbid karta hai.

L3.3

std::atomic<int> flag{0};
int data = 0;
 
// Producer
data = 5;
flag.store(1, std::memory_order_release);
 
// Consumer
int f = flag.load(std::memory_order_relaxed);  // relaxed load!
if (f == 1) use(data);

Store release hai. Kya consumer safe hai?

Recall Solution

Nahi. Ek hb edge ke dono halve chahiye: ek release-store aur ek acquire-load jo use padhta ho. Ek relaxed load koi acquire side nahi banata, toh koi sw edge nahi banta chahe 1 bhi padhe. data isliye unordered hai — data race, UB. Fix: load ko std::memory_order_acquire karo. Ek release bina matching acquire ke aise hai jaise ek flag raise karo jise koi dekhne ki ijazat nahi.

Level 4 — Synthesis

L4.1

Ek single std::atomic<bool> use karke spinlock ka lock() aur unlock() design karo. Sahi memory orders choose karo aur har ek explain karo.

Recall Solution

std::atomic<bool> held{false};
 
void lock() {
    while (held.exchange(true, std::memory_order_acquire))
        ; // spin
}
void unlock() {
    held.store(false, std::memory_order_release);
}

lock() exchange ko acquire ke saath use karta hai: ek baar lock jeetnay par (old value false thi), acquire ek upward barrier hai toh critical section ke reads/writes lock se upar float nahi kar sakte. Yeh ek mutex mirror karta hai: acquire on lock.
unlock() release use karta hai: ek downward barrier toh saare critical-section writes held ke false hone se pehle publish ho jaate hain. Agla thread ka acquiring exchange woh false padhta hai → sw edge banta hai → humara kaam dikhta hai.

Important classification note: yeh spinlock ek blocking synchronization mechanism hai, lock-free data structure nahi. Standard definition ke under, lock-free matlab hai ki system as a whole progress karta hai chahe koi bhi thread suspended ho; ek spinlock woh fail karta hai — agar lock-holder held == true hold karte hue descheduled ho jaaye, toh har waiter forever spin karta rahega. Jo genuinely lock-free hai woh underlying atomic `exchange` primitive hai jis se humne lock banaya. Sacche lock-free algorithms ko lock-free programming patterns ke under study karo.

Common mistake L4 trap: "lock() ko release-only banao, unlock() ko acquire-only"

Kyun sahi lagta hai: English words technical ones ko invert karte hain — "I acquire a lock" sunne par lagta hai lock() par release barrier daalo, aur "I release the lock when I unlock()" sunne par lagta hai wahan acquire barrier daalo. Verbs aur barrier names opposite directions point karte hain. Sachai: barrier direction decide karta hai, English verb nahi. Acquire barrier critical section ka start protect karta hai — yeh ek upward barrier hai, toh critical section ke andar kuch bhi us point ke upar leak nahi kar sakta jahan tum ownership lete ho. Yeh exactly lock() par chahiye. Release barrier end protect karta hai — yeh ek downward barrier hai, toh saare tumhare critical-section writes lock hand off hone se pehle publish ho jaate hain. Yeh exactly unlock() par chahiye. Unhe swap karne se critical-section code dono ends se bahar leak ho jaayega, mutual exclusion ki visibility guarantee destroy ho jaayegi. Fix: "acquire on lock, release on unlock" yaad karo — rule ko barrier direction se bind karo (acquire = upward = entry protect karo; release = downward = exit protect karo), English verb se nahi.

L4.2

Message-passing pattern ko tagged atomics ki jagah fence use karke rewrite karo. Kaun sa fence kahan jaayega?

Recall Solution

int data = 0;
std::atomic<bool> ready{false};
 
// Producer
data = 42;
std::atomic_thread_fence(std::memory_order_release);  // (F1)
ready.store(true, std::memory_order_relaxed);
 
// Consumer
while (!ready.load(std::memory_order_relaxed)) ;
std::atomic_thread_fence(std::memory_order_acquire);  // (F2)
assert(data == 42);

(F1) release fence relaxed store se pehle baith ta hai: yeh data = 42 ko store se neeche sink karne se rokta hai. Store publish karta hai.
(F2) acquire fence relaxed load succeed hone ke baad baith ta hai: yeh assert(data) ko load ke upar float karne se rokta hai.
Release-fence-then-store, load-then-acquire-fence ke saath pair karta hai taaki same hb edge bane. Dekho thread fences. Yeh tagged release/acquire ke equivalent hai lekin barrier ko atomic op se decouple karta hai.

L4.3

Tumhare paas ek producer hai jo buffer fill karta hai aur size set karta hai, aur bahut saare consumers hain. Tum chahte ho ki consumers independent atomics ke across size updates ka ek consistent global order dekhen. Kaun sa memory order, aur acq_rel kyun nahi?

Recall Solution

==std::memory_order_seq_cst== use karo. acq_rel memory ko sirf ek matched store/load pair ke beech ek synchronizes-with chain ke along order karta hai. Jab tumhare paas independent atomics hain aur har thread ko ek global sequence of events par agree karna ho (L3.2 waali IRIW situation), toh acquire/release bahut weak hai — alag observers alag orders dekh sakte hain. seq_cst saare seq_cst operations cover karne wala ek single global total order S add karta hai, toh har consumer agree karta hai. Dekho sequential consistency. Cost: extra fences, usually slower.

Common mistake L4 trap: "seq_cst har jagah, bas safe rehne ke liye"

Kyun sahi lagta hai: L4.3 dikhata hai ki seq_cst global-order requirement ke liye single strong enough tag hai, toh temptation hota hai use har atomic par thok do aur sochna band karo. Sachai: seq_cst default precisely isliye hai kyunki woh safest hai, lekin woh sabse expensive bhi hai — woh global total order maintain karne ke liye extra full fences insert karta hai. Real code mein zyada tar sirf ek acquire/release pair (L4.1, L4.2) ya plain relaxed (L2.3) chahiye. Blanket seq_cst woh ordering ke liye performance throw karta hai jo tum kabhi use nahi karte. Fix: seq_cst tab reach karo sirf jab tumhe sacchi mein independent atomics ke across ek global order chahiye (IRIW / Dekker); warna woh weakest order use karo jo specifically tumhari zaruri hb edge provide kare.

Level 5 — Mastery

L5.1

Prove karo ki L2.1 mein read (4) write (1) ke saath race nahi kar sakta, yani dikhao ki hb edge unhe order karta hai, transitivity rule reference karte hue.

Recall Solution

Data race ke liye chahiye ki same location par do accesses hon, ≥1 write ho, koi hb ordering na ho. Yahan access (1) data likhta hai, access (4) data padhta hai.

(1) sb (2): Thread 1 mein program order.
(2) sw (3): release-store acquire-load dwara padha gaya jo loop exit karta hai.
(3) sb (4): Thread 2 mein program order. Happens-before sb ∪ sw ka transitive closure hai. Chain karo: (1) hb (2), (2) hb (3), (3) hb (4) ⇒ transitivity se (1) hb (4). Kyunki (1) hb (4) hai, dono conflicting accesses ordered hain, toh definition ke hisaab se koi data race nahi hai. ∎

L5.2

Release sequence mein: producer x.store(1, std::memory_order_release) karta hai, phir baad mein koi doosra thread x.fetch_add(1, std::memory_order_relaxed) karta hai jisse x == 2 ho jaata hai. Consumer x.load(std::memory_order_acquire) karta hai aur 2 padhta hai (kabhi 1 nahi dekhta). Kya woh phir bhi original release-store ke saath synchronize-with karta hai?

Recall Solution

Haan. Yeh is page ke top par vocabulary list mein promised proof hai. Rule yeh hai: ek acquire-load ek release-store ke saath synchronizes-with karta hai agar woh stored value ya us release-store ki release sequence mein koi baad ki value padhta hai. Release sequence release-store se headed hoti hai aur same atomic par read-modify-write operations (fetch_add yahan) se continue hoti hai — chahe relaxed wale bhi hon. Toh 2 padhna (jo release-store par chained RMW se produce hua) phir bhi producer ka pehle wala kaam inherit karta hai. Yahi reason hai ki RMWs aisi chains ke andar relaxed ho sakte hain.

L5.3

Degenerate case: ek program mein exactly ek thread hai. Kya memory model ki reordering kabhi single-threaded program ko out-of-order results observe kara sakti hai?

Recall Solution

Nahi. Ek single-threaded program kabhi apni khud ki reordering observe nahi kar sakta. Poora reasoning yeh hai:

Ek thread ke andar, sequenced-before har dependent access ko fully order karta hai. Program order successive evaluations ke beech sb define karta hai, aur sb exactly woh ordering hai jo language us thread ko expose karti hai.
As-if rule saari reordering constrain karta hai. Compiler aur CPU instructions reorder ya eliminate kar sakte hain, lekin sirf tab jab program ka observable behavior (I/O, volatile accesses, aur objects ki final values) strictly program order mein run karne jaisi identical ho. Dekho the as-if rule aur, hardware level par, out-of-order execution and store buffers — CPU data dependencies track karta hai aur results as if in order retire karta hai.
Isliye koi bhi reordering jo ek single thread detect kar sake woh forbidden hai. Agar A aur B ko reorder karne se yeh thread kya padhta ya output karta hai woh change ho jaata, toh yeh illegal hai; agar nahi hota, toh thread bata nahi sakta ki yeh hua. Dono cases mein thread program-order results observe karta hai.
Memory-model subtleties strictly ek cross-thread phenomenon hain. Yeh tabhi appear hote hain kyunki ek thread ka sb doosre thread mein nahi pahunchta — threads ke across koi sb edge nahi hai, toh tumhe sw edges (acquire/release ke through) haath se banane padte hain. Ek single thread ke saath synchronize karne ke liye kuch nahi hai, toh happens-before plain program order mein collapse ho jaata hai aur visibility ka poora sawaal khatam ho jaata hai.

Conclusion: reordering ek akele thread ko construction se invisible hai; memory model tabhi observable hota hai jab ek doosra thread padhta hai jo pehle ne likha.

L5.4

Counting edge case: L3.2 mein seq_cst ke under, possible (x, y) outcomes enumerate karo aur confirm karo ki (0, 0) excluded hai.

Recall Solution

Dono stores 1 likhte hain. Loads ya toh initial 0 ya store ka 1 padhte hain. Candidate pairs: (0,0), (0,1), (1,0), (1,1). seq_cst ke under chaar operations ka ek total order S hai. S mein jo bhi store last aata hai, doosra store usse pehle hai; jo thread us earliest store ke baad S mein load karta hai use 1 observe karna hi padega. Formally, kam se kam ek load 1 dekhta hai, (0,0) rule out ho jaata hai. Teen surviving outcomes (0,1), (1,0), (1,1) sabhi reachable hain. Toh exactly 3 of the 4 combinations seq_cst ke under possible hain.

Parent par wapas jaao: Memory Model — Happens-Before, Acquire-Release Semantics.