Memory management: paging और address translation

लक्ष्य और conventions

Byte address translate करें, page-table size निकालें, fragmentation के प्रकार अलग करें और simple TLB effective access time निकालें। पूर्वज्ञान: binary powers और integer division। KiB=1024 bytes, MiB=2^20 bytes। Addresses तथा page/frame numbers zero से शुरू हैं। अलग न कहा हो तो mappings present और accessible, entries fixed-size और accesses fault-free हैं।

1. समान boxes और बदलती shelves

किताबें समान आकार के numbered boxes में रखी हैं। Logical क्रम के boxes अलग shelves पर हो सकते हैं; catalogue उनकी जगह बताता है। Paging virtual memory को fixed-size pages और physical memory को समान आकार के frames में बाँटता है। Page table virtual page numbers को physical frame numbers से जोड़ती है। Neighboring virtual pages के physical frames adjacent होना जरूरी नहीं।

Allocated frame के अंदर unused जगह internal fragmentation है। Simple contiguous process allocation को पूरे pages तक round करने पर केवल आखिरी page अधूरा हो सकता है। Page=1024 bytes पर 2500-byte allocation को ceiling(2500/1024)=3 frames चाहिए। वे 3072 bytes लेते हैं, इसलिए 572 bytes waste। Frames की संख्या के लिए floor division न लें।

Variable-size contiguous allocation में holes का कुल space पर्याप्त होकर भी हर hole छोटा हो सकता है। 3,5,4 KiB holes कुल 12 KiB हैं, पर unsplittable contiguous 6 KiB request किसी में fit नहीं। यह external fragmentation है। Basic paging process के सभी pages के लिए एक contiguous run की जरूरत हटाता है; हर तरह का overhead या waste नहीं हटाता।

2. Split, map, recombine

Page size P और virtual byte address V के लिए:

VPN=floor(V/P), offset=V mod P, physical address=PFN×P+offset।

Offset नहीं बदलता। Table page number को frame number में बदलती है। P=2^b हो तो low b bits offset हैं; v-bit virtual address में high v−b bits VPN हैं।

हल किया उदाहरण: P=1024, V=3589। 3589=3×1024+517, इसलिए VPN=3, offset=517। VPN 3 frame 11 में map हो तो physical address=11×1024+517=11781। Frame 11 byte 11264 से शुरू है; offset जोड़ने पर address उसी frame में है। पूरे virtual address को frame number से multiply न करें।

3. Address width और table size

30-bit virtual byte addresses, 2 KiB pages, 26-bit physical byte addresses और full single-level page table की 4-byte entries लें। Page=2^11 bytes, इसलिए offset 11 bits। VPN=30−11=19 bits, इसलिए 2^19 virtual pages/entries। पूरी table=2^19×4=2^21 bytes=2 MiB। Physical frame number=26−11=15 bits। इस conventional per-process table में entries virtual pages से तय हैं, physical frames से नहीं।

यह fully allocated flat table का calculation है। Sparse multilevel tables में unused lower-level tables छोड़ी जा सकती हैं; size populated regions और structure पर निर्भर है। Translation के साथ permissions भी जाँचनी हैं। Page resident होकर भी writable नहीं हो सकता। Residence write की अनुमति नहीं। TLB miss भी page के RAM से absent होने का प्रमाण नहीं।

4. TLB: translation cache

Translation lookaside buffer हाल की translations रखता है। इसे desk पर रखी frequent catalogue entries की छोटी card-list समझें। Hit पर उस translation के लिए page-table read बचती है। Translation होने से application का पूरा data उसी में मौजूद नहीं हो जाता।

हल किया timing model: lookup t=8 ns, memory m=80 ns, hit rate h=0.95। Lookup serial है; hit के बाद एक data-memory access; miss के बाद एक page-table-memory और एक data-memory access। Caches, page faults, multilevel walks या overlap नहीं। Hit=t+m=88 ns; miss=t+2m=168 ns। Effective time=0.95×88+0.05×168=92 ns। Average से पहले दोनों paths लिखें; overlap या table model बदले तो formula भी बदलता है।

5. Segmentation: जोड़ने से पहले जाँचें

Simple segmentation में address=(segment,offset)। हर segment का base और length limit है। Zero-based offsets में legal test 0≤offset<limit है, फिर physical=base+offset। Base=7000, limit=600 पर offset 599 का address 7599; offset 600 बाहर है। Length limit और highest-legal-offset convention अलग हैं; प्रश्न पढ़ें। Segments variable-size logical regions और pages fixed-size units हैं। Systems दोनों मिला सकते हैं; वे हमेशा mutually exclusive नहीं।

सामान्य गलतियाँ

Bytes, bits और entries अलग रखें। Frames के लिए ceiling; address split के लिए quotient/remainder; flat table entries के लिए virtual width लें। Internal/external fragmentation अलग रखें। TLB miss, page fault और protection fault अलग events हैं; दिए access model से तय करें कौन संभव है।

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

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

MM01. 1 KiB pages में virtual byte address 3589, page 3 offset 517 है। Page 3 frame 11 में है। Physical byte address क्या है?

A. 11781 B. 3589 C. 11264 D. 5650

उत्तर: A

A: 11×1024+517=11781।

B: Frame अलग हो तो virtual address ज्यों का त्यों नहीं।

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

D: Frame number×size में unchanged offset जोड़ना है।

MM02. 30-bit virtual byte space, 2 KiB pages और 4-byte entries की full single-level table कितनी बड़ी है?

A. 512 KiB B. 1 MiB C. 2 MiB D. 4 MiB

उत्तर: C

A: 512 Ki entry count है, byte count नहीं।

B: चार bytes प्रति entry पूरी नहीं गिनी गईं।

C: 2^(30−11)×4=2^21 bytes=2 MiB।

D: यह सही size का दोगुना है।

MM03. 2500-byte allocation पूरे 1024-byte frames तक round होता है। अन्य overhead छोड़कर कितने allocated bytes unused हैं?

A. 452 B. 524 C. 572 D. 1024

उत्तर: C

A: 452 आखिरी frame का used हिस्सा है।

B: 524, 3×1024−2500 नहीं।

C: तीन frames=3072; 3072−2500=572।

D: आखिरी frame पूरा unused नहीं।

MM04. Serial TLB lookup 8 ns, memory access 80 ns, hit rate 0.95 है। Lookup के बाद hit में एक, miss में दो memory accesses हैं। Faults/caches नहीं। Effective time?

A. 80 ns B. 88 ns C. 92 ns D. 168 ns

उत्तर: C

A: Lookup और miss costs छूटे हैं।

B: 88 ns केवल hit path है।

C: 0.95×88+0.05×168=92 ns।

D: 168 ns केवल miss path है।

MM05. Segment base 7000, limit length=600 bytes, offsets zero-based हैं। कौन सा invalid है?

A. Offset 0 B. Offset 599 C. Offset 600 D. Offset 300

उत्तर: C

A: 0, [0,600) में है।

B: 599 आखिरी legal offset है।

C: 600 length के बराबर और [0,600) से बाहर है।

D: 300 segment के भीतर है।

MM06. Free contiguous holes 3,5,4 KiB हैं। 6 KiB allocation एक hole में चाहिए; splitting/compaction नहीं। कुल 12 KiB free के बावजूद failure क्यों?

A. External fragmentation B. नए allocation के अंदर internal fragmentation C. कुल free bytes कम हैं D. TLB hit

उत्तर: A

A: कोई hole कम-से-कम 6 KiB नहीं।

B: नया allocation हुआ नहीं; free space अलग holes में है।

C: 12 KiB, 6 KiB से अधिक है; समस्या contiguity है।

D: TLB holes नहीं जोड़ता।

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

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

• Official GATE 2026 CS syllabus, Section 8
• OSTEP: Paging Introduction
• OSTEP: Translation Lookaside Buffers

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