Page tables and multi-level paging
WHY does paging exist at all?
WHAT problem are we solving? Physical RAM is a shared, finite resource. Multiple processes must coexist, be isolated from each other, and see a clean, contiguous address space even when physical memory is fragmented.
WHY pages (fixed-size blocks) instead of arbitrary segments?
- Fixed size ⇒ no external fragmentation, trivial allocation (any free frame fits any page).
- The offset within a page never changes during translation, so we only translate the page number.
HOW an address is split
A virtual address is cut into two parts: the page number and the offset.
Why does the offset pass through unchanged? Because a page and a frame have identical size , byte of a page is byte of its frame. Only which frame changes.
The single-level (flat) page table — and why it's too big
For 64-bit addresses a flat table is astronomically large ( entries). Flat tables do not scale.
Multi-level paging: a tree of tables
HOW it works: split the VPN itself into several index fields, one per level. Walk the tree top-down; each entry points to the next-level table; the last level holds the PFN.
The cost problem and the TLB
WHY do we need a cache for translation? An -level walk means RAM reads just to find where the data lives, before touching the data itself. That's brutal.
Common mistakes (steel-manned)
Recall Feynman: explain to a 12-year-old
Imagine a huge apartment complex. Every family (program) is told "you have rooms numbered 1 to a million!" — but the building doesn't really have a million rooms. So there's a directory: you say "I want my room 5", the directory looks up which real room that maps to. A giant directory listing all million fake rooms wastes paper, and most families only use 3 rooms. So instead we use a small directory that points to smaller directories — like a table of contents pointing to chapters. We only print the chapters a family actually uses. The TLB is a sticky note on your door remembering your last few room lookups so you don't reread the whole directory every time.
Active Recall
Why does a flat page table not scale?
What does multi-level paging optimize — time or space?
Why is the offset not translated?
Given page size , how many offset bits?
For 32-bit, 4 KiB pages, how many VPN bits and entries?
What does a PTE store?
How many memory accesses does an -level walk need (no TLB)?
What restores speed lost to multi-level walks?
What register holds the top-level table base on x86?
Why choose a 10/10/12 split for 32-bit?
Formula for physical address from PFN and offset?
What is stored at an unused top-level entry in a tree?
Connections
- Virtual Memory — paging is the mechanism that implements it.
- TLB and Translation Caching — recovers the time cost of walks.
- Cache Memory Basics — page tables themselves live in cache/RAM.
- Address Space Layout — sparsity is why trees win.
- Page Faults and Demand Paging — invalid PTE triggers a fault.
- Bit Manipulation and Masking — shifts/masks split the address.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, har program sochta hai ki uske paas poori memory hai — ye "virtual address" ka jaadu hai. Lekin real RAM to limited hai, isliye hardware ko har virtual address ko real (physical) address me convert karna padta hai. Ye kaam karta hai page table. Memory ko chote fixed blocks me todte hain jinhe page kehte hain (usually 4 KiB), aur physical memory ke blocks ko frame. Page table basically batata hai: "tumhara virtual page number X, physical frame Y me pada hai."
Ab problem ye hai: 32-bit me poore 10 lakh (2^20) entries banenge, yaani 4 MB sirf table ke liye — aur wo bhi har process ke liye! Zyadaatar entries khaali rehti hain kyunki program itni saari memory use hi nahi karta. Isiliye multi-level paging aata hai: ek chota top table (directory) banate hain jo chote-chote inner tables ko point karta hai, aur inner tables actual frame batate hain. Fayda? Jo address range use hi nahi hoti, uske liye inner table banate hi nahi. Bahut memory bach jaati hai — ye hai 80/20 wali soch.
Ek important baat: offset translate nahi hota. Address ke low 12 bits (4 KiB page ke andar ka position) waise ke waise reh jaate hain, sirf page number badalta hai — kyunki page aur frame same size ke hain. Aur yaad rakho: multi-level tree memory bachata hai, speed nahi. Har level ke liye ek extra memory read lagti hai, to walk slow ho jaata hai. Isko fix karne ke liye TLB hota hai — ek chhoti fast cache jo recent translations yaad rakhti hai, taaki har baar poora tree na chalna pade.