Multi-level page tables — why, overhead

WHY do we even need this?

WHAT goes wrong? Let's compute the size of a flat table.

HOW multi-level fixes it

Figure — Multi-level page tables — why, overhead

Formula Splitting the virtual address — derived

For a 2-level scheme with page size $2^{p}$ : $\underbrace{V}_{\text{total}} = \underbrace{a}_{\text{L1 index}} + \underbrace{b}_{\text{L2 index}} + \underbrace{p}_{\text{offset}}$

Why pick $a,b$ this way? We usually want each second-level table to fit in exactly one page so it's easy to allocate/swap.

Entries per page = $\dfrac{2^p}{E}$ ⇒ index bits per level $b = \log_2\!\frac{2^p}{E} = p - \log_2 E$ .

Worked for 32-bit, 4KB, 4B PTE:

$p=12$ , $\log_2 E = 2 \Rightarrow b = 10$ . Each table holds $2^{10}=1024$ entries (fits 4KB).
Remaining for L1: $a = 32 - 10 - 12 = 10$ ⇒ directory has $2^{10}=1024$ entries.
So $32 = 10 + 10 + 12$ . Why? All bits must be accounted for: directory + table + offset.

Overhead: space vs time

Formula Space overhead — best and worst case

Each table is $2^{10}\times 4 = 4\text{KB}$ .

Best case (tiny program touching 1 page): $1\ \text{directory} + 1\ \text{L2 table} = 4\text{KB}+4\text{KB}=8\text{KB}$ vs 4 MB flat — a ~500× saving. Why? All other directory entries say "not present"; their L2 tables don't exist.

Worst case (every page used): $\underbrace{4\text{KB}}_{\text{L1}} + \underbrace{1024\times 4\text{KB}}_{\text{all L2}} = 4\text{KB}+4\text{MB} \approx 4.004\text{MB}$ Why slightly bigger than flat? We pay an extra directory page on top of all the leaf tables. Multi-level is only a win when the table is sparse — which it almost always is.

Formula Time overhead — the real cost

A $k$ -level table needs $k$ memory accesses to walk the tree before the real access: $\text{accesses per reference} = \underbrace{k}_{\text{walk}} + \underbrace{1}_{\text{actual data}}$ For 2-level that's 3 memory accesses instead of 1. Why? Each level is in memory and must be read.

The fix: a TLB (Translation Lookaside Buffer) caches recent VPN→PFN translations, so most references skip the walk entirely: $\text{EAT} = h\cdot(t_{\text{TLB}}+t_{\text{mem}}) + (1-h)\cdot\big((k{+}1)\,t_{\text{mem}}+t_{\text{TLB}}\big)$ where $h$ = TLB hit rate. With $h \to 1$ , multi-level's walk cost nearly vanishes.

Common mistakes

Flashcards

Why is a single-level page table wasteful for a 32-bit space?

It needs one PTE per virtual page (

2^{20}

entries = 4MB per process) even though most pages are unused.

Size formula for a single-level table?

2^{V-p}\times E

bytes, where

V

=addr bits,

p=\log_2(\text{page size})

E

=PTE size.

Why does multi-level save space?

Unused regions are a single "not present" entry in the directory, so their second-level tables are never allocated (sparsity → savings).

How do you split a virtual address for

k

levels?

Add the bits:

V = (\text{L1 bits})+\dots+(\text{Lk bits})+ p

(offset).

Why choose 10/10/12 for 32-bit, 4KB, 4B PTE?

So each second-level table (1024×4B = 4KB) fits exactly in one page; remaining bits go to directory and offset.

Time cost of a

k

-level table per memory reference?

k+1

accesses (

k

for the walk, 1 for the data) — without a TLB.

What hardware hides the walk cost?

The TLB, which caches VPN→PFN; a hit skips the page-table walk.

Worst-case space vs single-level?

Slightly larger — you add directory page(s) on top of all leaf tables; multi-level only wins when sparse.

EAT formula with TLB hit rate

h

h(t_{TLB}+t_{mem}) + (1-h)((k{+}1)t_{mem}+t_{TLB})

Recall Feynman: explain to a 12-year-old

Imagine a giant hotel with a million rooms, and one huge guest list with a line for every room — even empty ones. That list is enormous and mostly blank. Instead, we keep a small floor directory: "Floor 3 has guests, here's its list; Floor 4 is empty — no list at all." To find a person you check the floor directory, then that floor's small list. You only keep lists for floors that actually have people. Looking someone up takes a couple of extra steps, so we keep a sticky-note (the TLB) of the people we looked up recently to go faster.

Connections

Paging — basics and address translation
TLB — translation lookaside buffer
Virtual Memory & Demand Paging
Inverted Page Tables (the opposite trade-off: size by physical memory)
x86-64 4-level paging
Locality of Reference (why TLBs and sparsity work)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, problem yeh hai: ek 32-bit process ke paas 4GB virtual space hota hai. Agar hum ek hi flat page table banayein, toh har page ke liye ek entry chahiye — total $2^{20}$ entries, yaani 4MB sirf table ke liye, har process ke liye! Aur sach yeh hai ki process apne space ka bahut chhota hissa hi use karta hai, baaki table khaali padi rehti hai. Yeh memory ka waste hai.

Multi-level page table is waste ko khatam karta hai. Hum virtual address ke bits ko todte hain: upar ke bits directory (L1) ko index karte hain, beech ke bits second-level table (L2) ko, aur neeche ke bits offset hote hain. Agar koi region use hi nahi ho raha, toh directory mein bas "not present" likh do — uska L2 table banane ki zaroorat hi nahi. Isi sparsity se memory bachti hai. 32-bit ke liye split hota hai 10+10+12, taaki har L2 table exactly ek 4KB page mein fit ho jaye.

Lekin har cheez free nahi hoti. Ab ek address translate karne ke liye 2 extra memory reads lagte hain (L1, L2), phir actual data read — total 3 accesses ek ke badle. Yeh time overhead hai. Iska solution hai TLB: yeh recent translations ka cache hai. Agar TLB hit ho gaya, toh walk skip ho jaata hai aur speed wapas aa jaati hai. Isiliye locality important hai — agar program same pages baar-baar touch karta hai, TLB hit rate high rehta hai aur overhead almost zero ho jaata hai.

Yaad rakho: multi-level space bachata hai sirf jab table sparse ho. Agar pura space use ho, toh thoda zyada memory lagti hai (extra directory). Real life mein space hamesha sparse hota hai, isliye yeh approach jeet jaati hai — x86-64 toh 4 levels use karta hai!

Multi-level page tables — why, overhead

WHY do we even need this?

HOW multi-level fixes it

Overhead: space vs time

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Operating Systems

Connections