Foundations — Page tables and multi-level paging

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

Pehle aapko parent note Page Tables and Multi-Level Paging padne se pehle har symbol ka malik banana hoga. Yeh page har ek ko ground up se build karta hai: plain words → picture → topic ko iske zaroorat kyun hai. Upar se neeche padho; har idea uske upar waale pe lean karta hai.

1. "Bit" aur "power of two" — sab kuch ka alphabet

$n$ switches ek row mein lagao aur har switch independently flip ho sakta hai. Toh distinct patterns ki sankhya $2\times 2\times \dots$ ($n$ baar) hai:

Picture: socho ek car odometer, lekin har wheel pe sirf do symbols hain ($0,1$) das ki jagah. 3 wheels se tum $000,001,010,\dots ,111$ dikha sakte ho — yani $2^3=8$ distinct readings.

Topic ko iske zaroorat kyun hai: paging mein har "size" — kitne pages, page kitna bada, table entries kitni — power of two hai, kyunki woh kuch address bits se count hoti hai.

2. Bytes aur addresses — har locker ko ek number dena

Picture: identical mailboxes ki ek hallway, har ek pe ek chhoti number plate. Plate address hai; andar jo letter hai woh byte hai.

• $V=32$ ⇒ $2^{32}$ bytes = 4 GiB addressable space.
• $V=64$ ⇒ ek astronomically bada space (isliye flat tables mar jaate hain).

Topic ko iske zaroorat kyun hai: paging ka poora kaam ek address ko doosre mein badalna hai. $V$ batata hai "from" world kitna bada hai.

3. Virtual vs physical — fake number aur real number

Picture: do hallways side by side. Baayaan (virtual) woh hai jo program dekhta hai — clean, complete, sab uska apna. Daayaan (physical) real, shared, aadha-bhara building hai. Arrows left boxes se scattered right boxes ki taraf jaate hain.

Topic ko iske zaroorat kyun hai: iske bina, do programs dono "locker 5" chahenge toh clash hoga. Virtual addresses har program ko pretend karne dete hain ki woh sab kuch own karta hai, jabki physical reality shared aur safe rehti hai. Badi kahani ke liye Virtual Memory aur Address Space Layout dekho.

4. Pages aur frames — dono hallways ko equal blocks mein kaatna

Picture: figure s02 se dono hallways lo aur har $P$ boxes ke baad thick dividers draw karo. Har virtual block (page) ek physical block (frame) se map hota hai. Kyunki blocks same size hain, ek virtual page kisi bhi free frame mein ja sakta hai — jaise same-size bricks kisi bhi same-size slot mein fit hoti hain.

Topic ko iske zaroorat kyun hai: fixed equal-size blocks external fragmentation khatam karte hain aur address ke low bits ko untouchable banate hain — yeh do pillars hain jinpe baaki sab khada hai.

5. Address ko kaatna: page number | offset

Ab Section 4 ke dividers use karke ek single address ko do fields mein kaato.

Yeh do operations kyun?

• $\lfloor \text{addr}/P\rfloor$ (integer divide, remainder drop karo) jawaab deta hai "is address ke neeche $P$ ke kitne whole blocks fit hote hain?" — woh hi block number hai.
• $\text{addr}\mathrm{mod}P$ (bacha hua) jawaab deta hai "current block mein hum kitna andar hain?" — woh hi offset hai.

Picture: ek odometer jahan ek vertical line wheels ko split karti hai. Line ke baayein wheels = page number; daayein = offset. Offset wheels ghoomne se page-number wheels tab tak nahi hilte jab tak woh $P$ ke aage roll over nahi ho jaate.

Topic ko iske zaroorat kyun hai: translation sirf page number rewrite karta hai; offset verbatim copy hota hai. Yeh split hi poora engine hai.

6. Bit operations: masking &, shifting << >>, aur |

Upar ke formulas $\ll$, $\gg$, aur $\mathrm{mod}$ use karte hain jo computer pe real division se saste hain. Kyunki $P$ power of two hai, "divide" aur "remainder" pure bit surgery hai. (Poori detail Bit Manipulation and Masking mein.)

Topic ko iske zaroorat kyun hai: parent $(\text{PFN}\ll p)|\text{offset}$ aur $\text{addr}\mathrm{mod}P$ har jagah likhta hai. Yeh do tareekon se boli gayi same baat hai — powers of two division ko shifting bana deti hain.

7. Lookup table, entry, aur uske flags

Picture: ek spreadsheet. Row number = VPN (tum ise store nahi karte — yeh bas wahan hai jahan row baithti hai). Cell contents = PFN + flags. Index andar, value bahar.

Topic ko iske zaroorat kyun hai: "array position key hai, entry value hai" parent ki ek steel-manned galti hai. Agar tum table ko VPN se indexed nahi dekhte, toh multi-level walk ka kuch bhi samajh nahi aata.

8. "Level" aur base register — ek table tree kyun banta hai

$2^{20}$ rows wala ek single flat table ek real program ke liye mostly empty hota hai. Toh hum stages mein index karte hain: VPN ko khud slices mein kaato, aur har slice ko ek chhote tables ke tree ka ek level neeche jaane ke liye use karo.

Picture: ek table of contents (top table) chapters (inner tables) point karta hai, jo pages (frames) point karte hain. Tum sirf woh chapters print karte ho jo koi actually padh raha hai. Har level ek real RAM read maangta hai — yahi woh jagah hai jahan TLB baad mein apna kaam karta hai, bilkul waise jaise ek plain cache slow memory ko rescue karta hai.

Sab kuch topic se kaise connect hota hai

Equipment checklist

Jab upar ki har line obvious lagey, toh parent note padho — ya Hinglish version.