5.2.27 · D3 · HinglishC++ Programming

Worked examplesMemory model — happens-before, acquire-release semantics

4,569 words21 min read↑ Read in English

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

Yeh page Memory model — happens-before, acquire-release semantics ka exercise dojo hai. Hum theory dobara nahi padhayenge — hum isko stress-test karenge. Neeche har worked example ko scenario matrix ke ek cell se tag kiya gaya hai, taaki aap dekh sako ki humne koi case miss nahi kiya.


Scenario matrix

Cell Axis being tested Kya galat ho sakta hai Example
C1 release + acquire, load reads the value kuch nahi — yeh hold karna chahiye Ex 1
C2 relaxed store, load reads value koi hb edge nahi → stale data Ex 2
C3 acquire load galat (purani) value padhta hai handshake kabhi fire nahi hota Ex 3
C4 transitive chain A→B→C across 3 threads hb transitive hai Ex 4
C5 RMW fetch_add with acq_rel (ek counter) ordering + atomicity saath mein Ex 5
C6 acq_rel vs seq_cst — IRIW / two-flag case acq_rel ke under koi global order nahi Ex 6
C7 degenerate: mixed order (release store, relaxed load) aadha handshake = koi edge nahi Ex 7
C8 real-world word problem (double-checked init) correct lock-free singleton Ex 8
C9 exam twist: legally reorder karo, kya assert phir bhi hold karta hai? allowed reorderings ke baare mein reason karo Ex 9
C10 consume + dependency-ordered-before tricky data-dependency ordering Ex 10
C11 degenerate: zero threads racing (single thread) + self-store jab model ordering free mein deta hai Ex 11
C12 standalone seq_cst fence + plain seq_cst store/load fence as a movable barrier Ex 12

Prerequisite reading agar koi cell confuse kare: std-atomic and atomic operations, Sequential consistency vs weak memory models, Out-of-order execution and store buffers (CPU), std-atomic_thread_fence.

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

Example 1 — woh handshake jo zaroor succeed karna chahiye (Cell C1)

Forecast: aage padhne se pehle guess karo yes/no — aur woh ek condition bolo jo ise hold karati hai.

  1. Events list karo. (1) data = 42, (2) ready.store(...,release), (3) ready.load(...,acquire) returns true, (4) assert(data==42). Yeh step kyun? Jab tak aap har evaluation ko naam nahi dete, tab tak ordering ke baare mein reason nahi kar sakte.
  2. Intra-thread edges. (1) sequenced-before (2); (3) sequenced-before (4). Yeh step kyun? Program order yeh ek thread ke andar free mein deta hai.
  3. Cross-thread edge. Store (2) ek release hai; load (3) ek acquire hai aur usne exactly woh value true padhi jo (2) ne likhi thi. To (2) synchronizes-with (3). Yeh step kyun? Thread boundaries cross karne ka yahi ek tarika hai — aur iske liye value handshake chahiye.
  4. Transitive closure. (1) →hb (2) →hb (3) →hb (4). Isliye (1) happens-before (4). Yeh step kyun? Happens-before transitive hai, to chain write ko read se link karti hai.
  5. Visibility guarantee apply karo. hb ⇒ (4) un sab side-effects ko dekhta hai jo (1) se pehle sequenced hain +(1) khud bhi, to data == 42. Yeh step kyun? Yahi payoff hai — visibility guarantee exactly wahi hai jo ek hb edge kharidta hai.

Verify: Edge tab hi exist karta hai jab acquire ne released value padhi ho. Kyunki while loop tab hi exit karta hai jab true padhta hai, condition satisfied. Assert holds — hamesha. ✓ (figure s01 dekho, green arrow synchronizes-with edge hai).


Example 2 — relaxed store data ko poison karta hai (Cell C2)

Forecast: kya ready ko atomic banana pehle se data ko protect kar deta hai?

  1. Synchronizes-with edge check karo. relaxed sirf atomicity + modification-order consistency deta hai — koi acquire/release nahi. To (2) nahi synchronizes-with (3). Yeh step kyun? Bina release/acquire tags ke, koi cross-thread edge banana possible nahi.
  2. Koi aur edge dhundho. (1)→(2) aur (3)→(4) sirf intra-thread hain; threads ke across koi chain nahi. Yeh step kyun? Koi edge nahi ⇒ koi happens-before nahi ⇒ koi guarantee nahi.
  3. data ke liye consequence. data non-atomic hai, dono threads use touch karti hain, kam se kam ek write karta hai, aur koi hb ordering nahi → yeh ek data race hai = UB (undefined behavior). Yeh step kyun? Data race ki definition mein exactly yahi teen ingredients hain, aur yahan hum missing edge ko formal verdict mein convert kar rahe hain.

Verify: x86 par bhi (ek strong model) compiler data = 42 ko relaxed store ke baad reorder kar sakta hai, ya T2 ek cached stale data padh sakta hai. Assert fire ho sakta hai — aur formally poora program UB hai. ✗ Safe nahi. (Figure s03 dekho: s01 jaisi hi picture lekin green edge erase hai kyunki relaxed koi synchronizes-with nahi banata.)

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

Example 3 — acquire galat value padhta hai (Cell C3)

Forecast: kya kaunsi value hum padhte hain iska matter hai, ya koi bhi acquire enough hai?

  1. Woh release identify karo jisne 2 likha. Value 2 doosre store(2, release) se aayi, jo data = 7 ke sequenced-after hai. Yeh step kyun? Handshake us store se attach hota hai jisne woh value produce ki jo humne padhi.
  2. Edge banao. Acquire ne 2 padha; woh value ek release store se aayi; aur data = 7 us store se pehle sequenced hai. To hb chain: data=7 →hb store(2) →hb load()==2 →hb assert. Yeh step kyun? Same C1 logic, bas value 2 ke store par anchored hai.
  3. Edge case — 0 padhna. Agar acquire load 0 return karta hai (initial value, kisi release ne nahi likha), to if false hai, koi assert nahi chalta. Agar 1 padha, to data=7 store(1) se pehle bhi ordered hai. Har value jo load legally return kar sakta hai jo kisi release se aayi ho, data=7 ko order karti hai. Yeh step kyun? Hum har woh value cover karte hain jo load legally return kar sakta hai, sirf happy path nahi.

Verify: {1, 2} mein observe kiye gaye kisi bhi value ke liye data = 7 write assert se pehle happens; 0 ke liye assert skip ho jaata hai. To assert kabhi fire nahi hoga. ✓ (figure s04: do release-stores ki timeline aur acquire kaunsi value latch karta hai.)

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

Example 4 — teen threads ke across transitive chain (Cell C4)

Forecast: T3 ne T1 se directly baat nahi ki — kya phir bhi T1 ki write dekh sakta hai?

  1. Edge 1 (T1→T2). T1 ka release of a synchronizes-with T2 ka acquire of a. To x=1 →hb T2 ke acquire ke baad ki sab cheezein. Yeh step kyun? Pehla handshake T1 ka kaam T2 ko publish karta hai.
  2. T2 ka local order. x=1 (inherited) →hb T2 ka y=2 →hb T2 ka b.store(1,release). Yeh step kyun? Sequenced-before T2 ke andar x ki visibility ko aage chain karta hai.
  3. Edge 2 (T2→T3). T2 ka release of b synchronizes-with T3 ka acquire of b. Yeh step kyun? Doosra handshake T2 ke release set ko publish karta hai, jisme ab T1 ka x=1 bhi hai.
  4. Transitivity. x=1 →hb y=2 →hb b.store →hb b.load →hb assert. To T3 dono dekhta hai. Yeh step kyun? Happens-before ek transitive closure hai, to do handshakes chain karne se T1 ki write T3 tak pahunch jaati hai.

Verify: happens-before ek transitive closure hai — x=1 ki visibility T2 ke release se ride karti hai bhale hi T3 ne T1 se directly synchronize nahi kiya. Assert holds. ✓ (figure s02 do arrows ko ek chain mein join hote dikhata hai.)

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

Example 5 — fetch_add ke saath ek atomic counter (Cell C5)

Forecast: pehle final count predict karo.

  1. RMW ki atomicity. fetch_add ek read-modify-write (RMW) hai: yeh read, add, write ek indivisible step mein karta hai, to koi increment lost nahi hota. Yeh step kyun? Sahi count ke liye atomicity chahiye, ordering nahi.
  2. Count. 4 threads × 250 increments = . Koi lost updates nahi. Yeh step kyun? Atomic RMW guarantee karta hai ki har +1 exactly ek baar apply ho.
  3. acq_rel kyun (relaxed nahi)? Agar har increment bhi woh data publish karta hai jo doosre threads padhte hain, to acq_rel har RMW ko ek saath acquire (pehle ka kaam dekho) aur release (apna khud publish karo) banata hai. Agar yeh sirf ek pure counter hai bina payload ke, to relaxed kaafi hoga aur faster bhi hoga. Yeh step kyun? Woh sabse weak tag choose karo jo aapki actually zaroori ordering de.

Verify: Final counter == 1000. RMW ka modification order ek atomic ke liye single total order hai, to sum exact hai chahe interleaving kaisi bhi ho. ✓ (figure s05: chaar threads +1 operations ek modification order mein funnel karte hue.)

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

Example 6 — do flags, do readers: acq_rel global nahi hai (Cell C6)

Forecast: kya do observers do independent writes ke order par disagree kar sakte hain?

  1. acq_rel ka koi single global order nahi. Acquire/release sirf memory ko ek synchronizes-with chain ke along order karta hai. x aur y independent atomics hain — inhe link karne wali koi chain nahi. Yeh step kyun? Guarantee chain-local hai, global nahi.
  2. Bura outcome legal hai. T3 y propagate hone se pehle x observe kar sakta hai; T4 x propagate hone se pehle y observe kar sakta hai. Result a=1,b=0 aur c=1,d=0 acq_rel ke under allowed hai — do readers store order par disagree karte hain. Yeh step kyun? Yahi defining IRIW inconsistency hai (dekho Sequential consistency vs weak memory models).
  3. seq_cst ke under. Sab seq_cst operations ek global total order share karte hain. Dono readers agree karna zaroori hai, to a=1,b=0 aur c=1,d=0 dono saath nahi ho sakte. Yeh step kyun? seq_cst extra fences ke saath ek global order kharidta hai.

Verify: Contradiction test — agar koi global order exist karta, to ya x ka store y se pehle hota ya vice versa; T3 aur T4 agree karte. acq_rel aisa koi order nahi deta → disagreement possible (result: allowed). seq_cst → forbidden. ✓ (figure s06: do readers do windows se dekh rahe hain aur flags ko opposite orders mein uthte dekh rahe hain.)

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

Example 7 — aadha handshake (Cell C7, degenerate)

Forecast: kya ek strong side pair ko rescue kar leti hai?

  1. Synchronizes-with ko DONO sides chahiye. Ek synchronizes-with edge ke liye ek release store aur ek acquire (ya stronger) load chahiye jo use padhe. Yahan load relaxed hai. Yeh step kyun? Handshake symmetric hai — ek release bina acquire ke koi partner nahi rakhta.
  2. Koi edge nahi. Release store + relaxed load ⇒ koi synchronizes-with nahi ⇒ data=5 aur assert ke beech koi hb nahi. Yeh step kyun? Missing acquire = T2 mein missing upward barrier; T2 ka data ka read flag read se upar hoist ho sakta hai.
  3. Consequence. data par data race (non-atomic, unordered) → UB, assert fire ho sakta hai. Yeh step kyun? Same teen-ingredient data-race verdict jaise Example 2, broken handshake par apply kiya.

Verify: Dono endpoints par ordering hona chahiye. release + relaxed = broken handshake. Safe nahi. ✗ (Symmetric failure: relaxed store + acquire load equally broken hai.)


Example 8 — real-world: lock-free lazy singleton (Cell C8)

Forecast: kya koi reader non-null pointer lekin half-built object dekh sakta hai?

  1. Publish. Winning thread w construct karta hai (sab writes), phir ek compare-exchange (ek RMW) karta hai release success order ke saath. Construction release se pehle sequenced hai. Yeh step kyun? Release constructor writes ko store ke neeche rakhta hai — "downward fence".
  2. Subscribe. Koi bhi doosra thread instance ko acquire ke saath padhta hai. Winner ka pointer padhna ek synchronizes-with edge banata hai. Yeh step kyun? Acquire baad ke field accesses ko load se upar rakhta hai — woh constructor ki writes dekhte hain.
  3. hb chain. construct(w) →hb CAS release →hb load acquire →hb use fields. Reader ek complete object dekhta hai. Yeh step kyun? Writer ke constructor se reader ke usage tak transitivity har constructor write cross karati hai.
  4. Failure branch. CAS failure par (expected winner ke pointer ke saath relaxed failure order se overwrite hua), hum w delete karte hain aur winner ka fully-published pointer paane ke liye re-load(acquire) karte hain. Yeh step kyun? Relaxed failure order theek hai kyunki subsequent acquire load real edge deta hai, to hum kabhi unpublished pointer return nahi karte.

Verify: Har returned pointer ek release CAS se publish hua aur ek acquire load se padha gaya ⇒ constructor se use tak hb ⇒ kabhi half-built Widget nahi. ✓ (Yeh exactly Lock-free programming patterns init idiom hai; ek mutex same edge aur simply deta.)


Forecast: in do moves mein se kaun sa release actually forbid karta hai?

  1. Release kya forbid karta hai. release (B) ek downward fence hai: koi bhi memory op jo iske sequenced-before hai woh iske neeche move nahi ho sakta. Yeh baad ke ops ke upar aane ke baare mein kuch nahi kehta. Yeh step kyun? Mnemonic yaad karo: "Release keeps the past below." Kisi bhi move ko judge karne se pehle humein barrier ki direction pata honi chahiye.
  2. (A) ko (B) ke neeche move karo? (A) release (B) se sequenced-before hai. (A) ko (B) ke neeche sink karna ek earlier write ko publish point se aage nikal jaane dega, to ek consumer ka acquire b==1 padhega lekin a nahi dekhega. Forbidden. Yeh step kyun? Yahi exact guarantee hai jiske liye release exist karta hai — tag ka poora point yahi hai.
  3. (C) ko (B) se upar move karo? (C) release ke sequenced-after hai. Release baad ke ops ko upar aane se nahi rokta. To (C) ko (B) se upar hoist karna legal hai (assuming (C) khud koi ordering nahi rakhta). Yeh step kyun? Release one-directional hai (sirf downward); future kuch bhi pin nahi karta.
  4. (C) ko bhi pin karne ka tarika. Agar (C) ko bhi (B) ke neeche rakhna hota, to aap (B) ko seq_cst banate ya ek atomic_thread_fence insert karte, one-way gate ko two-way barrier mein convert karte. Yeh step kyun? Reader ko fix dikhata hai jab default asymmetry enough nahi hoti.

Verify: Release = sirf downward barrier. Move (A)-below-(B): illegal. Move (C)-above-(B): legal. Yeh parent ke mnemonic "R↓ A↑" se match karta hai. ✓ (Dekho Compiler reordering and the as-if rule aur std-atomic_thread_fence.)


Example 10 — memory_order_consume aur data dependencies (Cell C10)

Forecast: kya acquire se weaker tag phir bhi us data ko protect karta hai jo loaded pointer ke through reach hota hai?

  1. Consume kya promise karta hai. Ek consume load ek dependency-ordered-before edge banata hai: sirf woh operations jo loaded value se data dependency carry karte hain woh matching release ke baad ordered hain — sab baad ke operations nahi (yeh acquire karta hai). Yeh step kyun? Narrower guarantee ko jaanna zaroori hai use trust karne se pehle. consume ⊂ acquire in reach.
  2. Kya *p dependency-carrying hai? p directly consume load se aayi, aur *p p ke through padhta hai. To dereference p par ek dependency carry karta hai. Yeh step kyun? Guarantee sirf dependency-carrying reads cover karti hai; hum confirm karte hain ki *p qualify karta hai.
  3. (Dependency) chain banao. payload=99 →hb ptr.store(release) →(dependency-ordered-before)→ *p. Kyunki *p loaded pointer par depend karta hai, yeh release ke prior work ko dekhta hai. Yeh step kyun? Same publish/subscribe shape jaise acquire, lekin edge sirf dependency-linked reads tak pahunchta hai.
  4. Consume kahan FAIL karta. Ek unrelated read assert(payload == 99) jo p ke through nahi pahuncha woh koi dependency carry nahi karta, to consume use order nahi karta — acquire ke saath karta. Yahi trap hai. Yeh step kyun? Woh case cover karo jahan weak tag protect nahi karta, taaki reader surprise na ho.

Verify: *p == 99 holds (dependency-carried). payload ka sibling read directly consume se order nahi hoga. Practice mein zyaadatar compilers consume ko acquire mein promote karte hain; standard iske use ko discourage bhi karta hai — prefer karo acquire jab tak profiling demand na kare. ✓


Example 11 — degenerate inputs: single thread aur self-store (Cell C11)

Forecast: relaxed ne Example 2 ko break kiya — kya yeh inhe bhi break karta hai?

  1. Case A — koi doosra thread nahi matlab koi race nahi. Ek single thread ke saath, evaluations ka har pair sequenced-before (program order) se connected hai. Disagree karne wala koi doosra thread nahi. Yeh step kyun? Data race ke liye do threads chahiye; ek thread ke saath "no ordering" precondition kabhi meet nahi ho sakta.
  2. Case A conclusion. data = 42 load se pehle sequenced hai, jo assert se pehle sequenced hai. hb sirf sequenced-before se hold karta hai — relaxed yahan irrelevant hai. Assert holds. Yeh step kyun? Dikhata hai ki jab koi cross-thread visibility question nahi hai to tag choice matter nahi karta.
  3. Case B — apni most recent write padhna. Ek thread ke andar, ek atomic ka load us latest value ko observe karna chahiye jo us thread ne store kiya (sequenced-before + modification-order consistency). To v.load() returns 7. Yeh step kyun? relaxed bhi ek single location ke liye modification-order consistency guarantee karta hai; ek thread apne khud ke store ke peeche kabhi nahi padhta.
  4. Example 2 se contrast. Example 2 ka danger ek doosra thread data padh raha tha. Doosra thread hata do (ya apni khud ki write padho) aur danger khatam. Yeh step kyun? Exactly woh precondition pin karo jo change hui.

Verify: Case A assert holds (single-thread sequenced-before). Case B assert holds (ek thread apna latest store relaxed ke under bhi padhta hai). Dono safe, koi UB nahi. ✓


Example 12 — ek standalone seq_cst fence (Cell C12)

Forecast: kya ek alag fence wahi edge bana sakta hai jo release/acquire tag banata?

  1. Fence-to-fence synchronization rule. Ek release fence relaxed store se pehle, ek acquire fence relaxed load ke baad ke saath paired (jo woh store padhta hai), ek synchronizes-with edge banata hai — bilkul store/load ko directly tag karne jaisa. Yeh step kyun? Yeh standalone-fence equivalent hai Example 1 ka; aapko pata hona chahiye ki yeh rule exist karta hai.
  2. Release fence. data = 77 release fence se sequenced-before hai, jo relaxed store se sequenced-before hai. Fence data=77 ko store ke neeche sink hone se rokta hai. Yeh step kyun? Fence woh downward barrier supply karta hai jo relaxed store mein nahi hai.
  3. Acquire fence. Relaxed load true padhta hai; acquire fence (load ke sequenced-after) data ka read upar hoist hone se rokta hai. Yeh step kyun? Fence woh upward barrier supply karta hai jo relaxed load mein nahi hai.
  4. hb chain. data=77 →hb release-fence →hb (relaxed store jo relaxed load ne padha) →hb acquire-fence →hb assert. Edge complete. Yeh step kyun? Same message-passing chain jaise C1, sirf barriers fences mein detach hain.

Verify: Do fences exactly C1 acquire-release edge reconstruct karte hain, to data == 77 hamesha hold karta hai. ✓ Ek plain seq_cst store/load pair (koi alag fence nahi) aur bhi strong guarantee deta — ek global total order — lekin is ek-flag message pass ke liye fence pair kaafi hai. Dekho std-atomic_thread_fence.


Recall Matrix par self-quiz

Kaun sa cell "release store + relaxed load" hai? ::: C7 — ek broken half-handshake, koi hb edge nahi, UB. Kya do acquire-loads do independent release-stores ke order par disagree kar sakte hain? ::: Haan, acq_rel ke under (Cell C6, IRIW); seq_cst ke under nahi. Kya ek acquire-load jo initial value padhta hai (kisi release ka nahi) ek edge banata hai? ::: Nahi — usne koi release observe nahi kiya, to koi synchronizes-with nahi (Cell C3 edge case). 4 threads × 250 fetch_add(1) ka final value? ::: 1000, atomic RMW se guaranteed (Cell C5). Kya happens-before ek aisi thread ke across jump karta hai jisne sirf flag relay kiya? ::: Haan — yeh transitive hai (Cell C4). consume kya order karta hai jo plain program order nahi karta, aur acquire ke compare mein kya MISS karta hai? ::: Yeh un reads ko order karta hai jo loaded value se data dependency carry karte hain; yeh unrelated (non-dependent) baad ke reads ko order nahi karta jo acquire karta (Cell C10). Kya ek relaxed store/load ek single-threaded program ko break karta hai? ::: Nahi — ek thread sequenced-before se fully ordered hai; race ke liye do threads chahiye (Cell C11). Kya ek standalone release fence + acquire fence tagged store/load replace kar sakta hai? ::: Haan — fence-to-fence rule same synchronizes-with edge banata hai (Cell C12).