Visual walkthrough — Virtual memory and paging

5.4.11 · D2 · Hardware › Memory Hierarchy & Caches › Virtual memory and paging

---

Step 1 — Address hota kya hai (bytes ka ek ruler)

KYA HAI. Memory ek bahut bada row hai numbered boxes ka, jisme har ek ek byte (8 bits) hold karta hai. Ek address bas box number hota hai. Box 0, box 1, box 2, … aur aage tak.

KYUN. Isse pehle ki hum koi address "translate" kar sakein, hume agree karna hoga ki isme koi rahasya nahi hai — yeh ek ruler pe ek position hai. Agar tumhare addresses $n$ bits wide hain, to sabse bada number jo tum likh sakte ho $2^n-1$ hai, isliye tum total $2^n$ boxes ko naam de sakte ho.

PICTURE. Neeche, kali ruler memory hai. Lal tick ek address hai jo ek box ko point kar raha hai.

---

Step 2 — Ruler ko equal pages mein kaat do

KYA HAI. Us lambi ruler ko lo aur equal-length segments mein kaat do. Har segment ek page hai. Agar ek page $P$ bytes lamba hai aur $P=2^p$ hai, to har page mein exactly $2^p$ boxes aate hain.

KYUN. Hum length ko power of two, $P=2^p$, choose karte hain on purpose — yeh poori derivation ka sabse important decision hai. Binary mein, $2^p$ se divide karna bas "lowest $p$ bits ko ignore karo" hota hai, aur remainder "lowest $p$ bits by themselves" hote hain. Hum Step 4 mein isi par depend karenge. Agar $P$ kuch aur hota, say $1000$, to yeh bit-magic kaam nahi karta.

PICTURE. Wohi ruler, ab sliced. Har slice (page) same width ki hai. Lal slice page number 2 hai, aur uske andar boxes phir se $\mathrm{0..}P-1$ numbered hain, locally.

---

Step 3 — Address ko split karo: VPN aur offset

KYA HAI. Address $A$ ko binary mein likho. High $n-p$ bits ka jawab hai "konsa page?" — inhe Virtual Page Number (VPN) kaho. Low $p$ bits ka jawab hai "kitna andar?" — inhe offset kaho.

$$A=\underset{\text{high }n-p\text{ bits: which page}}{\underbrace{\text{VPN}}}\Vert \underset{\text{low }p\text{ bits: how far into it}}{\underbrace{\text{offset}}}$$

• $A$ — poora virtual address (box number jo program use karta hai).
• $\Vert$ — "saath mein likha hua," yaani bit-groups ka concatenation, multiplication nahi.
• VPN — Step 2 ki sliced ruler mein page ka index.
• offset — us page ke andar local position, hamesha $0\dots 2^p-1$ mein.

KYUN. Kyunki Step 2 ne power-of-two boundaries par slice kiya, bits literally do clean groups mein aate hain. "Konsa page" ko "andar kahan" se alag karne ke liye koi arithmetic trick nahi chahiye — split bas bit-string ko kaatna hai.

PICTURE. Bit-string $A$ jisme ek lal divider bit $p$ aur bit $p-1$ ke beech daala gaya hai. Line ke baayein sab VPN hai; daayein sab offset hai.

---

Step 4 — Shift aur mask se har part nikalo

KYA HAI. Ab hum VPN aur offset real operations se compute karte hain:

$$\text{offset}=A\&(2^p-1),\text{VPN}=A\gg p$$

• $\&$ — bitwise AND: kisi bit ko tabhi rakhta hai jab dono inputs 1 hon.
• $2^p-1$ — ek number jo binary mein $p$ ones hota hai (jaise $2^{12}-1=\text{0xFFF}$). Isse AND karne par exactly low $p$ bits bachte hain aur baaki zero ho jaate hain → yahi offset hai.
• $\gg p$ — right shift by $p$: har bit ko $p$ jagah neeche slide karo, to low $p$ bits end se gir jaate hain aur VPN neeche aa jaata hai.

KYUN yeh do tools aur division nahi? $A\gg p$ hi $\lfloor A/2^p\rfloor$ hai aur $A\&(2^p-1)$ hi $A\mathrm{mod}{2}^p$ hai — lekin shift aur mask single, one-cycle hardware operations hain. Humne Step 2 mein $P=2^p$ isliye choose kiya tha taaki mehnga division ek free wire-shift ban jaaye. Yahi power-of-two choice ka fayda hai.

PICTURE. Baayein: mask (ek lal band of $p$ ones) $A$ ke neeche, sirf offset ko rakh raha hai. Daayein: ek right-shift ka arrow VPN ko neeche place mein slide kar raha hai.

---

Step 5 — Page table mein frame dhundho

KYA HAI. VPN ko page table mein daalo — ek per-process lookup array — aur Physical Frame Number (PFN) nikalo:

$$\text{PFN}=\text{PageTable}[\text{VPN}]$$

• PageTable — VPN se index kiya gaya array; entry number $k$ batata hai ki virtual page $k$ actually kahan rehta hai.
• $[\text{VPN}]$ — "row VPN pe wali entry," ordinary array indexing.
• PFN — physical frame ka index (real RAM mein ek slot), page ke size jitna hi.

KYUN. Yahi ek step hai jahan fiction fact banti hai. Offset ko kabhi nahi chheda jaata (Step 6 batata hai kyun); sirf page ki identity remap hoti hai. Yahi indirection hai jo har process ko apna map rakhne deta hai — dekho Multi-level page tables ki table khud kitne saste mein store hoti hai.

PICTURE. VPN ek kaali table mein point karta hai; lal arrow matched row se bahar nikalta hai PFN ko physical side pe le jaata hai.

---

Step 6 — Physical address rebuild karo

KYA HAI. Frame number ko wapas untouched offset ke saath jodo:

$$\text{PA}=(\text{PFN}\ll p)|\text{offset}$$

• $\text{PFN}\ll p$ — frame number ko $p$ se left shift karo, yaani $2^p$ se multiply karo. Yeh PFN ko high bits mein le jaata hai aur $p$ empty low bits create karta hai.
• $|$ — bitwise OR: offset ko un nayi-khali low bits mein daalta hai.
• Result: PA — woh real box number jo RAM access karega.

KYUN left shift? Frame $f$ physical byte $f\times 2^p$ se shuru hota hai (frames $2^p$ bytes ki doori par, back to back hain). To frame ka starting byte $\text{PFN}\ll p$ hai, aur offset add karne se hum baaki raasta andar jaate hain. Kyunki $\text{PFN}\ll p$ ke low $p$ bits guaranteed zero hain, OR aur add identical result dete hain — koi carry collide nahi kar sakti.

PICTURE. Step 4 ka offset (poori time laal rakha gaya) shifted PFN ke saath milta hai PA banane ke liye. Dhyaan do ki lal offset bits Step 3 ke bit-for-bit same hain.

---

Step 7 — Degenerate aur edge cases

Reader ko koi unshown scenario mein mat chhodna. Is machine ke chaar corners:

1. Offset = 0. Address page boundary par exactly baitha hai — ek page ka pehla byte. To $\text{PA}=\text{PFN}\ll p$, ek clean frame base. Kuch nahi toota; OR bas zero add karta hai.
2. Offset = $2^p-1$. Ek page ka aakhri byte (saare offset bits 1). Phir bhi usi frame ke andar rehta hai — offset kabhi PFN mein overflow nahi kar sakta kyunki woh sirf $p$ bits wide hai. Yahi guarantee hai jo "sirf VPN differ karta hai" ko sach banati hai.
3. VPN table mein nahi (ya "not present" mark hai). Step 5 ka lookup fail hota hai → ek page fault fire hota hai. Yeh crash nahi hai: OS page ko disk se fetch karta hai, table entry fill karta hai, aur usi instruction ko re-run karta hai. Tab Steps 1–6 succeed karte hain.
4. VPN genuinely invalid (process ki allowed range se bahar). Ab yeh ek real error hai — ek segfault. Compare karo Segmentation se, jahan fixed pages ki jagah poori regions check hoti hain.

PICTURE. Do chote rulers side by side: sabse baayi box (offset 0, lal) aur sabse daayein box (offset $2^p-1$, lal) dono safely ek frame ke andar rehte hain — offset kabhi frame ki edge se bahar nahi jaata.

---

Step 8 — Worked number, end to end

---

Ek-picture summary

Upar sab kuch, compressed: ek arrow virtual address se flow karta hai, VPN + offset mein split hota hai, VPN page table se guzar kar PFN banta hai, aur dono physical address ke roop mein milte hain. Lal offset ko follow karo — woh seedha VA se PA tak, bina chhede, saath chalta rehta hai.

Recall Feynman retelling — poora walk simple shabdon mein

Memory ek lambi shelf hai numbered boxes ki (Step 1). Hum isse equal-size pages mein tape karte hain, har ek power-of-two lamba, to ek address naturally "konsa page, phir kitna andar" ke roop mein read hota hai — VPN aur offset (Step 3). Split free hai: page number ke liye right shift, how-far-in ke liye mask (Step 4). Sirf page number page table visit karta hai, jo ise real frame number se swap karta hai (Step 5). Hum us frame number ko upar push karte hain aur untouched offset ko neeche wapas daate hain — wahi real address hai (Step 6). Edge boxes (page ke pehle aur aakhri) phir bhi frame ke andar rehte hain, missing pages sirf OS ko fetch karke retry karwate hain, aur truly-bad addresses hi sirf real error hain (Step 7). Real hex par run karo aur offset unchanged nikalta hai, rigid-slide idea ko prove karta hua (Step 8).

Recall Quick self-check

VA→PA ek sentence mein? ::: Offset alag karo, sirf VPN ko page table ke through PFN mein translate karo, phir PFN‹‹p ko untouched offset ke saath recombine karo. Page size power of two kyun hona chahiye? ::: Taaki VPN/offset split ek free shift-and-mask ho, division nahi. Kya translation ke dauran offset kabhi change hota hai? ::: Nahi — yeh VA se PA tak bit-for-bit copy hota hai. Agar VPN ki entry "not present" ho to kya hota hai? ::: Ek page fault; OS page ko disk se load karta hai aur instruction re-run hoti hai — crash nahi.

Related: 5.4.11 Virtual memory and paging (Hinglish) · CPU caches · Locality of reference · Page replacement algorithms · Multi-level page tables