4.1.15
Intuition 30-second pictureHar memory access mein CPU ek virtual address use karta hai. Lekin RAM sirf physical addresses samajhti hai. Ek ko doosre mein translate karne ke liye memory mein ek multi-level page table walk karni padti hai — matlab har ek load/store ke liye kaafi extra memory accesses . Yeh catastrophically slow hota.
TLB (Translation Lookaside Buffer) ek tiny, super-fast cache hai recent virtual→physical page translations ka . Yeh "DRAM mein page table walk karo" ko "ek entry ko kuch nanoseconds mein lookup karo" mein badal deta hai.
TLB ek chhota sa hardware cache hai jo recently-used page-table entries (PTEs) store karta hai , ek Virtual Page Number (VPN) ko Physical Frame Number (PFN) aur metadata (valid, dirty, permission, ASID) se map karta hai.
Yeh MMU mein baith ta hai aur har memory reference par consult kiya jata hai, cache access ke parallel mein (ya pehle).
Key vocabulary
VPN (Virtual Page Number): virtual address ke high bits (page index).PFN / PPN (Physical Frame Number): physical address ke high bits.Page offset : low bits — yeh virtual aur physical addresses mein identical hote hain, isliye inhe kabhi translate nahi kiya jata .
Intuition Offset kyun translate nahi hotaTranslation page granularity par kaam karta hai. Agar page size 4 KB = 2 12 andar koi byte kahan hai — isliye offset seedha pass through hota hai. TLB ko sirf page-number mapping yaad rakhni hoti hai, isliye yeh tiny ho sakta hai.
Worked example 48-bit VA, 4 KB pages
V = 48 = 4 KB ⇒ p = log 2 ( 4096 ) = 12 Offset = 12 bits. VPN = 48 − 12 = 36 Yeh step kyun? Kyunki page size se neeche kuch bhi translation ke under nahi badal sakta.Pages ki sankhya jo ek process ke paas ho sakti hai = 2 36 page tables multi-level hote hain aur isliye hume TLB chahiye taaki unhe walk karna skip ho sake.
Ek TLB entry kuch aisi dikhti hai:
Valid
ASID/PCID
VPN (tag)
PFN
Dirty
Permissions (R/W/X, U/S)
Global
Definition Associativity options
Fully associative : koi bhi VPN kisi bhi entry mein baith sakta hai → highest hit rate, costly (saare tags compare karta hai). Chhote L1 TLBs ke liye common (jaise 64 entries).Set-associative : VPN bits ek set choose karte hain; tag set ke andar match karta hai. Bade L2 TLBs ke liye use hota hai (jaise 1536 entries).
Intuition ASID/PCID kyun exist karta haiDo processes dono virtual address 0x400000 use karte hain, lekin yeh alag physical frames par map hota hai. Bina tag ke, ek context switch poora TLB flush force karta (sab kuch phenk do — costly!). Address Space ID (ASID/PCID) har entry ko uske owning process se tag karta hai, taaki alag processes ke entries safely saath rahe sakein. Global bit kernel pages ko mark karta hai jo sab share karte hain → kabhi flush nahi hote.
Do philosophies hain ki kaun TLB ko refill karta hai.
Definition Hardware-managed (walk) vs Software-managed
Hardware-managed TLB (x86, ARM): Ek dedicated hardware page-table walker miss par automatically multi-level page table walk karta hai memory mein, PTE ko TLB mein insert karta hai, aur instruction retry karta hai. OS sirf tables set up karta hai. Fast, lekin page-table format ISA se fix hota hai. Software-managed TLB (MIPS, older SPARC): Miss ek TLB-miss exception/trap raise karta hai; OS handler PTE padhta hai aur explicitly usse ek special instruction se TLB mein likhta hai, phir return karta hai. Flexible page-table format, lekin trap overhead zyada hota hai.
Intuition "Miss" aur "page fault" ek nahi hai
TLB miss : translation page table mein exist karta hai lekin TLB mein cached nahi hai. Thoda sasta — bas PTE fetch karo.Page fault : page physical memory mein bhi nahi hai (PTE mein valid bit = 0) → OS ko disk se fetch karna hoga, shayad doosra page evict karna hoga. Expensive (milliseconds).
Ek TLB miss page fault le ja sakta hai agar walk invalid PTE paata hai.
Worked example TLB miss par kya hota hai
CPU VA banata hai, VPN/offset mein split karta hai. Kyun? Page number chahiye lookup ke liye.
TLB lookup → miss (koi matching valid entry nahi).
Hardware walker DRAM se page table padhta hai, ek level per memory access (jaise x86-64 ke 4-level ke liye 4 accesses). Itne zyada kyun? Table hierarchical hai taaki 2 36
Agar PTE valid hai → (VPN→PFN, perms) ko TLB mein install karo, possibly ek purani entry evict karo (LRU/pseudo-LRU). Faulting instruction retry karo → ab hit .Agar PTE invalid hai → page fault raise karo → OS page laata hai, PTE update karta hai, return karta hai; access retry hota hai (likely ek aur TLB miss, phir hit).
Worked example Numbers daalot TLB = 1 ns t m = 100 ns h = 0.98 k = 4 EMAT = 1 + 100 ( 1 + 0.02 × 4 ) = 1 + 100 ( 1.08 ) = 109 ns . Yeh kyun matter karta hai: 98% hit rate bhi har access mein 8% add karta hai. 90% rate deta 1 + 100 ( 1.4 ) = 141 isliye huge TLB hit rates silicon ke kaam ki hain.
Intuition Forecast-then-VerifyPehle predict karo: agar h → 1 forecast karna chahiye t TLB + t m = 101 ( 1 − h ) k → 0
Common mistake "TLB miss = page fault"Kyun sahi lagta hai: dono mein "address nahi mila." Fix: TLB miss ka sirf matlab hai translation cached nahi thi; page table mein abhi bhi hai. Page fault ka matlab hai page RAM mein nahi hai . Ek nanoseconds ka, doosra milliseconds ka.
Common mistake "Page offset bhi translate hota hai"Kyun sahi lagta hai: poora virtual address transform hona chahiye lagta hai. Fix: sirf VPN→PFN mapping translate hoti hai; offset verbatim copy hota hai. Yahi reason hai ki TLB entry chhoti hoti hai.
Common mistake "Har context switch par poora TLB flush karna hoga"Kyun sahi lagta hai: alag processes same virtual addresses reuse karte hain, isliye stale entries dangerous lagti hain. Fix: ASID/PCID tags alag processes ke entries ko saath rehne dete hain; sirf tab flush karo jab ASIDs exhaust/recycle ho jaayein. Kernel pages Global bit use karte hain aur flushes survive karte hain.
Common mistake "Bade pages hamesha TLB ke liye better hote hain"Kyun sahi lagta hai: ek huge-page entry zyada memory cover karti hai → kam misses. Fix: TLB reach ke liye sahi hai, lekin huge pages memory waste karte hain (internal fragmentation) aur allocation complicated karte hain; yeh tradeoff hai, free nahi.
TLB kya cache karta hai? Recently-used page-table entries: VPN → PFN mappings plus metadata (valid, dirty, permissions, ASID).
Page offset kabhi translate kyun nahi hota? Translation per-page hoti hai; offset sirf ek byte ko page ke andar locate karta hai, jo page relocate hone par nahi badalta.
V-bit virtual address aur page size 2 p V − p p
TLB miss aur page fault mein kya fark hai? TLB miss = translation cached nahi lekin page table mein exist karti hai (sasti walk). Page fault = page physical memory mein nahi hai (slow disk access).
Hardware- vs software-managed TLB? Hardware: ek page-table walker miss par auto-refill karta hai (x86/ARM). Software: ek trap OS handler ko invoke karta hai jo entry likhta hai (MIPS).
EMAT formula kya hai? t TLB + t m ( 1 + ( 1 − h ) k ) h k
ASID/PCID field kya prevent karta hai? Context switch par full TLB flushes — alag processes ke entries apne owning address space ke tag se saath coexist karte hain.
TLB hit par physical address kaise banta hai? P A = ( P F N ≪ p ) ∣ offset
Global bit kya mark karta hai? Kernel/shared pages jo saare address spaces mein valid hain — context switch par kabhi flush nahi hote.
Page tables multi-level kyun hote hain (TLB miss cost se relevant)? 2 V − p k
Recall Feynman: 12-saal ke bachche ko samjhaoSocho tumhara ghar ka number ek secret code mein likha hai, aur asli street dhundhne ke liye tumhe ek bade phone book mein dekhna padta hai. Har ek kadam par yeh karna exhausting hoga. Toh tum ek tiny notepad rakhte ho apne last few lookups ke saath. Woh notepad hi TLB hai. Agar tumhara chahiye address notepad par hai — instant! Agar nahi, tum bade phone book mein jaate ho (page table), answer apne notepad par copy karte ho, aur continue karte ho. Agar jagah phone book mein bhi nahi hai, toh tume door ke storage se mangwana padta hai — woh slow page fault hai.
Mnemonic Miss path yaad karo"Split, Search, Stuck? Walk, Write, reTry."
VA split karo → TLB Search karo → Stuck (miss)? → Page table Walk karo → TLB mein entry Write karo → Instruction reTry karo.
Recall Active recall checkpointPage cover karo. Zor se jawab do: (1) TLB hit ke liye kaunse teen fields match karne chahiye? (2) 16 KB pages ke liye offset bits derive karo. (3) h = 0.95 k = 3 t m = 80 t TLB = 2
Virtual Memory — woh abstraction jise TLB accelerate karta hai.Page Tables (Multi-level) — jo TLB miss walk karta hai.Cache Memory & Associativity — TLB ek cache hai ; same set/fully-associative ideas.Page Faults & Demand Paging — kya hota hai jab walk ek invalid PTE paata hai.Context Switching — kyun ASID/PCID aur TLB flushes matter karte hain.Huge Pages / TLB Reach — ek single TLB entry ki coverage tune karna.
passes through untranslated
too large to walk each time
Valid ASID Dirty Perms Global
