Memory management: paging and address translation

Goals and conventions

Translate a byte address, calculate page-table size, distinguish fragmentation types, and compute a simple TLB effective access time. Prerequisite: binary powers and integer division. All sizes use KiB=1024 bytes and MiB=2^20 bytes. Addresses and frame/page numbers start at zero. Unless stated otherwise, mappings are present and accessible, page-table entries have fixed size, and memory accesses do not fault.

1. Fixed boxes versus variable shelves

Imagine packing books into equal-sized numbered boxes. A logical sequence of books can occupy boxes placed on different shelves, while a catalogue tells you where each box is. Paging similarly divides virtual memory into fixed-size pages and physical memory into equally sized frames. A page table maps virtual page numbers to physical frame numbers; neighboring virtual pages need not occupy neighboring physical frames.

Fixed-size allocation can waste unused space inside an allocated frame: internal fragmentation. In a simple contiguous process allocation rounded to full pages, only the last page may be partly unused. With page size 1024 bytes, a 2500-byte allocation needs ceiling(2500/1024)=3 frames, occupying 3072 bytes and wasting 572 bytes. Do not use floor division for the frame count.

Variable-size contiguous allocation has a different problem: holes between allocations can be individually too small even when their total is sufficient. Holes of 3,5,4 KiB total 12 KiB, but none holds an unsplittable contiguous request of 6 KiB. This is external fragmentation. Basic paging avoids that requirement for a process's pages to occupy one contiguous run, but does not eliminate every kind of memory overhead or waste.

2. Split, map, recombine

For page size P and virtual byte address V:

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

The offset does not change. The table changes the page number into a frame number. If P=2^b, the low b bits are offset; with a v-bit virtual address, the high v−b bits identify the virtual page.

Worked example: P=1024, V=3589. Since 3589=3×1024+517, VPN=3 and offset=517. If VPN 3 maps to frame 11, the physical address is 11×1024+517=11781. Frame 11 starts at byte 11264; adding offset 517 stays within that frame. Do not multiply the whole virtual address by the frame number.

3. Address width and table size

Take 30-bit virtual byte addresses, 2 KiB pages, 26-bit physical byte addresses and 4-byte entries in a full single-level page table. A page holds 2^11 bytes, so offset has 11 bits. VPN has 30−11=19 bits, giving 2^19 virtual pages and entries. The complete table uses 2^19×4=2^21 bytes=2 MiB. Physical frame number has 26−11=15 bits. The page table's entry count is determined by virtual pages, not by physical frames in this conventional per-process table.

This is a fully allocated flat-table calculation. Sparse multilevel tables can omit unused lower-level tables; their size depends on populated regions and structure. A valid translation also needs permission checks. A page can be resident but not writable; residence alone does not authorize a write. Conversely, a TLB miss does not establish that the page is absent from RAM.

4. TLB: cache the translation

A translation lookaside buffer caches recent address translations. Think of a small desk card containing frequently used catalogue entries. A hit avoids reading the page table for that translation; it does not contain all of the requested application data merely because it contains a translation.

Worked timing model: lookup cost t=8 ns, memory access m=80 ns, hit rate h=0.95. Lookup is serial, a hit then requires one data-memory access, and a miss requires one page-table-memory access plus one data-memory access. There are no caches, page faults, multilevel walks or overlap. Hit time=t+m=88 ns. Miss time=t+2m=168 ns. Effective access time=0.95×88+0.05×168=92 ns. Always write the hit and miss paths before averaging; different overlap or page-table models give different formulas.

5. Segmentation check before addition

In a simple segmentation model an address is (segment,offset). Each segment has a base and a length limit. For zero-based offsets the legal test is 0≤offset<limit, then physical address=base+offset. If base=7000 and limit=600, offset 599 maps to 7599; offset 600 is outside. A limit interpreted as length differs from a highest-legal-offset convention, so read the question. Segments are variable-sized logical regions; pages are fixed-sized allocation units. Systems can combine them, so they are not universally mutually exclusive designs.

Common traps

Keep bytes separate from bits and entries. Use ceiling for required frames, division/remainder for address splitting, and the virtual width for flat page-table entry count. Keep internal and external fragmentation distinct. TLB miss, page fault and protection fault are different events; the access model determines which ones are possible.

Original practice: six single-correct MCQs

Choose exactly one option. Each question states its own required assumptions.

MM01. With 1 KiB pages, virtual byte address 3589 belongs to page 3 with offset 517. Page 3 maps to frame 11. What is the physical byte address?

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

Answer: A

A: 11×1024+517=11781.

B: The virtual address is not retained when the frame differs.

C: 11264 is the frame base; the offset is missing.

D: The translation requires frame size times frame number plus unchanged offset.

MM02. A full single-level page table covers a 30-bit virtual byte address space with 2 KiB pages and 4-byte entries. What is its size?

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

Answer: C

A: 512 Ki is the entry count, not the byte count.

B: This undercounts the four bytes per entry.

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

D: This doubles the correct table size.

MM03. An allocation of 2500 bytes is rounded up to whole 1024-byte frames. Ignoring all other overhead, how many allocated bytes are unused?

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

Answer: C

A: 452 is the used portion of the final frame.

B: 524 is not 3×1024−2500.

C: Three frames occupy 3072 bytes; 3072−2500=572.

D: The last frame is partly used, not entirely unused.

MM04. Serial TLB lookup takes 8 ns and each memory access 80 ns. Hit rate is 0.95; a hit needs one memory access after lookup, a miss needs two. No page faults or caches. What is effective time?

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

Answer: C

A: This omits lookup and miss costs.

B: 88 ns is the hit-only path.

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

D: 168 ns is the miss-only path.

MM05. A segment has base 7000 and limit interpreted as length 600 bytes, with zero-based offsets. Which access is invalid?

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

Answer: C

A: 0 is within [0,600).

B: 599 is the last legal offset.

C: 600 equals the length and lies outside [0,600).

D: 300 is within the segment.

MM06. Three free contiguous holes have sizes 3,5,4 KiB. A 6 KiB allocation must occupy one contiguous hole and cannot be split or compacted. Why can it fail despite 12 KiB total free?

A. External fragmentation B. Internal fragmentation within the new allocation C. Insufficient total free bytes D. TLB hit

Answer: A

A: No individual hole is at least 6 KiB.

B: The new allocation has not occurred; free space is separated between allocations.

C: Total 12 KiB exceeds 6 KiB; contiguity is the problem.

D: Translation-cache behavior does not combine holes.

Sources and scope

This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.

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

Sources checked 2026-10-14.