4.2.26
Intuition Core idea ek line meinEk huge address space ke liye single flat page table mostly empty hoti hai, phir bhi bahut badi hoti hai . Multi-level page tables humein sirf woh hisse store karne deti hain jo actually use ho rahe hain , virtual address ko ek tree of indexes mein split karke.
Definition Problem (single-level page table)Ek page table har virtual page number (VPN) ko ek physical frame number (PFN) se map karti hai.
Single-level table ke saath, humein har virtual page ke liye ek entry chahiye, chahe woh page use ho ya na ho.
KYA gadbad hoti hai? Chaliye flat table ka size compute karte hain.
Worked example Classic 32-bit shockV = 32 4 KB ⇒ p = 12 E = 4
#pages = 2 32 − 12 = 2 20 ≈ 1 0 6
Table size = 2 20 × 4 = 4 MB per process .
Yeh step kyun matter karta hai: 100 processes ⇒ 400 MB page tables ke liye, jo mostly unused hain (ek process apni 4 GB space ka ek tiny slice hi touch karta hai). Yahi waste hai jis par hum attack karte hain.
Intuition Splitting kyun help karta haiEk program ke used pages kuch regions mein cluster hote hain (code neeche, stack upar, heap middle mein). Flat table humein har possible page ke liye slot reserve karwati hai. Agar hum stages mein index karein, toh poora unused 4 MB chunk top table mein ek single "not present" entry se represent ho sakta hai — toh hum kabhi uski second-level table allocate hi nahi karte. Sparsity ban jaati hai savings.
Definition Two-level page tableVPN ko do parts mein split karo. Top bits ek page directory (level 1) ko index karte hain. Har present directory entry ek second-level page table ki taraf point karti hai. Agle bits uss table ko index karte hain taaki PFN mile. Final bits page offset hote hain (translation se unchanged).
Worked example EAT numbers — pehle forecast phir verifyMaano t mem = 100 ns t TLB = 0 k = 2 h = 0.98
Forecast: mostly hits ⇒ 100ns ke kareeeb hona chahiye.Verify: 0.98 ( 100 ) + 0.02 ( 3 × 100 ) = 98 + 6 = 104 ns Yeh step kyun: dikhata hai ki TLB 3× cost ko ek tiny tax mein badal deta hai.
Common mistake "Multi-level page tables hamesha memory save karte hain."Kyun sahi lagta hai: hum sunते hain ki yeh zyada efficient hote hain.
Sach: agar ek process apna poora address space use kare, toh multi-level thoda bada hota hai (extra directory pages). Saving sparsity se aati hai, structure se nahi.
Fix: yaad rakho ki win hai "khali regions ke liye L2 tables allocate mat karo."
Common mistake "Page size× Kyun sahi lagta hai: dimensional handwaving.
Fix: bits add hote hain: V = a + b + ⋯ + p = 2 V 2 ( lower bits )
Common mistake "TLB multi-level cost ko permanently remove kar deta hai."Kyun sahi lagta hai: hits fast hoti hain.
Fix: ek TLB miss abhi bhi full k 4 levels use karta hai) achhi locality + large pages par rely karte hain.
Why is a single-level page table wasteful for a 32-bit space? Isko har virtual page ke liye ek PTE chahiye (2 20
Size formula for a single-level table? 2 V − p × E V p = log 2 ( page size ) E
Why does multi-level save space? Unused regions directory mein sirf ek "not present" entry hoti hain, toh unki second-level tables kabhi allocate nahi hoti (sparsity → savings).
How do you split a virtual address for k Bits add karo: V = ( L1 bits ) + ⋯ + ( Lk bits ) + p
Why choose 10/10/12 for 32-bit, 4KB, 4B PTE? Taaki har second-level table (1024×4B = 4KB) exactly ek page mein fit ho; baaki bits directory aur offset ko jaate hain.
Time cost of a k k + 1 k
What hardware hides the walk cost? TLB, jo VPN→PFN cache karta hai; ek hit page-table walk skip kar deta hai.
Worst-case space vs single-level? Thoda bada — saari leaf tables ke upar directory page(s) add ho jaate hain; multi-level tab hi win karta hai jab sparse ho.
EAT formula with TLB hit rate h h ( t T L B + t m e m ) + ( 1 − h ) (( k + 1 ) t m e m + t T L B )
Recall Feynman: ek 12-saal ke bache ko explain karoSocho ek giant hotel hai jisme ek million rooms hain, aur ek badi guest list hai jisme har room ke liye ek line hai — chahe woh empty ho. Woh list enormous hai aur mostly blank hai. Iske bajaye, hum ek chhoti floor directory rakhte hain: "Floor 3 mein guests hain, yeh rahi unki list; Floor 4 khali hai — koi list nahi." Kisi ko dhundhne ke liye tum floor directory check karte ho, phir us floor ki chhoti list. Tum sirf unhi floors ki lists rakhte ho jisme actually log hain. Kisi ko dhundhna do extra steps leta hai, toh hum ek sticky-note (TLB) rakhte hain un logon ka jo humne recently dhundhe hain, taaki jaldi jaa sakein.
Mnemonic Structure yaad rakho"DIP TO" — D irectory → I ndex into P age T able → O ffset.
Aur cost ke liye: "Walk costs k
Used pages cluster in regions
L2 fits one page b = p - log2 E
