Page tables and multi-level paging — Hinglish notes

5.4.13 · Hardware › Memory Hierarchy & Caches

WHY paging exist karta hai?

WHAT problem solve kar rahe hain? Physical RAM ek shared, finite resource hai. Multiple processes ko saath rehna hai, ek doosre se isolated rehna hai, aur ek clean, contiguous address space dikhna chahiye — chahe physical memory fragmented ho.

WHY pages (fixed-size blocks), arbitrary segments ki jagah?

Fixed size ⇒ koi external fragmentation nahi, trivial allocation (koi bhi free frame kisi bhi page ke liye fit hoga).
Page ke andar ka offset translation ke dauran kabhi nahi badalta, isliye hum sirf page number translate karte hain.

HOW address split hota hai

Ek virtual address do parts mein cut hota hai: page number aur offset.

Offset unchanged kyun jaata hai? Kyunki ek page aur ek frame ka size $P$ identical hai, ek page ka byte $k$ uske frame ka byte $k$ hota hai. Sirf kaun sa frame hai woh badalta hai.

Single-level (flat) page table — aur yeh itna bada kyun hota hai

64-bit addresses ke liye flat table astronomically bada hoga ( $2^{52}$ entries). Flat tables scale nahi karte.

Multi-level paging: tables ka ek tree

HOW kaam karta hai: VPN ko khud kai index fields mein split karo, ek per level. Tree ko top-down walk karo; har entry next-level table ko point karti hai; aakhiri level PFN rakhta hai.

Figure — Page tables and multi-level paging

Cost problem aur TLB

Translation ke liye cache kyun chahiye? $n$ -level walk matlab $n$ RAM reads sirf yeh jaanne ke liye ki data kahan hai, data ko touch karne se pehle. Yeh brutal hai.

$avg translation time = t_{T L B} + (miss rate) \times (walk cost)$

Common mistakes (steel-manned)

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek bade apartment complex ki kalpana karo. Har family (program) ko bataya jaata hai "tumhare paas rooms number 1 se ek million tak hain!" — lekin building mein sach mein ek million rooms nahi hain. Toh ek directory hai: tum kaho "mujhe mera room 5 chahiye", directory dekhe ki woh asli room kaun sa hai. Ek badi directory jo sab ek million fake rooms list kare, kaagaz barbad karti hai, aur zyaadatar families sirf 3 rooms use karti hain. Toh hum ek chhoti directory use karte hain jo chhoti directories ko point kare — jaise ek table of contents jo chapters ko point kare. Hum sirf wahi chapters print karte hain jo family actually use karti hai. TLB tumhare darwaze pe ek sticky note hai jo tumhare last kuch room lookups yaad rakhti hai taaki har baar poori directory na parhni pade.

Active Recall

Flat page table scale kyun nahi karta?

Isko har possible page ke liye ek entry chahiye (

2^{v}

), zyaadatar unused; e.g. 32-bit process ke liye 4 MiB, 64-bit ke liye astronomical.

Multi-level paging kya optimize karta hai — time ya space?

Space (memory), unused address ranges ke liye tables allocate na karke. Per walk yeh zyaada time leta hai.

Offset translate kyun nahi hota?

Pages aur frames same size ke hain, toh ek page ka byte

k

= uske frame ka byte

k

; sirf page/frame number badalta hai.

Page size

P

diya ho, toh kitne offset bits?

p = lo g_{2} P

32-bit, 4 KiB pages ke liye, kitne VPN bits aur entries?

20 VPN bits,

2^{20}

≈ 1M entries.

PTE kya store karta hai?

Physical frame number aur flags (valid, R/W, user/super, dirty, accessed).

n

-level walk mein kitne memory accesses chahiye (no TLB)?

n

(ek per level) final data access se pehle.

Multi-level walks se jo speed kho jaati hai, woh kaun waapas laata hai?

TLB, jo recent VPN→PFN translations cache karta hai.

x86 pe top-level table base kaun sa register rakhta hai?

CR3.

32-bit ke liye 10/10/12 split kyun choose karte hain?

Har table =

2^{10}

× 4 B = 4 KiB = exactly ek page.

PFN aur offset se physical address ka formula?

P A = (P F N \times P) + offset

Tree mein ek unused top-level entry par kya hota hai?

Woh invalid mark hoti hai aur kisi inner table ko point nahi karti (poora subtree bacha leta hai).

Connections

Virtual Memory — paging iska mechanism implement karta hai.
TLB and Translation Caching — walks ka time cost recover karta hai.
Cache Memory Basics — page tables khud cache/RAM mein rehte hain.
Address Space Layout — sparsity ki wajah se trees jeetate hain.
Page Faults and Demand Paging — invalid PTE ek fault trigger karta hai.
Bit Manipulation and Masking — shifts/masks address split karte hain.