Foundations — Atomic operations and CAS

6.1.9 · D1 · Hardware › Parallelism & Multicore › Atomic operations and CAS

Parent note padhne se pehle, tumhe kuch chote se words aur squiggles mein fluent hona chahiye jo woh bina ruke use karta hai. Hum unhe ek-ek karke banate hain, har ek pichle ke upar. Yahan koi yeh nahi maana gaya ki tum pointer, race, ya *addr ka matlab jaante ho — hum ek numbered boxes ki shelf se shuru karte hain.

1. Memory ek numbered boxes ki wall ki tarah

Figure dekho. Gray row memory hai. Har box ke neeche number (0, 1, 2, …) uska address hai — yeh kabhi nahi badalti. Box ke andar number uski value hai — yeh badal sakti hai. Yeh ek distinction (address vs. value) baad mein almost har confusion ka source hai, isliye ise firmly pakad ke rakho.

Topic ko yeh kyun chahiye: atomic operations hamesha ek specific box par act karti hain. Poora khel yeh hai ki "is box ke andar number ko kaun badal sakta hai, aur kab."

2. Pointer *addr — ek box ki taraf arrow

Do symbols, do kaam:

• addr — arrow khud (kaunsa box).
• *addr — arrow follow karna us box mein number padhne/likhne ke liye.

Figure mein orange arrow hi addr hai; yeh number 200 hold karta hai, isliye box 200 ki taraf point karta hai. *addr = 7 likhna matlab hai "us box mein 7 daalo jis box ki taraf arrow point karta hai." *addr = *addr + 1 likhna matlab hai "box 200 padho, ek jodo, result wapas box 200 mein daalo."

Topic ko yeh kyun chahiye: CAS ka pehla argument hamesha ek pointer hota hai (CAS(addr, ...)). Use pata hona chahiye kaunsa box guard karna hai tab hi woh use guard kar sakta hai.

3. Read-Modify-Write (RMW) — teen-step move

counter = counter + 1 ek line lagti hai, lekin CPU yeh karta hai:

1. R — box mein number padho (maano 10),
2. M — compute karo 10 + 1 = 11,
3. W — 11 wapas box mein likho.

Topic ko yeh kyun chahiye: parent note jis poori danger ke saath kholti hai woh R, M, aur W ke beech ke gaps mein rehti hai. Agar woh teen steps aapas mein jude nahi hain, toh doosra worker andar ghus sakta hai.

4. Threads — bahut haath, ek wall

Do haath ek hi box ki taraf badhte socho. Kuch bhi dono ko roke nahi — jab tak hardware koi rule na de. Woh rule hi atomics deta hai hamein.

5. Interleaving aur race window

Figure mein time axis (left → right) follow karo. Dono threads 10 padhte hain koi bhi likhne se pehle. Dono 11 compute karte hain. Dono 11 likhte hain. Do increments hue lekin counter sirf ek se badha — ek lost update. Ek thread ke Read aur uske Write ke beech dashed red region race condition window hai: woh gap jahan doosre thread ki write tumhari assumption ko poison kar sakti hai.

Topic ko yeh kyun chahiye: parent note ki opening story ("12 expect ki, 11 mila") yahi figure hai.

6. Math notation ←, =, aur cases {

Parent note $\ast addr\leftarrow new$ jaise formulas likhta hai. Yeh arrows aur braces scary nahi hain — yahan har ek hai.

Toh parent ka CAS formula $\text{CAS}(addr,expected,new)⟹\{\begin{array}{ll}\ast addr\leftarrow new,& \text{if }\ast addr=expected\\ \text{no change},& \text{if }\ast addr\ne expected\end{array}$ ab plain English mein padha jaata hai: "Box dekho. Uski value ko expected se compare karo. Agar match karte hain, box mein new assign karo. Warna, chodh do." $\ne$ symbol bas "not equal" matlab hai.

Topic ko yeh kyun chahiye: parent mein har atomic primitive (Fetch-And-Add, Test-And-Set, Swap, CAS) exactly inhi teen symbols ke saath likha hai.

7. true/false aur retry loop

Figure loop ko ek cycle ke roop mein dikhata hai: read → compute → attempt. Ek green exit success par loop se bahar nikalta hai; ek red arrow failure par wapas curls karta hai. Yeh har lock-free algorithm ka skeleton hai jo tumhe Lock-Free Data Structures mein milega.

Topic ko yeh kyun chahiye: retry loop ke bina, ek single CAS failure tumhara kaam kho deti. Loop hi "interference detect karo" ko "interference handle karo" mein badalta hai.

8. Cache lines aur coherence — jahan atomicity physically hoti hai

Abhi tumhe poora protocol nahi chahiye (woh baad ka dive hai) — bas yeh jaano ki "ek cache line lock karna" woh hai jisse hardware §5 ka zero-width window deta hai, aur yeh poori bus freeze karne se sasta hai.

9. Instruction reordering — kyun memory barriers exist karte hain

Parent ke tags ${\text{CAS}}_{acquire}$, ${\text{CAS}}_{release}$, ${\text{CAS}}_{seq\_cst}$ bas is fence ki teen strengths hain, CAS ke saath judi hain. D1 ke liye tumhe bas itna jaanna chahiye ki ek fence exist karti hai; strengths baad mein aati hain.

Prerequisite map

Ise top-down padho: numbered boxes aur threads ground floor hain; race window atomicity ki zaroorat force karti hai; atomicity plus math notation aur retry loop milke CAS banate hain; cache lines aur barriers explain karte hain ki yeh sab real silicon par kaise kaam karta hai.

Equipment checklist

Right side cover karo aur zor se jawab do. Agar koi bhi ruke, parent note kholne se pehle woh section dobara padho.