Visual walkthrough — Memory model — happens-before, acquire-release semantics

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

Step 1 — Do threads, memory ka ek shared box

KYA HAI. Socho tumhare program ki memory ek lambi shelf of numbered boxes ki tarah hai. Har box mein ek value hoti hai. Ek thread bas ek worker hai jo shelf ke saath chalte hue boxes ko read aur write karta hai, ek instruction at a time. Hamare paas do workers hain, T1 aur T2, aur woh same shelf share karte hain.

KYUN. Isse pehle ki hum writes ki ordering ke baare mein baat karein, humein yeh picture chahiye ki kaun write karta hai aur kaun read karta hai. Baaki sab iske upar layered hai.

PICTURE. Figure mein, box data 0 se shuru hota hai aur box ready false se shuru hota hai. T1 eventually data mein ek real value dalega aur phir ready flip karega. T2 ready ko baar baar read karta rehta hai, aur sirf tab jab woh true dekhta hai, data read karta hai.

Step 2 — Program order woh order NAHI hai jo duniya dekhti hai

KYA HAI. T1 ka source code kehta hai: line (1) data = 42; phir line (2) ready = true;. Code mein yeh upar-se-neeche ka order program order kehlata hai. Lekin data mein value aur ready mein value zaruri nahi ki T2 ko usi order mein visible hon.

KYUN. Teen alag machines ko allow hai jab koi write dekhi jaati hai uski timing shuffle karne ki:

1. compiler (as-if rule) stores ko alag order mein emit kar sakta hai,
2. CPU out of order chalta hai aur writes ko store buffer mein rokta hai,
3. woh store buffer doosre cores mein tab drain hota hai jab usse theek lage.

Inme se har ek ek thread ke andar invisible hai — T1 hamesha apne khud ke writes sahi se wapas read karta hai. Shuffle sirf threads ke paar dikhta hai.

PICTURE. Figure T1 ka saaf program order left mein dikhata hai, aur messy order right mein jo T2 actually observe kar sakta hai: ready true mein flip ho sakta hai isse pehle ki data ka 42 pahuncha ho.

Step 3 — Bug, drawn: T2 ek empty box kholti hai

KYA HAI. Maano T2 ka loop ready == true read karta hai aur phir data read karta hai. Kyunki Step 2 ready ko pehle visible hone deta hai, T2 data ko tab read kar sakti hai jab woh abhi bhi 0 hai — purani value. assert(data == 42) fire hoti hai.

KYUN. T1 ke data ke write aur T2 ke data ke read ko connect karne ka koi rule nahi hai. Jab do threads same plain box ko touch karte hain, ek write karta hai, aur kuch order nahi karta, yeh by definition ek problem hai.

PICTURE. Red X: T2 flag utha hua dekhti hai lekin box abhi bhi 0 hold kar raha hai. Dashed arrow (connection jo hum chahte the) missing hai.

Step 4 — Atomic box introduce karo (abhi bhi kaafi nahi)

KYA HAI. Hum ready ko plain bool se upgrade karke std::atomic<bool> mein badal dete hain. Ek atomic box guarantee karta hai ki uske khud ke reads aur writes indivisible hain: T2 kabhi half-written ready nahi dekhega.

KYUN. Humein ek special box chahiye kyunki ordinary boxes cross-thread promises bilkul nahi dete. Atomic woh hook hai jispar hum baad mein ordering attach karenge. Lekin dhyan se note karo: atomicity akele abhi bhi data ko order nahi karti. Agar hum operations ko relaxed tag karein, hum sirf promise karte hain "no torn read of ready" — data ke baare mein kuch nahi.

PICTURE. ready box ab ek "atomic" badge pehanta hai (no torn reads), lekin data ka dashed wish-arrow relaxed ke neeche abhi bhi missing hai.

$\underset{\text{write the atomic}}{\underbrace{\text{ready.store(true,}}}\underset{\text{no ordering of other boxes}}{\underbrace{\text{ relaxed}}}\text{)}$

Term by term: store box likhta hai; value true usme land hoti hai; relaxed promise level hai — yahan, data ke baare mein koi promise nahi.

Step 5 — Release tag: store ke neeche ek one-way floor

KYA HAI. T1 ka store std::memory_order_release mein badlo. Yeh store mein ek rule add karta hai: koi bhi memory operation jo program order mein isse pehle aati hai woh iske baad nahi ja sakti. Write data = 42 ab kuch ke neeche pin hai aur release ke upar — yeh slip through nahi kar sakta.

KYUN. Hum chahte hain ki T1 data likhna finish kare isse pehle ki flag possibly visible ho jaye. release exactly woh tool hai jo kehta hai "jo maine pehle kiya woh pehle rehta hai." Yeh ek downward barrier (ek floor) hai: earlier work isse through nahi gir sakta.

PICTURE. Ek solid orange floor ready.store ke neeche baithta hai. data = 42 arrow isse bounce karta hai — yeh kabhi neeche nahi ja sakta. Yeh hai "publish the box, then raise the flag" order, ab enforce hua.

$\text{ready.store(true, }\underset{\text{floor: earlier ops cannot sink below}}{\underbrace{\text{memory\_order\_release}}}\text{)}$

Step 6 — Acquire tag: load ke upar ek one-way ceiling

KYA HAI. T2 ka load std::memory_order_acquire mein badlo. Yeh load mein ek rule add karta hai: koi bhi memory operation jo program order mein iske baad aati hai woh isse pehle nahi ja sakti. Toh T2 ka data ka read acquire-load ke neeche pin hai — yeh tab tak nahi ho sakta jab tak T2 ne ready read nahi kar liya.

KYUN. Hum chahte hain ki T2 pehle flag read kare, aur tabhi data read kare. acquire kehta hai "ek baar jab maine signal dekh liya, jo kuch bhi main baad mein karta hoon woh baad mein rehta hai." Yeh ek upward barrier (ek ceiling) hai: later work iske upar nahi uth sakta.

PICTURE. Ek solid magenta ceiling ready.load ke upar baithti hai. T2 ka read data arrow isse neeche se bounce karta hai — yeh kabhi load ke upar nahi uth sakta.

$\text{ready.load(}\underset{\text{ceiling: later ops cannot rise above}}{\underbrace{\text{memory\_order\_acquire}}}\text{)}$

Step 7 — Handshake: floor + ceiling snap together

KYA HAI. Magic tab hota hai sirf jab T2 ka acquire-load exactly woh value read karta hai jo T1 ka release-store ne likhi (true). Us instant mein ek cross-thread link banta hai — release synchronizes-with acquire.

KYUN. Synchronization clock time ke baare mein nahi hai; yeh data flow ke baare mein hai. Value true ko T1 ke box se T2 ke register mein travel karna tha. Woh journey hi handshake hai. Agar T2 ne koi doosri value read ki (ek purana false), koi journey nahi hua, toh koi link nahi bana. Parent note ne ise "must read the stored value" kaha.

PICTURE. Release ka orange floor aur acquire ka magenta ceiling ek continuous rail mein click ho jaate hain. Bounced-off data = 42 (floor ke neeche) aur read data (ceiling ke upar) ab ek rigid connection ke opposite ends par hain.

Step 8 — Happens-before mein chain karo (guarantee)

KYA HAI. Hum ab teen links ko ek guarantee mein assemble karte hain. Chaar events label karo:

• (1) data = 42
• (2) ready.store(true, release)
• (3) ready.load(acquire) == true
• (4) read data

Chain:

Symbols padhne ke liye: $\stackrel{\text{sb}}{\to }$ hai sequenced-before (ek thread ke andar order); $\stackrel{\text{sw}}{\to }$ hai synchronizes-with (cross-thread handshake).

KYUN. Happens-before define hota hai transitive closure ke roop mein: agar tum A se B tak sb aur sw arrows ke saath walk kar sako, tab A happens-before B. Arrows follow karo: $(1)\to (2)\to (3)\to (4)$, toh

$(1)\stackrel{\text{hb}}{\to }(4)⟹(4)\text{ sees the write in }(1).$

Isliye T2 ka read data 42 dekhne ki guarantee hai. Aur kyunki (1) aur (4) ab ordered hain, woh ab data race nahi hain — UB chali gayi.

PICTURE. Chaar nodes, teen colored arrows chain spell karte hue; final assert(data == 42) par ek bada green check.

Step 9 — Edge & degenerate cases (taaki koi scenario surprise na kare)

KYA HAI / KYUN, case by case:

• Case A — relaxed store ya load. Koi floor ya ceiling nahi, koi synchronizes-with nahi. Step 8 ki chain sw link par toot jaati hai. (1) nahi hota happens-before (4): assert fail ho sakti hai. (Yeh Step 4 ki picture hai, abhi bhi broken.)
• Case B — acquire purana false read karta hai. Loop condition !ready abhi bhi true hai, toh T2 looping karti rehti hai; usne abhi stored value nahi read ki, toh abhi koi handshake nahi — exactly jaise definition demand karti hai. Guarantee sirf us iteration par aati hai jo true read karta hai.
• Case C — store kabhi nahi hota (T1 (2) se pehle crash karta hai). T2 false read karte hue forever spin karta hai. Koi false guarantee kabhi nahi di jaati — tum simply assert mein kabhi enter nahi karte. Safe, agar stuck.
• Case D — do independent atomic flags, do readers (IRIW). Acquire-release har thread ko apni chain ke saath order karta hai lekin koi single global order nahi deta. Do readers do independent stores ke order par disagree kar sakte hain. Ek global order force karne ke liye tumhe seq_cst chahiye — sabse strong tag (ya ek fence).

PICTURE. Ek 2×2 grid: A (broken chain), B (still looping), C (spin forever), D (two readers disagree). Har cell dikhata hai kyun guarantee holds hoti hai ya nahi.

Ek-picture summary

Upar sab compressed: T1 data likhta hai, release floor us write ko flip ke neeche pin karta hai; value true travel karti hai (the handshake); acquire ceiling T2 ka data ka read load ke upar pin karta hai; transitive chain (1) ko (4) se pehle happen karta hai, aur box guaranteed full hai.

Flashcards