Page tables and multi-level paging: Question bank — Hinglish deep dive

5.4.13 · D5 · Hardware › Memory Hierarchy & Caches › Page tables and multi-level paging

Intuition Is bank ko kaise use karein

Yeh parent note ka concept-trap child hai. Har line mein pehle ek question hai, phir :::, phir answer. Right side ko cover karo, apni reasoning poori sentences mein zor se bolo, phir reveal karo. Agar tumhara answer sirf "yes/no" tha bina kisi why ke, toh tum galat ho — yahan poora point justification dena hai.

Shuru karne se pehle, yeh words solid lagane chahiye (parent se build karo agar nahi hain): page virtual address space ka ek fixed-size block hai; frame physical RAM ka same-size block hai; VPN (virtual page number) address ke high bits hain jo batate hain kaun sa page hai; offset low bits hain jo page ke andar ek byte identify karte hain; PTE (page table entry) ek row hai jisme PFN (physical frame number) plus flags stored hote hain. Agar inme se kuch bhi fuzzy lag raha hai, pehle Virtual Memory aur Address Space Layout revisit karo.

True or false — justify

Har line ke liye: true/false decide karo, phir ek saanth mein explain karo.

A flat (single-level) page table is smaller than a two-level table for a process using all of its address space.

True — agar har page use ho raha hai, toh tree overhead add karta hai (inner-table pointers, extra top table) bina kisi empty branch ke prune karne ke, isliye flat table zyada lean hota hai. Tree tabhi jeetता hai jab address space sparse ho.

Multi-level paging ek single translation ko flat table se faster banata hai.

False — har level ek extra sequential RAM read hai, isliye walk slower hota hai, faster nahi. Tree memory savings deta hai; TLB speed wapas dilata hai.

Translation ke dauran offset field transform hoti hai.

False — kyunki ek page aur ek frame ka same size

P

hota hai, page ke andar byte

k

uske frame ke andar bhi byte

k

hi hota hai, isliye low

p = lo g_{2} P

bits verbatim copy hote hain. Sirf page/frame number badalta hai.

Multi-level table ka har level poore VPN se index karta hai.

False — VPN ko disjoint slices mein partition kiya jaata hai, ek per level. Level 1 sirf apna slice

i_{1}

use karta hai, level 2 sirf

i_{2}

use karta hai, aur aise hi; koi bhi level poora VPN nahi dekhta.

Ek page table entry woh virtual page number store karta hai jisse woh map karta hai.

False — VPN array position se implicitly encoded hota hai (index se). Entry mein sirf PFN plus flags stored hote hain. Position key hai, contents value hai.

Levels ki sankhya badhana hamesha memory bachata hai.

False — zyada levels tabhi help karte hain jab address space sparse ho. Dense-use space ke liye, extra levels table overhead add karte hain. Ek sweet spot hota hai; blindly levels add karne se memory cost ho sakti hai aur walk time bhi definitely badhta hai.

Do processes safely ek hi physical frame share kar sakti hain jab dono ke alag page tables hon.

True — har process ki PTE same PFN ko point kar sakti hai, jisse shared memory ya shared libraries milti hain. Isolation isi mein hai ki kaun se pages har table expose karta hai, frames mein nahi.

Agar page 4 KiB ka hai, toh offset hamesha 12 bits ka hoga chahe address width kuch bhi ho.

True — offset ek page ke andar bytes count karta hai, isliye yeh sirf page size par depend karta hai:

p = lo g_{2} 4096 = 12

. Address width

V

sirf yeh change karta hai ki VPN ke liye kitne bits bache hain.

Bada page size page-table size ko reduce karta hai.

True — bade pages ka matlab hai describe karne ke liye kam pages, isliye kam PTEs (zyada offset bits, kam VPN bits). Trade-off hai coarser granularity aur zyada internal fragmentation (partly-used pages ke andar waste hue bytes).

TLB memory se data store karta hai.

False — TLB VPN → PFN translations cache karta hai, actual data bytes nahi. Data data cache / RAM mein rehta hai; TLB sirf batata hai kahaan hai.

Spot the error

Har statement mein ek flaw hai. Use naam do aur correct karo.

"Translate karne ke liye, address ke high bits ko mask off karo aur low bits ko table mein look up karo."

Ulta hai — tum low bits (offset) ko unchanged rakhte ho aur high bits (VPN) ko translate karte ho. Correct approach yeh hai: table ko VPN se index karo, phir unchanged offset append karo. Dekho Bit Manipulation and Masking.

"Physical address PFN times VPN ke barabar hota hai."

Galat operation — physical address

(PFN \times P) + offset

hota hai, yaani (PFN << p) | offset. VPN sirf PFN dhundhne ke liye use hota hai; yeh final address arithmetic mein kabhi appear nahi karta.

"10/10/12 split ke saath, har inner table mein 4 KiB worth of entries hoti hain kyunki 10 bits 4096 entries address karte hain."

Miscount — 10 index bits

2^{10} = 1024

entries address karte hain, 4096 nahi. 4 bytes each par yeh

1024 \times 4 = 4

KiB hota hai, jo ek page ke barabar hota hai — reasoning sahi size par pahunchti hai lekin galat entry count ke zariye.

"Ek invalid PTE phir bhi ek real frame ko point karta hai; OS sirf ise use karne se refuse karta hai."

Galat — ek invalid PTE kuch bhi point nahi karta; uska PFN field meaningless hai aur koi frame allocated nahi hai. Aisa page touch karna ek page fault trigger karta hai, jo phir ek frame allocate kar sakta hai.

"TLB miss ka matlab hai data memory mein nahi hai, isliye yeh page fault cause karta hai."

Do mechanisms ko confuse kar raha hai — TLB miss ka sirf yeh matlab hai ki translation cached nahi thi; phir tum page table walk karte ho. Page fault tabhi hota hai jab walk ek invalid PTE dhundhe. Valid mapping par TLB miss sirf walk karta hai aur aage badh jaata hai.

"Kyunki top-level table mein 1024 entries hain, ek two-level scheme zyada se zyada 1024 pages map kar sakta hai."

Galat — 1024 top entries mein se har ek ek full inner table ki taraf point karti hai jisme aur 1024 entries hain, isliye reach

1024 \times 1024 = 2^{20}

pages hai. Tum levels ko multiply karte ho, add nahi.

Why questions

Sirf fact nahi, reason ke saath jawab do.

Ek tiny program ke liye bhi flat 32-bit page table 4 MiB kyun cost karta hai?

Kyunki flat table har possible page ke liye ek entry reserve karta hai (

2^{20}

entries × 4 B), chahe page use ho ya na ho. Yeh unused ranges skip nahi kar sakta — yahi exactly woh flaw hai jise tree fix karta hai.

4 KiB itna common page size kyun hai?

4-byte PTEs ke saath, ek 4 KiB table exactly

2^{10} = 1024

entries hold karta hai, aur ek 10-bit index exactly ek page fill karta hai — isliye har table perfectly ek frame mein fit hota hai, jisse allocation aur alignment simplify hoti hai.

Page-table base (jaise x86 CR3) ek physical address kyun hona chahiye?

Kyunki base translation ka hi starting point hai — agar yeh virtual hota, toh ise dhundhne ke liye pehle se ek translation chahiye hoti, jo ek infinite regress hai. Translation ko ek physical anchor par bottom out karna zaroori hai.

Sparse address space tree ko itni memory kyun save karne deta hai?

Kyunki unused top-level entries invalid mark hoti hain aur kisi inner table ko point nahi karti —

2^{v_{2}}

potential entries ka poora subtree simply allocate hi nahi hota. Tum sirf un branches ke liye pay karte ho jinhe tum actually walk karte ho.

Ek level add karna per translation memory reads ko multiply kyun karta hai?

Har level RAM mein rehta hai, aur tumhe ek level read karna hota hai next ka address jaanne ke liye. Reads strictly sequential hain (ek dependency chain), isliye

n

levels ka matlab hai

n

reads pehle data touch karne se.

TLB ko offset store karne ki zaroorat kyun nahi?

Kyunki offset kabhi translate nahi hota — yeh unchanged ride karta hai. TLB sirf woh part cache karna chahta hai jo badhta hai: VPN → PFN. Offset baad mein reattach hota hai.

Alag processes mein do virtual addresses same VPN par map ho sakte hain lekin different physical frames par kyun?

Kyunki har process ki apni page table hoti hai; same VPN alag tables mein different PFNs hold karti hain. Yahi exactly isolation ka kaam hai — identical virtual layouts, disjoint physical backing.

Edge cases

Woh boundary aur degenerate scenarios jo yeh topic quietly assume karta hai ki tum handle karoge.

Virtual address 0 ka "page number" kya hai?

VPN 0, offset 0 — yeh pehle page ka pehla byte hai. Translation mein kuch bhi special nahi; lekin bahut se systems deliberately page 0 ko unmapped rakhte hain taaki null pointer dereference fault kare.

Ek page ke last byte par, offset

P - 1

par, kya hota hai?

Woh theek se translate hota hai — offset

P - 1

maximum in-page offset hai aur phir bhi

p

offset bits mein fit hota hai. Agla byte offset 0 par next VPN mein roll karta hai, jo possibly alag (ya unmapped) frame hai.

Agar page size poore address space ke barabar ho, toh kitne levels chahiye?

Zero page-number bits bachte hain — poora address offset hai, isliye exactly ek page hai aur koi translation table ki zaroorat nahi. Paging ki degenerate limit.

Agar page size 1 byte hoti, toh kya hota?

Phir

p = 0

hota: koi offset nahi, har byte apna page hai, aur VPN poora address hai — table memory jitna bada ho jaata. Yahi wajah hai ki tiny pages absurd hain; yeh dikhata hai ki offset ka poora purpose ek PTE ko bahut saare bytes par amortize karna hai.

Jab mid-level (final nahi) PTE invalid ho toh walk kya karta hai?

Yeh turant ruk jaata hai aur page fault raise karta hai — descend karne ke liye koi inner table nahi hai, isliye us entry ke neeche poora subtree absent hai. Tum kabhi final level tak nahi pahunchte.

Kya same physical frame ek page table mein do baar appear ho sakta hai (do VPNs → ek PFN)?

Haan — yeh aliasing hai, shared memory ya copy-on-write ke liye use hota hai. Yeh legal hai lekin dhyan zaroori hai: ek VPN se write dusre se visible hota hai, aur caches ko ek frame ke do virtual names handle karne honge.

Agar kisi virtual address ke high bits top table ke valid part ke baad index karein toh kya hoga?

Real hardware par index simply ek top-level entry select karta hai jo invalid mark hoti hai (ya 64-bit par address non-canonical reject hota hai). Dono taraf se translation fault ke saath fail hoti hai — koi "out of bounds" wraparound nahi hota.

Active Recall

Multi-level paging time ya space optimize karta hai?

Space — yeh unused ranges ke liye tables allocate karne se bachata hai, lekin per walk zyada memory reads ki cost par.

Translation ke dauran offset bits kahaan jaati hain?

Yeh physical address mein verbatim copy hoti hain; sirf VPN → PFN part translate hota hai.

PTE par kya stored hota hai versus uski position se kya encoded hota hai?

Position VPN encode karti hai (implicit key); entry PFN plus flags store karti hai (value).

Multi-level walk se khoi speed kya recover karta hai?

TLB, jo recent VPN → PFN mappings cache karta hai taaki zyaatar translations walk skip kar sakein.

Page-table base register physical address kyun hold karta hai?

Warna ise translate karne ke liye khud ek translation chahiye hoti — infinite regress; translation ko physical memory par anchor karna zaroori hai.