Memory models — sequential consistency, TSO, relaxed

4.1.26 · Coding › Computer Architecture (Deep)

Memory model exist kyun karta hai?

YEH kya govern karta hai: threads ke across alag memory locations par operations ki visible ordering. (Single-location ordering cache coherence se handle hoti hai aur har jagah assume ki jaati hai.)

HOW we reason: hum ek chota canonical test (ek litmus test) pick karte hain, enumerate karte hain ki kaunse final register/memory values possible hain, aur ek memory model simply woh outcomes hain jo yeh allow karta hai.

Models ki seedhi (strong → weak)

Reordering allowed?	SC	TSO	Relaxed
Store → Load	✗	✓	✓
Store → Store	✗	✗	✓
Load → Load	✗	✗	✓
Load → Store	✗	✗	✓

Canonical litmus tests ko first principles se derive karna

Store Buffer (SB) test — SC aur TSO mein farq karta hai

Shared x = y = 0. Do threads:

T1:  x = 1;   r1 = y;
T2:  y = 1;   r2 = x;

Worked example Kya

r1 == 0 && r2 == 0 ho sakta hai? Yeh kyun poocha? Yeh woh minimal program hai jo store→load reordering expose karta hai.

SC ke under: Koi bhi total interleaving pick karo. Dono reads ke 0 hone ke liye, dono loads ko dono stores ke visible hone se pehle execute hona chahiye. Lekin do stores aur do loads ek total order mein fit hone chahiye; jo bhi store pehle hota hai, doosre thread ka baad wala load use dekhna chahiye. Enumerate karo: har interleaving mein r1,r2 mein se kam se kam ek 1 read karta hai. Toh 0,0 FORBIDDEN hai. (Yeh step kyun? Ek single total order mein aap dono loads ko dono stores se pehle nahi rakh sakte jabki har thread apna program order rakhe.)
TSO ke under: x=1 T1 ke store buffer mein jaata hai; T1 ka r1 = y turant run karta hai aur 0 read karta hai (y abhi globally nahi likha). Similarly T2 r2 = x = 0 read karta hai. Dono stores abhi buffers mein hain. 0,0 ALLOWED hai. Yahi woh famous behaviour hai jo real x86 chips dikhate hain.

Message Passing (MP) test — TSO aur Relaxed mein farq karta hai

T1:  data = 42;   flag = 1;        // producer
T2:  while(flag==0){}  r = data;   // consumer

Language layer: C11/C++11 memory orders

memory_order_relaxed — sirf atomicity + per-location coherence. Koi cross-location ordering nahi.
acquire (loads) / release (stores) — ek release-store us acquire-load ke saath synchronizes-with karta hai jo use read karta hai, release se pehle ki har cheez publish karta hai. MP sahi implement karta hai.
seq_cst (default) — saare seq_cst ops ke across ek single global total order (SC) restore karta hai. x86 par ek seq_cst store ≈ store + MFENCE; ARM par ≈ barriers.

Flashcards

Ek memory model kya specify karta hai?

Threads ke across memory reads/writes ke allowed orderings — hardware/compiler ↔ programmer contract.

Sequential consistency define karo.

Result ek single total interleaving ke barabar hota hai jo saare operations ka hai aur har thread ke program order ka respect karta hai.

TSO vs SC mein kaunsi single relaxation hai?

Ek per-core store buffer jo store→load reordering allow karta hai (ek load ek earlier store ke globally visible hone se pehle complete ho sakta hai).

TSO kaun se reorderings forbid karta hai?

store→store, load→load, load→store (sirf store→load allowed hai).

Ek relaxed model (ARM/POWER) kaun se reorderings allow karta hai?

Charon: store/load × store/load alag addresses par (coherence + dependencies ke subject).

SB test mein, kya r10 && r20 SC ke under possible hai?

Nahi — SC se forbidden hai.

SB test mein, kya r10 && r20 TSO/x86 ke under possible hai?

Haan — dono stores store buffers mein baithe hain jabki loads stale 0s read karte hain.

SB pattern ke liye x86 par SC kaunsi instruction restore karti hai?

Store aur load ke beech MFENCE (store buffer drain karta hai).

MP test mein, kya consumer TSO ke under flag==1 lekin stale data dekh sakta hai?

Nahi — store→store aur load→load preserved hain, toh flag se pehle data publish ho jaata hai.

MP test mein, relaxed hardware stale data kyun dikha sakta hai?

store→store ya load→load reorder ho sakta hai; stores independently propagate hote hain kisi implicit ordering ke bina.

Correct MP saste mein implement karne wale C++ orders kaun se hain?

flag par release store + flag par acquire load.

Release→acquire pair kya guarantee karta hai?

Release se pehle ki har cheez matching acquire ke baad ki har cheez se happens-before hai (publication).

Recall Feynman: 12 saal ke bachche ko explain karo

Socho har worker (CPU core) notes likhta hai aur unhe ek outbox mein daalta hai. Ek note doosron ko tab tak nahi dikhta jab tak mail actually nahi jaata — chahe worker aage badh gaya ho. Sequential consistency = ek strict office jahan ek shared list har action ko ek true order mein record karti hai, toh sabko pata hai kya kab hua. TSO = office mostly agree karta hai, lekin har worker ka ek chota outbox hai, toh woh apna aagla reading kar sakta hai pehle hi aakhiri likha hua note mail hone se. Relaxed = ek chaotic office jahan letters kisi bhi order mein aate hain jab tak tum explicitly "pehle yahi bhejo!" stamp nahi karte (ek barrier). Stamp slow hai lekin order guarantee karta hai.

Connections

Cache Coherence (MESI) — single-location ordering guarantee karta hai; memory models multi-location ordering govern karte hain.
Store Buffers and Out-of-Order Execution — woh hardware reason jo TSO ko exist karata hai.
Memory Barriers and Fences — MFENCE, DMB, lwsync/sync, isb.
C++ Atomics and memory_order — language-level model.
Lock-free Programming — jahan release/acquire aur seq_cst sabse zyada matter karte hain.
Peterson and Dekker Locks — fence ke bina TSO ke under break ho jaate hain (SB pattern).
Happens-before and Synchronizes-with — formal ordering relation.