Multilevel page tables और sparse address spaces

लक्ष्य और conventions

Two-level address split बनाएँ, केवल जरूरी lower-level tables गिनें और metadata को application data से अलग रखकर page-walk cost निकालें। पूर्वज्ञान: memory-management पाठ का page/offset तथा flat-table arithmetic। Byte addressing, KiB=2^10, MiB=2^20, zero-based indices और conventional per-process two-level table लेते हैं। Page-table blocks RAM में resident हैं; requested mappings valid और permitted हैं। Main model में huge pages, inverted tables या translation faults नहीं।

1. Optional volumes वाला catalogue

एक विशाल catalogue हर संभावित book के लिए line रखे, भले shelves खाली हों। Optional volumes की directory खाली sections की volumes allocate किए बिना काम कर सकती है। Multilevel page table भी top-level directory रखती है और mapping वाले virtual regions के लिए ही lower tables बनाती है। Absent directory entry पूरा region unmapped बता सकती है। Sparse spaces में metadata बचता है; offset नहीं बदलता और application data free नहीं हो जाता।

Tradeoff: translation-cache miss पर लंबा walk। Fully populated space में upper levels extra metadata हैं, इसलिए हमेशा space नहीं बचता। एक mapped data page के लिए हमेशा अलग leaf table नहीं चाहिए: पास के कई virtual pages एक table share करते हैं।

2. Bit split निकालें

32-bit virtual byte addresses, 4 KiB pages, 4-byte directory entries और 4-byte leaf entries लें। हर page-sized table में 4096/4=1024=2^10 entries। Offset 12 bits। VPN bits=32−12=20, जिन्हें 10 directory और 10 leaf bits में बाँटते हैं। High-to-low layout: directory[10] | leaf[10] | offset[12]। 4-byte entry size उसका storage है, चार-bit frame number नहीं।

एक leaf 1024 pages यानी 1024×4096=4 MiB virtual region map करती है। Directory में 1024 entries, total coverage=1024×4 MiB=4 GiB=2^32 bytes। Coverage और अपना size अलग हैं: leaf 4 KiB लेती है पर 4 MiB region बताती है।

3. दोनों levels का translation

Virtual address 0x0040307A, decimal 4,206,714 लें। 4096 से divide: VPN=1027, offset=122 (0x07A)। VPN को 1024 से divide: directory index=1, leaf index=3। पहले directory entry 1 से leaf table खोजें, फिर उस table की entry 3 से data frame। यदि physical frame 9 मिले तो data address=9×4096+122=36,986।

Directory entry का frame page-table page दिखाता है, जरूरी नहीं कि वही final data frame हो। पहले level के result से सीधे application address बनाना leaf lookup छोड़ देता है। Physical frame number को virtual index समझना भी गलत है। हर level की भूमिका अलग रखें।

4. Sparse tables: directory index से groups बनाएँ

केवल virtual pages {0,1,1023,1024,2048} mapped हैं। Implementation सिर्फ जरूरी leaves और एक root allocate करता है। floor(VPN/1024) निकालें: 0,1,1023 का directory index 0; page 1024 का 1; page 2048 का 2। इसलिए तीन leaves, पाँच नहीं। Metadata=एक root+तीन leaves=4×4096=16384 bytes=16 KiB। पाँच data pages अलग से 20 KiB। बाकी structures छोड़कर table+data=36 KiB।

उसी virtual width की full flat table=2^20 entries×4=4 MiB, भले सिर्फ पाँच pages mapped हों। यहाँ multilevel का लाभ sparsity है। सभी 1024 leaves allocate हों तो metadata=1025×4096=4,198,400 bytes=4 MiB+4 KiB, flat से थोड़ा अधिक। इसलिए “multilevel हमेशा कम memory” गलत है।

4 MiB boundary पार करता छोटा region भी दो leaves माँग सकता है। Pages 1023,1024 adjacent होकर अलग directory entries लेते हैं। केवल mapped-page count को 1024 से divide/round करने की बजाय distinct higher-level indices गिनें।

5. Walk cost और TLB hits

TLB के अलावा relevant caches नहीं मानें। TLB hit final translation देकर एक data-memory access माँगती है। Miss में directory, leaf, data: तीन accesses। Root-table address register से ज्ञात है; उसे लेने की extra memory read न गढ़ें। Tables स्वयं fault कर सकती हों तो यह simple model पर्याप्त नहीं।

हल किया timing: serial lookup 5 ns, memory read 100 ns, hit rate 0.9। Hit=5+100=105 ns; miss=5+3×100=305 ns। Effective=0.9×105+0.1×305=125 ns। पिछला single-level formula जस का तस नहीं लग सकता, क्योंकि अब miss दो table levels traverse करती है। Hardware walk caches/overlap cost बदल सकते हैं; arithmetic question के model पर करें।

6. अलग structures, अलग counts

Conventional per-process table virtual pages के आधार पर entries रखती है। Inverted page table physical frames पर organize होती है और owning address-space/page की पहचान तथा hashing जैसी lookup व्यवस्था चाहिए। इस पाठ की conventional virtual-indexed table को physical-frame count से size न करें। Huge/mixed pages से offset/coverage भी बदलते हैं; उन्हें यहाँ चुपचाप नहीं मानते।

परीक्षा checklist

Table entries=block bytes/entry bytes निकालें। Address bits को levels और offset में बाँटें। Sparse tables में occupied index prefixes गिनें, root एक बार लें, table pages/data pages अलग रखें। Average से पहले miss path की हर access लिखें और residency/cache assumptions बताएँ।

मौलिक अभ्यास: छह single-correct MCQ

हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।

PT01. 32-bit virtual byte address, 4 KiB pages और दोनों levels की page-sized tables में 4-byte entries हैं। Directory/leaf/offset split?

A. 12/10/10 B. 10/10/12 C. 8/12/12 D. 10/12/10

उत्तर: B

A: 4 KiB page को 12 offset bits चाहिए, 10 नहीं।

B: 4096/4=1024 entries: हर level 10 bits; offset 12।

C: 4 KiB में 4-byte entries 1024 हैं, 4096 नहीं।

D: 10-bit offset 1 KiB बताता है, 4 KiB नहीं।

PT02. Leaf में 1024 entries, प्रत्येक एक 4 KiB virtual page map करती है। Coverage कितना?

A. 4 KiB B. 1 MiB C. 4 MiB D. 4 GiB

उत्तर: C

A: 4 KiB leaf का अपना storage हो सकता है, coverage नहीं।

B: 1024×4 KiB इससे अधिक है।

C: 1024×4096=2^22 bytes=4 MiB।

D: 4 GiB सभी 1024 leaves का coverage है।

PT03. हर leaf में 1024 entries, हर table 4 KiB। केवल VPN 0,1,1023,1024,2048 mapped हैं। एक root और जरूरी leaves ही allocate हों। Metadata कितना?

A. 12 KiB B. 16 KiB C. 20 KiB D. 24 KiB

उत्तर: B

A: 12 KiB तीन leaves गिनता है, root छोड़ता है।

B: Indices 0,0,0,1,2: तीन leaves+root=16 KiB।

C: 20 KiB पाँच data pages हैं, metadata नहीं।

D: 24 KiB हर data page की अलग leaf मानता है।

PT04. 4 KiB pages, split 10/10/12; virtual 0x0040307A, directory 1/leaf 3 से frame 9 map है। Physical byte address?

A. 36986 B. 4206714 C. 36864 D. 12410

उत्तर: A

A: Offset=0x07A=122; 9×4096+122=36986।

B: यह मूल virtual address है।

C: 36864 frame 9 base है; offset छूटा।

D: 12410 leaf index 3 को mapped frame मानता है।

PT05. Serial TLB lookup=5 ns, RAM read=100 ns, hit rate=0.9। Hit में एक data read; two-level miss में directory,leaf,data reads। अन्य cache/fault नहीं। Effective time?

A. 105 ns B. 115 ns C. 125 ns D. 305 ns

उत्तर: C

A: 105 ns केवल hit path।

B: 115 ns one-level 205 ns miss से आता है।

C: 0.9×105+0.1×305=125 ns।

D: 305 ns केवल miss path।

PT06. Two-level में एक 4 KiB root और सभी 1024 leaves, प्रत्येक 4 KiB allocated हैं। 4 MiB flat table के मुकाबले metadata कितना?

A. ठीक 4 MiB B. 4 MiB और 4 KiB C. केवल 4 KiB D. 4 MiB से 4 KiB कम

उत्तर: B

A: Extra root छूट गया।

B: 1024 leaves=4 MiB; root अतिरिक्त 4 KiB।

C: केवल root गिना।

D: Root metadata जोड़ता है, घटाता नहीं।

स्रोत और दायरा

यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।

• Official GATE 2026 CS syllabus, Section 8
• OSTEP: Advanced Page Tables
• OSTEP: Translation Lookaside Buffers

स्रोत जाँचे गए: 2026-10-14।