Multi-level page tables — why, overhead: Question bank

4.2.26 · D5 · Coding › Operating Systems › Multi-level page tables — why, overhead

Quick vocab refresher taaki neeche kuch bhi surprise na kare:

VPN = virtual page number, virtual address ka "kaun sa page" wala part.
PFN = physical frame number, "real RAM mein kaun sa slot" wala part.
PTE = page table entry, ek row jo PFN aur flags (present, dirty, ...) store karta hai.
L1 / directory = top table; L2 = doosra-level table jis pe yeh point karta hai.
Walk = ek address translate karne ke liye tree ke har level ko order mein read karne ki kriya.
TLB = recent VPN→PFN answers ka ek chhota cache.

True or false — justify

Multi-level page tables hamesha flat table se kam memory use karte hain.

False. Agar ek process apna poora address space touch kare, toh har L2 table waise bhi exist karni padegi, aur upar se ek extra directory page ka bhi cost aata hai — toh yeh thoda bada ho jaata hai. Saving tabhi aati hai jab table sparse ho.

Directory mein ek "not present" entry ka matlab hai ki RAM se ek specific page missing hai.

False. Ek not-present directory entry ka matlab hai ki poora L2 table (pages ka ek pura region) kabhi allocate hi nahi hua. Single page absent hone ka matlab hota hai leaf PTE level pe not-present hona.

Virtual address ko zyada levels mein split karne se aap jitna map kar sakte ho woh address space badh jaata hai.

False. Address space

V

se fixed hai, yaani virtual-address bits ki sankhya se. Splitting sirf same bits ko stages mein reorganise karta hai; yeh storage layout badalta hai, reach nahi.

k

-level table ke liye, har memory reference ko

k + 1

memory accesses lagte hain.

Practice mein False. Yeh

k + 1

cost sirf TLB miss pe aati hai. TLB hit pe PFN directly mil jaata hai, toh reference lagbhag ek access ka hota hai — jo achhi locality mein common case hai.

Page table ko 2-level ki jagah 3-level banana best-case memory footprint ko bada karta hai.

True. Har extra level kisi bhi used region ke path par ek mandatory top table aur add karta hai, toh "sirf ek page in use" ka minimum cost har level ke saath ek page badh jaata hai.

Translation ke dauran page offset bits transform hote hain.

False. Offset unchanged copy hota hai; sirf VPN (upar ke bits) lookup hota hai. Translation kaun sa page hai yeh replace karta hai, page ke andar kahan nahi.

Ek TLB multi-level walk ka cost permanently hata deta hai.

False. TLB miss pe abhi bhi poora

k

-level walk hota hai. Context switches, bade working sets, ya TLB flushes walk cost wapas le aate hain.

Agar do levels mein 10-10 bits hain, toh dono tables mein entries ki sankhya same honi chahiye.

True (entry count ke liye), lekin trap dhyaan se dekho.

2^{10} = 1024

entries each. Lekin woh alag tarah ki entries hold karte hain: L1 entries tables ki taraf point karti hain, L2 entries frames ki taraf.

Ek flat page table aur ek fully-populated multi-level table mein leaf PTEs ki sankhya same hoti hai.

True. Dono ko har virtual page ke liye ek leaf PTE chahiye; multi-level version sirf unke upar directory pages add karta hai. Leaf count identical hai.

Spot the error

"Address space

= page size \times number of levels

Galat. Bits add hote hain, sizes aise multiply nahi hote.

V = a + b + \dots + p

, aur address space hai

2^{V}

. Levels VPN ko split karne ke baare mein hain, space scale karne ke baare mein nahi.

"32-bit paging ke liye humne 10/10/12 choose kiya taaki directory jitni chhoti ho sake."

Galat reason. L2 ke liye 10 is liye choose kiya jaata hai taaki ek L2 table (

1024 \times 4 B = 4 KB

) exactly ek page mein fit ho, jisse allocate aur swap karna aasaan ho. Directory size baaki bachhe bits se naturally aati hai.

"Worst-case multi-level overhead

1024 \times 4 KB = 4 MB

hai, flat jaisa, toh dono barabar hain."

Ek term missing hai. Tum directory page bhool gaye:

4 KB + 4 MB \approx 4.004 MB

. Worst case mein yeh flat se thoda worse hai, barabar nahi.

"Har process ko multi-level ke saath bada page table milta hai, toh yeh RAM waste karta hai."

Galat. Real processes apne address space ka ek chhota sparse slice use karte hain, isliye lagbhag saare L2 tables kabhi create hi nahi hote — ek typical process ko megabytes nahi, tables ke kuch pages chahiye hote hain.

"2-level table par 98% TLB hit rate ke saath, average reference cost

3 \times 100 = 300 ns

hai."

Galat. Yeh sirf miss-only cost hai. Inhe blend karo:

0.98 (100) + 0.02 (300) = 104 ns

. TLB ka poora point yahi hai ki 3× cost rare ho.

"Ek not-present PTE aur ek invalid PTE same amount of memory waste karte hain."

Sloppy. Dono entries ek PTE slot occupy karti hain, lekin asli memory story yeh hai ki L2 table khud exist karti hai ya nahi. Sparsity savings poori tables skip karne se aati hai, individual entry flags se nahi.

Why questions

Ek flat table memory waste kyun karta hai jab yeh "sirf ek list" hai?

Kyunki yeh har possible virtual page ke liye ek PTE reserve karta hai, present ho ya na ho — ek 32-bit space

2^{20}

entries (

\approx 4 MB

) force karta hai chahe process sirf kuch dozen pages touch kare.

Multi-level sparsity ko savings mein kyun convert karta hai?

Ek unused region ek single "not present" directory entry mein collapse ho jaata hai, aur uska poora L2 table simply kabhi allocate hi nahi hota. Empty regions thousands ki jagah ek entry ka cost lete hain.

Hum deliberately ek L2 table ko exactly ek page mein fit karne ke liye size kyun karte hain?

Taaki OS ek page table ko allocate, free, aur swap kar sake usi machinery se jo woh ordinary pages ke liye use karta hai — koi special-case memory management nahi.

Deeper paging (jaise x86-64 ke 4 levels) performance kyun tabah nahi karta?

Kyunki locality translations ko TLB mein rakti hai, aur large pages walks ko chhota karte hain. 5-access worst case steady-state execution mein rare hai.

Time overhead ko "asli cost" kyun maana jaata hai, space nahi?

Space savings sparsity se guaranteed hain, lekin har level memory mein rehta hai aur tree walk karne ke liye read karna padta hai — ek access ko

k + 1

mein badal deta hai. Yahi latency hai jise TLB hide karne ke liye exist karta hai.

Inverted page tables exist kyun karte hain jab multi-level already space bachaa leta hai?

Inverted tables structure ko physical memory ke hisaab se size karti hain, per-process virtual space ke hisaab se nahi, isliye inki cost processes ki sankhya ke saath nahi badhti — yeh ek alag trade-off hai, strict improvement nahi.

Edge cases

Ek process jo exactly ek page touch karta hai: kitne page-table pages exist karte hain?

Do — ek directory (L1) aur ek L2 table. Yeh

8 KB

hai flat ke

4 MB

ke mukable, directory mein ek single not-present pattern se roughly 500× win.

Ek process jo apna poora address space use karta hai: flat se better hai ya worse?

Worse, lekin sirf thoda. Tumhe har L2 table plus extra directory page chahiye:

\approx 4.004 MB

4.000 MB

. Multi-level ke edge cases confirm karte hain ki yeh sirf sparse hone pe jeetता hai.

TLB hit rate 0 ho jaaye (flush ke baad cold cache): har reference ka cost kya hai?

Har reference pe poora walk:

k + 1

accesses. 2-level table ke liye yeh TLB warms up hone tak har reference pe 3 memory accesses hai.

Zero-sized PTE ya ek level par zero index bits — kya yeh meaningful hai?

Nahi. Zero index bits wala level kuch nahi karta (yeh sirf ek entry address kar sakta hai), aur zero-size PTE ek PFN store nahi kar sakta. Har level mein

\geq 1

index bit hona chahiye aur PTEs itni wide honi chahiye ki ek frame number plus flags hold ho sake.

Woh boundary kya hogi jahan ek used region do directory entries mein span karta hai?

Dono directory entries present ho jaati hain aur har ek ko apna L2 table milta hai. Boundary ke paas split hone wale region ka cost do L2 tables hai chahe boundary ke paas sirf kuch hi pages actually used hon.

Agar page size double ho jaaye (bade pages), toh levels ki zaroorat pe kya hoga?

Zyada offset bits (

p

badhta hai), isliye VPN bits split karne ke liye kam bachte hain — tumhe fewer levels ki zaroorat pad sakti hai, aur har L2 table abhi bhi ek (ab bada) page mein fit hota hai. Large pages walks chhote karne ka standard tarika hain.

Recall Ek-sentence self-test

Agar tum explain kar sako kyun "multi-level hamesha memory save karta hai" false hai, kyun offset kabhi nahi badlta, aur kyun TLB miss poori walk cost wapas laata hai — toh yeh topic tumhara hai. Saari memory savings actually kahaan se aati hain? ::: Unused (sparse) regions ke liye L2 tables kabhi allocate na karne se, tree structure se nahi.

Connections

Multi-level page tables — why, overhead (parent — yahan har trap ke peeche ki derivations)
Paging — basics and address translation
TLB — translation lookaside buffer
Virtual Memory & Demand Paging
Inverted Page Tables
x86-64 4-level paging
Locality of Reference