Virtual memory and paging

5.4.11 · Hardware › Memory Hierarchy & Caches

Virtual memory exist kyun karta hai?

Teen problems jo yeh ek saath solve karta hai:

1. RAM kaafi nahi. Programs ko physical RAM se zyada memory ki zaroorat pad sakti hai. Virtual memory humein pretend karne deta hai ki RAM disk jaisi badi hai — inactive pages ko disk par swap karke.
2. Multiple programs, ek RAM. Agar program A ne directly physical address 0x4000 use kiya aur program B bhi 0x4000 chahta, toh woh collide karte. Virtual memory har process ko uska apna address space deta hai — isolation & protection.
3. Fragmentation. Programs ko contiguous chunks chahiye; RAM time ke saath gaps mein cut ho jaati hai. Paging "physical RAM mein contiguous hona zaroori hai" wali constraint hata deta hai.

Key objects kya hain?

Ek address translate kaise hota hai? (derive karo)

Maano page size $P=2^p$ bytes hai. $n$ bits ka ek virtual address do parts mein split hota hai.

Split kyun? Kyunki ek single page ke andar, virtual aur physical addresses bilkul same hote hain — ek page ko frame mein move karne se internal layout identical rehta hai. Sirf kaunsa page/frame hai yeh alag hota hai. Isliye:

• Low $p$ bits = page ke andar offset. Yeh kabhi translate nahi hote.
• High $n-p$ bits = Virtual Page Number (VPN). Sirf yahi map hota hai.

$\text{VA}=\underset{n-p\text{ bits}}{\underbrace{\text{VPN}}}\Vert \underset{p\text{ bits}}{\underbrace{\text{offset}}}$

Split ko arithmetically derive karna. Ek virtual address $A$ ke liye: $\text{offset}=A\mathrm{mod}{2}^p=A\&(2^p-1),\text{VPN}=\lfloor \frac{A}{2^p}\rfloor =A\gg p$

Mask/shift kyun? $2^p$ se divide karne par low $p$ bits chhoot jaate hain (page number milta hai); remainder exactly wahi hai jo page ke andar bacha hai.

Phir frame lookup karo: $\text{PFN}=\text{PageTable}[\text{VPN}]$ $\text{PA}=(\text{PFN}\times 2^p)+\text{offset}=(\text{PFN}\ll p)|\text{offset}$

PFN ko $2^p$ se multiply kyun karte hain? Kyunki frame number $f$ physical byte $f\cdot P$ se shuru hota hai. Exact byte par pahunchne ke liye untouched offset add karo.

TLB — translation slow kyun nahi hoti

Effective access time (derive karo). Maano $t_{TLB}$ = TLB lookup time, $t_{mem}$ = memory access, hit ratio $h$. Hit par hum TLB + memory pay karte hain. Miss par hum TLB + page-table walk (ek memory access, single-level) + real memory access pay karte hain: $\text{EAT}=h(t_{TLB}+t_{mem})+(1-h)(t_{TLB}+t_{mem}+t_{mem})$ $=t_{TLB}+t_{mem}+(1-h)t_{mem}$

Last term kyun? Miss penalty exactly ek extra $t_{mem}$ hai table walk ke liye, miss probability $(1-h)$ se weighted.

Worked examples

Common mistakes (steel-manned)

Recall

Connections

• Memory hierarchy — VM, RAM aur disk ke beech ka level hai (RAM disk pages cache karta hai).
• CPU caches — TLB ek specialized cache hai; VA vs PA, VIPT/PIPT cache indexing ko affect karta hai.
• Page replacement algorithms — LRU/Clock decide karte hain ki fault par kaunsa frame evict karna hai.
• Multi-level page tables — gigantic single-level tables ka fix.
• Locality of reference — yahi wajah hai ki TLBs aur demand paging actually kaam karte hain.
• Segmentation — paging ka alternative/complement.

Concept Map