Memory consistency models: Exercises — Hinglish deep dive

5.4.16 · D4 · Hardware › Memory Hierarchy & Caches › Memory consistency models

Shuru karne se pehle, ek shared vocabulary reminder taaki koi bhi symbol unexplained na rahe:

Reordering table jo hum baar baar use karte hain (parent se):

Model	L→L	L→S	S→S	S→L
SC	✅	✅	✅	✅
TSO (x86)	✅	✅	✅	❌
PSO	✅	✅	❌	❌
Weak (ARM/POWER)	❌	❌	❌	❌

(✅ = model inhe order mein rakhta hai; ❌ = model inhe swap kar sakta hai.)

Level 1 — Recognition

L1.1

Kaun si property — coherence ya consistency — ek single memory address ke baare mein hai, aur kaun si alag-alag addresses ke beech ordering ke baare mein hai?

Recall Solution

Coherence = single address. Sabhi cores ko ek cell pe writes ke order pe agree karna chahiye. Dekho Cache Coherence.
Consistency = across addresses. Yeh govern karta hai ki alag-alag cells pe ops ek doosre ke relative kaise order hoti hain. Coherence necessary but weaker hai; consistency global rulebook hai.

L1.2

Plain x86 (TSO) pe, chaar program-order pairs mein se kaun sa ek reorder hone diya jaata hai?

Recall Solution

Sirf S→L (ek earlier Store baad wale Load se bypass ho sakta hai). Reason: store per-core FIFO store buffer mein baitha rehta hai aur baad mein drain hota hai, jabki load abhi complete ho jaata hai. Mnemonic: "Stores Look Late."

L1.3

True ya false: C/C++ mein volatile hardware fences insert karta hai aur cross-thread ordering deta hai.

Recall Solution

False. volatile sirf compiler ko ek value register mein cache karne se rokta hai; yeh koi hardware fence emit nahi karta aur koi cross-thread ordering nahi deta. Us ke liye aapko ordering ke saath std::atomic chahiye (dekho C++ Memory Model (acquire-release)).

Level 2 — Application

L2.1 — Store Buffering (SB)

Init x = 0, y = 0.

Core 1	Core 2
`x = 1` (S1)	`y = 1` (S3)
`r1 = y` (L2)	`r2 = x` (L4)

Kya r1 == 0 && r2 == 0 possible hai (a) SC, (b) TSO ke under?

Recall Solution

(a) SC: Nahi. SC har pair enforce karta hai, S→L bhi. To $S 1 <_{m} L 2$ aur $S 3 <_{m} L 4$ . r1==0 chahiye $L 2 <_{m} S 3$ ; r2==0 chahiye $L 4 <_{m} S 1$ . Inhe chain karo: $S 1 <_{m} L 2 <_{m} S 3 <_{m} L 4 <_{m} S 1$ — ek cycle, impossible. Forbidden.
(b) TSO: Haan. TSO S→L drop karta hai. Dono stores store buffers mein baithe hain; dono loads stale 0 memory se padhte hain kisi bhi store ke drain hone se pehle. Outcome r1==r2==0 x86 pe legal hai.

L2.2 — Message passing on x86

Init data = 0, flag = 0.

Core 1 (producer)	Core 2 (consumer)
`data = 42` (S1)	`while(flag==0){}` (L3)
`flag = 1` (S2)	`r = data` (L4)

TSO/x86 pe, kya r == 42 guarantee karne ke liye fence chahiye?

Recall Solution

TSO pe koi fence nahi chahiye. Producer ke dono stores S→S hain, jo TSO preserve karta hai, isliye data=42 globally visible hota hai flag=1 se pehle. Consumer ka L3→L4, L→L hai, jo bhi preserve hota hai. Jab L3 flag==1 dekh le, data already 42 hai. (Weak hardware pe isko fences chahiye honge — dekho L3.2.)

Level 3 — Analysis

L3.1 — Cycle test on a custom outcome

L2.1 ka wahi SB test, lekin target outcome hai r1 == 1 && r2 == 0 SC ke under. Kya yeh legal hai? Ordering graph banao.

Recall Solution

Legal. Forced edges:

Program order: $S 1 <_{m} L 2$ , $S 3 <_{m} L 4$ .
r1==1 (L2 ne nayi y padhi) ⇒ $S 3 <_{m} L 2$ .
r2==0 (L4 ne purani x padhi) ⇒ $L 4 <_{m} S 1$ . Ab cycle dhundhne ki koshish karo. Ek valid total order: $S 3, L 4, S 1, L 2$ . Check: $S 3 <_{m} L 4$ ✅ (po), $S 1 <_{m} L 2$ ✅ (po), $S 3 <_{m} L 2$ ✅, $L 4 <_{m} S 1$ ✅. Koi cycle nahi ⇒ allowed. Ek single acyclic ordering jo saare edges witness kare = ek legal SC execution.

L3.2 — IRIW under weak memory

Init x = y = 0. C1: x=1. C2: y=1. C3: r1=x; r2=y. C4: r3=y; r4=x. Kya hum r1=1, r2=0, r3=1, r4=0 observe kar sakte hain (a) SC/TSO, (b) POWER/ARM pe?

Recall Solution

Is outcome ka matlab hai C3 pehle x-write dekhta hai, C4 pehle y-write dekhta hai — dono writes opposite orders mein observed.

(a) SC/TSO: Nahi. Dono ek single total store order guarantee karte hain. Agar us ek order mein $x = 1$ , $y = 1$ se pehle hai, to har reader jo $y = 1$ dekhta hai use $x = 1$ bhi dikhna chahiye. C4 ka r3=1,r4=0 dekhna C3 ke r1=1,r2=0 dekhne ko contradict karta hai.
(b) POWER/ARM: Haan. Ye non-multi-copy-atomic hain: ek write alag-alag cores tak alag-alag times pe pahunch sakti hai. Koi global store order impose nahi hota, isliye dono readers legally disagree kar sakte hain. (Dekho Out-of-Order Execution for why propagation is not simultaneous.)

Level 4 — Synthesis

L4.1 — ARM ke liye flag pattern fix karo

L2.2 ka message-passing code lo. Minimum fences insert karo taaki weak (ARM) hardware pe r == 42 guarantee ho. Har fence ka role batao.

Recall Solution

Do fences, ek per core:

Producer — S1 aur S2 ke beech ek release fence: data = 42; RELEASE_FENCE; flag = 1; Role: S1 (data) ko globally visible karta hai S2 (flag) se pehle. Theek us jagah S→S recover karta hai jahan matter karta hai.
Consumer — L3 ke baad ek acquire fence: while(flag==0){}; ACQUIRE_FENCE; r = data; Role: L4 (read data) ko L3 (read flag) ke upar float karne se rokta hai. L→L recover karta hai. Saath milke yeh ek acquire–release pair banate hain (C++ Memory Model (acquire-release)): Core 1 pe release se pehle jo kuch bhi hai wo Core 2 pe matching acquire ke baad visible hai. Poore program ko SC banane se sasta.

L4.2 — Sabse sasta tool choose karo

Tumhe chahiye ki r1==0 && r2==0 impossible ho SB test (L2.1) mein x86 pe run karte waqt. Minimum change kya hai?

Recall Solution

Har core pe store aur load ke beech ek fence insert karo: x = 1; MFENCE; r1 = y; aur y = 1; MFENCE; r2 = x; MFENCE (ya koi bhi LOCK-prefixed atomic) store buffer drain karta hai, S→L ordering restore karta hai jo TSO ne drop ki thi. Ab $S 1 <_{m} L 2$ aur $S 3 <_{m} L 4$ hold karte hain ⇒ SC wala wahi cycle argument double-zero forbid karta hai. Koi coherence change aur koi lock nahi chahiye — sirf do fences.

Level 5 — Mastery

L5.1 — Hand-off protocol design karo aur judge karo

Ek single-producer/single-consumer one-slot buffer design karo jo weak hardware pe use ho sake, phir prove karo ki consumer kabhi stale data nahi padh sakta. Har ordering guarantee batao jo tum use karte ho aur wo kahan se aati hai.

Recall Solution

Protocol (ek full flag ko acquire-release handshake ki tarah use karta hai):

Producer:            Consumer:
  buf = item           while(load_acquire(full)==0){}
  store_release(full,1)  x = buf
                         store_release(full,0)   // reclaim slot

Proof ki consumer kabhi stale buf nahi dekhta:

store_release(full,1) guarantee karta hai ki usse pehle ki har write (yahan buf=item) kisi bhi core ko visible hai jo matching load_acquire(full) perform kare aur value 1 dekhe. — release semantics.
Consumer ka load_acquire(full) jo 1 observe kare isliye producer ke release ke saath synchronizes-with karta hai. — acquire semantics.
Consequently x = buf (jo program order mein acquire ke baad hai, aur acquire baad wale loads ko uske upar hoist hone se rokta hai) wo value padh ta hai jo producer ne likhi. ∎
Coherence (single-address agreement, Cache Coherence) guarantee karta hai ki full flag itself consistently dekha jaata hai, isliye spin-wait ek baar terminate hota hai. Consistency full aur buf ke beech cross-address ordering handle karti hai.

Judgment: correct aur sasta — hot path pe exactly ek acquire aur ek release fence, kuch bhi global nahi. Yeh strictly weaker (isliye faster) hai poore region ko SC banane se, phir bhi sufficient hai.

L5.2 — Ek claim falsify karo

Ek colleague claim karta hai: "x86 pe mujhe kabhi koi fence nahi chahiye, kyunki x86 TSO hai aur TSO 'basically SC' hai." Ek ek program do jo ise falsify kare, aur wo fence batao jo ise save karta hai.

Recall Solution

Falsifier = SB test (L2.1). TSO ki single relaxation, S→L, r1==0 && r2==0 ko real x86 pe observable banati hai — ek aisa outcome jo SC forbid karta hai. To TSO, SC nahi hai; difference exactly store-buffer bypass hai. Fix: har core ke store aur load ke beech MFENCE (jaisa L4.2 mein) buffer drain karta hai aur double-zero forbid karta hai. Conclusion: "TSO ≈ SC" exactly S→L pair ke liye false hai, aur yeh pair koi academic curiosity nahi — yeh everyday Dekker/mutex-flag hazard hai.

Recall Ek-line self-check

Kisi bhi outcome ke liye universal legality test ::: program-order + read-from edges se memory-order graph banao, phir cycle check karo; ek cycle ka matlab hai wo outcome forbidden hai.