Intuition The one-sentence ideaVirtual memory needs a page table lookup on every memory access to turn a virtual address into a physical one — but that lookup itself lives in memory, so it would double (or more) every access . The TLB is a tiny, fast cache that remembers recent virtual→physical page translations , so the CPU can skip the slow page-table walk almost always.
Intuition The problem it solvesUnder paging, the CPU produces virtual addresses (VA) . Before touching memory, hardware must find the physical address (PA) by reading the page table — which is itself in DRAM.
Without help: 1 program memory access = 1 page-table read + 1 data read = at least 2× slower .
With multi-level page tables (e.g. 4 levels on x86-64): a walk is 4 DRAM reads → up to 5× slower !
Locality saves us: programs touch the same few pages repeatedly . So cache the translations. That cache is the TLB.
A Translation Lookaside Buffer is a small, fast (often fully- or set-associative) hardware cache that stores recently-used virtual-page-number → physical-frame-number mappings, together with permission/status bits. It sits inside the MMU and is consulted on every memory reference.
An address splits into a page part and an offset:
VA = VPN ⏟ virtual page number ∥ offset ⏟ within page \text{VA} = \underbrace{\text{VPN}}_{\text{virtual page number}} \;\Vert\; \underbrace{\text{offset}}_{\text{within page}} VA = virtual page number VPN ∥ within page offset
The offset is not translated — only the page number is. So the TLB maps VPN → PFN (physical frame number), and:
PA = ( PFN ≪ log 2 P ) ∥ offset \text{PA} = (\text{PFN} \ll \log_2 P) \;\Vert\; \text{offset} PA = ( PFN ≪ log 2 P ) ∥ offset
where P P P
Every memory access:
Split VA into VPN + offset.
Look up VPN in the TLB.
TLB hit → get PFN immediately → form PA → access cache/memory.TLB miss → do a full page-table walk (hardware or OS) to get PFN → insert into TLB → retry.
Also check the valid and permission bits (read/write/execute, user/kernel). A violation raises a fault.
Worked example A concrete TLB hitSystem: P = 4 P = 4 P = 4 VPN 0x00012 → PFN 0x0037.
Access VA = 0x00012ABC .
Step: split → offset = low 12 bits = 0xABC; VPN = high 20 bits = 0x00012. Why? 4 4 4 2 12 2^{12} 2 12 Step: TLB lookup for 0x00012 → hit , PFN = 0x0037.Step: PA = (PFN << 12) | offset = 0x0037 shifted left 12 = 0x00037000, OR 0xABC = 0x00037ABC . Why shift by 12? Because the PFN names a 4KiB frame; multiplying by frame size (< < 12 <<12 << 12 Result: no page-table walk needed.
Intuition Why we quantify itWe want to prove the TLB actually helps, and by how much, so we derive EMAT from first principles.
Let:
h h h t TLB t_{\text{TLB}} t TLB t m t_{m} t m a walk costs W W W L L L L L L
On a hit : pay TLB search + one data access = t TLB + t m t_{\text{TLB}} + t_m t TLB + t m miss : pay TLB search + walk (W ⋅ t m W\cdot t_m W ⋅ t m t TLB + W t m + t m t_{\text{TLB}} + W\,t_m + t_m t TLB + W t m + t m
Weighting by probability:
EMAT = t TLB + t m + ( 1 − h ) W t m \boxed{\;\text{EMAT} = t_{\text{TLB}} + t_m + (1-h)\,W\,t_m\;} EMAT = t TLB + t m + ( 1 − h ) W t m
Worked example Plugging numberst TLB = 1 t_{\text{TLB}}=1 t TLB = 1 t m = 100 t_m=100 t m = 100 W = 1 W=1 W = 1 h = 0.98 h=0.98 h = 0.98
Step: extra miss cost = ( 1 − 0.98 ) ( 1 ) ( 100 ) = 2 =(1-0.98)(1)(100)=2 = ( 1 − 0.98 ) ( 1 ) ( 100 ) = 2 Why? only 2% of accesses walk, each costing one t m t_m t m Step: EMAT = 1 + 100 + 2 = 103 =1+100+2=103 = 1 + 100 + 2 = 103 Why so close to 100? High hit rate makes the walk almost invisible.Compare h = 0.90 h=0.90 h = 0.90 = 0.10 × 100 = 10 =0.10\times100=10 = 0.10 × 100 = 10 = 111 =111 = 111 10% miss triples the overhead — hit rate matters a lot.
Intuition The TLB can holdstale or wrong-process data
The TLB holds mappings for a specific address space. On a context switch , VPN 0x5 for process A ≠ VPN 0x5 for process B. Two fixes:
Flush the TLB on every switch (simple, but cold TLB → miss storm afterward).ASID/PCID (Address-Space IDs): tag each entry with a process id so entries coexist; no flush needed.
Also, if the OS changes a page table entry (unmaps a page), the stale TLB entry must be invalidated — a TLB shootdown (on multicore, an IPI tells other cores to invalidate too).
Common mistake "The offset gets translated too."Why it feels right: translation seems to convert the whole address, so people transform all bits.
The fix: VA and PA share the same offset — only the page/frame number changes. Bytes keep their position within a page; paging just moves the whole page to a different frame. So low log 2 P \log_2 P log 2 P
Common mistake "A TLB miss means a page fault."Why it feels right: both are "misses" during translation.
The fix: A TLB miss = translation not cached, but the page is in memory → just walk the page table (fast, no disk). A page fault = the page isn't in physical memory at all → OS must load from disk (thousands× slower). TLB miss ≠ page fault.
Common mistake "Bigger TLB always wins."Why it feels right: more entries = higher hit rate.
The fix: A larger/associative TLB is slower and costs power/area, and it sits on the critical path of every access . Real designs use multi-level TLBs (small fast L1 TLB + bigger L2 TLB) — same idea as data caches.
Recall The 20% that gives 80%
TLB caches VPN→PFN ; offset is untranslated.
Flow: hit → done; miss → page-table walk , then fill.
EMAT = t TLB + t m + ( 1 − h ) W t m \text{EMAT}=t_{\text{TLB}}+t_m+(1-h)W t_m EMAT = t TLB + t m + ( 1 − h ) W t m TLB miss ≠ page fault.
Context switch → flush or ASID tags.
Recall Feynman: explain to a 12-year-oldImagine your school has thousands of lockers, but the map telling you which locker is yours is kept in the principal's office far away. Every time you fetch a book you'd have to walk to the office, read the map, then walk to your locker — super slow. So you keep a sticky note in your pocket with the locker numbers you use most. The TLB is that sticky note: check your pocket first (fast!), and only walk to the office (the page table) when the note doesn't have it.
"TLB = Translation Last-used Buffer." It remembers your last-used page translations. And for the flow: "Hit? Home. Miss? Map." (Miss → go read the page table map.)
What does a TLB cache? Recently-used virtual-page-number → physical-frame-number translations (plus permission/valid bits).
Why is the page offset never translated? Paging moves whole pages to frames; a byte keeps its position within the page, so the low
log 2 P \log_2 P log 2 P bits are identical in VA and PA.
For a 4KiB page, how many offset bits? 12, since
4 KiB = 2 12 4\text{KiB}=2^{12} 4 KiB = 2 12 .
What happens on a TLB miss? A page-table walk finds the PFN, the mapping is inserted into the TLB, and the access is retried.
Difference between TLB miss and page fault? TLB miss = translation not cached but page is in memory (fast walk); page fault = page not in physical memory (must load from disk).
Give the EMAT formula. EMAT = t TLB + t m + ( 1 − h ) W t m \text{EMAT}=t_{\text{TLB}}+t_m+(1-h)W t_m EMAT = t TLB + t m + ( 1 − h ) W t m , with hit rate
h h h and walk length
W W W accesses.
Why does hit rate matter so much? The extra cost
( 1 − h ) W t m (1-h)Wt_m ( 1 − h ) W t m scales with the miss fraction; each miss costs a full walk, so small drops in
h h h inflate access time.
Two ways to handle the TLB on a context switch? Flush the whole TLB, or tag entries with ASID/PCID so multiple address spaces coexist.
What is a TLB shootdown? Invalidating a stale TLB entry across cores (via an inter-processor interrupt) when the OS changes/unmaps a page.
How is PA formed from PFN and offset? P A = ( PFN ≪ log 2 P ) ∣ offset PA=(\text{PFN}\ll\log_2 P)\;|\;\text{offset} P A = ( PFN ≪ log 2 P ) ∣ offset .
Why not just make the TLB huge? It's on the critical path of every access; larger = slower/more power. Hence multi-level TLBs (L1 small+fast, L2 bigger).
Virtual Memory — the TLB accelerates the address translation that paging requires.Page Table — the slow structure the TLB caches; consulted on a miss (the "walk").Cache (memory hierarchy) — same locality principle; VIPT caches even overlap TLB lookup with cache indexing.Context Switch — triggers TLB flush or ASID handling.Page Fault — a different miss: page absent from RAM, not just from the TLB.Locality of Reference — why the TLB's small size still yields high hit rates.
Valid and permission bits
Intuition Hinglish mein samjhoDekho, virtual memory mein har ek memory access ke liye CPU ko virtual address ko physical address mein convert karna padta hai. Ye conversion page table dekhkar hoti hai — par page table khud DRAM mein hoti hai, jo slow hai. Agar har access pe page table padhna pade, to speed aadhi ya usse bhi kam ho jaaye (multi-level page table mein to 4 DRAM reads!). Isiliye TLB banaya gaya: ye ek chhota, super-fast hardware cache hai jo recently use hui VPN -> PFN translations yaad rakhta hai. Programs baar-baar same pages touch karte hain (locality), isliye TLB mostly hit hota hai aur slow walk bach jaata hai.
Key baat: address ka offset translate nahi hota . Sirf page number (upar ke bits) badalta hai, niche ke log 2 P \log_2 P log 2 P Hit? Home (turant PFN mil gaya), Miss? Map (page table walk karo, PFN nikaalo, TLB mein daalo, retry karo).
Performance ka formula bhi first principles se aata hai: hamesha TLB search + ek data access lagta hai, aur extra cost sirf miss pe: EMAT = t TLB + t m + ( 1 − h ) W t m \text{EMAT}=t_{\text{TLB}}+t_m+(1-h)Wt_m EMAT = t TLB + t m + ( 1 − h ) W t m h h h
Ek confusion door kar lo: TLB miss aur page fault alag cheez hain . TLB miss matlab translation cache mein nahi tha par page RAM mein hai (fast walk). Page fault matlab page RAM mein hai hi nahi, disk se laana padega (hazaaron guna slow). Aur context switch pe TLB ya to flush hota hai ya ASID/PCID tags se different processes ki entries alag rakhi jaati hain.
