TLB — structure, TLB miss handling — Coding notes

WHAT is a TLB?

Key vocabulary

VPN (Virtual Page Number): the high bits of a virtual address (the page index).
PFN / PPN (Physical Frame Number): the high bits of the physical address.
Page offset: the low bits — these are identical in virtual and physical addresses, so they are never translated.

Structure of a TLB

A TLB entry looks like:

Valid	ASID/PCID	VPN (tag)	PFN	Dirty	Permissions (R/W/X, U/S)	Global

Figure — TLB — structure, TLB miss handling

TLB MISS handling — the heart of it

There are two philosophies for who refills the TLB.

Step-by-step miss flow (hardware-managed)

Performance model

Formula Effective Memory Access Time (derive it)

Let:

$h$ = TLB hit ratio, $t_{\text{TLB}}$ = TLB lookup time, $t_{m}$ = one memory access.
On a hit: total = $t_{\text{TLB}} + t_m$ (translate, then access data).
On a miss (hardware walk of $k$ levels): pay $t_{\text{TLB}}$ + $k\,t_m$ (the walk) + $t_m$ (the data) $\approx t_{\text{TLB}} + (k{+}1)t_m$ . $\text{EMAT} = h\,(t_{\text{TLB}} + t_m) + (1-h)\,\big(t_{\text{TLB}} + (k{+}1)\,t_m\big)$ Simplify ( $t_{\text{TLB}}$ paid always): $\boxed{\text{EMAT} = t_{\text{TLB}} + t_m\big(1 + (1-h)\,k\big)}$

Common mistakes (Steel-manned)

Flashcards

What does a TLB cache?

Recently-used page-table entries: VPN → PFN mappings plus metadata (valid, dirty, permissions, ASID).

Why is the page offset never translated?

Translation is per-page; the offset only locates a byte within a page, which doesn't change when the page is relocated.

Given V-bit virtual address and page size

2^p

, how many VPN bits?

V - p

bits; offset is

p

bits.

Difference between a TLB miss and a page fault?

TLB miss = translation not cached but exists in page table (cheap walk). Page fault = page not in physical memory (slow disk access).

Hardware- vs software-managed TLB?

Hardware: a page-table walker auto-refills on miss (x86/ARM). Software: a trap invokes an OS handler that writes the entry (MIPS).

What is the EMAT formula?

t_{\text{TLB}} + t_m\,(1 + (1-h)k)

where

h

=hit ratio,

k

=page-table levels.

What does the ASID/PCID field prevent?

Full TLB flushes on context switch — entries from different processes coexist by being tagged with their owning address space.

How is the physical address formed on a TLB hit?

PA = (PFN \ll p)\ |\ \text{offset}

What does the Global bit mark?

Kernel/shared pages valid in all address spaces — never flushed on context switch.

Why are page tables multi-level (relevant to TLB miss cost)?

To avoid storing

2^{V-p}

flat entries; the cost is that a miss walk takes

k

memory accesses.

Recall Feynman: explain to a 12-year-old

Imagine your house number is written in a secret code, and to find the real street you must look it up in a giant phone book. Doing that for every step you take would be exhausting. So you keep a tiny notepad with the last few lookups you did. That notepad is the TLB. If the address you need is on the notepad — instant! If not, you go flip through the big phone book (the page table), copy the answer onto your notepad, and continue. If the place isn't even in the phone book, you have to send for it from far away storage — that's the slow page fault.

Connections

Virtual Memory — the abstraction the TLB accelerates.
Page Tables (Multi-level) — what a TLB miss walks.
Cache Memory & Associativity — the TLB is a cache; same set/fully-associative ideas.
Page Faults & Demand Paging — what happens when the walk finds an invalid PTE.
Context Switching — why ASID/PCID and TLB flushes matter.
Huge Pages / TLB Reach — tuning the coverage of a single TLB entry.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, har baar jab CPU memory access karta hai, woh ek virtual address use karta hai, lekin RAM sirf physical address samajhti hai. Inko translate karne ke liye memory mein pada page table walk karna padta hai — matlab ek hi access ke liye kaafi extra memory accesses. Bahut slow! Isiliye CPU ke andar ek chhota, super-fast cache hota hai jise TLB kehte hain. Yeh recent VPN→PFN translations yaad rakhta hai. Address ka neeche wala hissa (offset) kabhi translate nahi hota — sirf page number wala upper hissa hota hai, isiliye TLB itna chhota reh sakta hai.

Jab TLB mein translation mil jaaye toh hit — turant physical address ban jaata hai: PFN ko offset bits jitna shift karo aur offset jod do. Agar na mile toh TLB miss. Yaad rakho: TLB miss ka matlab page fault nahi hai! Miss ka matlab sirf yeh ki translation cache mein nahi tha, lekin page table mein abhi bhi maujood hai — bas walk karke le aao (nanoseconds). Page fault tab hota hai jab page RAM mein hai hi nahi, disk se laana padta hai (milliseconds — bahut mehenga).

Miss handle karne ke do tarike: hardware-managed (x86, ARM — ek hardware walker khud page table walk karke TLB bhar deta hai) aur software-managed (MIPS — ek trap aata hai aur OS ka handler entry likhta hai). Context switch pe poora TLB flush na karna pade isliye har entry pe ASID/PCID tag lagta hai, taaki alag processes ki entries saath reh saken. Kernel pages ke liye Global bit hota hai.

Performance ka formula yaad rakho: $\text{EMAT} = t_{\text{TLB}} + t_m(1 + (1-h)k)$ . Yahan $h$ hit ratio hai aur $k$ page-table levels. 98% hit rate pe bhi har access 8% slow ho jaata hai — isiliye engineers TLB hit rate ko bahut high rakhne ki koshish karte hain, aur isiliye huge pages se TLB ka "reach" badhate hain. Yeh subtopic isliye important hai kyunki har single instruction isi translation pe depend karti hai.

TLB — structure, TLB miss handling

WHAT is a TLB?

HOW addresses split

Structure of a TLB

TLB lookup logic

TLB MISS handling — the heart of it

Step-by-step miss flow (hardware-managed)

Performance model

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections