Questions: Virtual Address Translation: Paging and TLBs

Question 1

A system uses 4 KB pages (12-bit offset) and 32-bit virtual addresses. A process references virtual address 0x00005200. The page table shows that virtual page 5 maps to physical frame 17. What is the physical address?

• A. 0x00005200 — virtual and physical addresses are the same after a TLB lookup
• B. 0x00011200 — frame 17 × 4096 + offset 0x200
• C. 0x00011000 — frame 17 × 4096, with the offset discarded after translation
• D. Cannot be determined without knowing whether the TLB contains this entry

Answer: (B)

With 4 KB pages, the bottom 12 bits are the offset (0x200 = 512). The upper bits form VPN = 5. The page table maps VPN 5 → frame 17. Physical address = (17 × 4096) + 0x200 = 0x11000 + 0x200 = 0x11200. The offset is preserved unchanged — it tells you where within the page the byte lives. The TLB state affects performance (hit vs. miss) but not the final physical address.

Question 2

Why do modern 64-bit operating systems use multi-level page tables instead of a single flat page table per process?

• A. Flat page tables cannot store permission bits like read/write/execute
• B. A flat page table for a 64-bit address space would require terabytes of memory per process, most of it wasted on unmapped regions
• C. Multi-level tables allow the TLB to cache more entries simultaneously
• D. Flat page tables only support 32-bit virtual addresses

Answer: (B)

A flat page table needs one entry per virtual page. A 64-bit address space with 4 KB pages has 2^52 possible pages — storing one 8-byte entry per page would require 32 petabytes per process. Multi-level page tables solve this by only allocating page table nodes for virtual address ranges the process actually uses. Unmapped regions (the vast majority of a 64-bit space) require no page table storage at all, making the structure sparse and practical.

Question 3

On a TLB hit, the CPU is expected to still access main memory once to verify the cached translation has not been invalidated.

• T. True
• F. False

Answer: False

The entire purpose of the TLB is to eliminate page table memory accesses for the common case. On a TLB hit, the cached virtual-to-physical translation is used directly in a single cycle — no main memory access is needed for address translation. If TLB entries required verification on every access, the performance benefit would be entirely lost. Entries are invalidated by the OS on context switches and explicit flushes; between invalidations, cached translations are trusted.

Question 4

The page offset portion of a virtual address is identical to the page offset in the resulting physical address.

• T. True
• F. False

Answer: True

Paging maps entire pages to entire frames of the same size. The offset specifies a byte position within the page, and since the whole page is relocated to a frame, that relative position is unchanged. Only the page number changes (VPN → PFN); the offset carries through unchanged. This is why the translation formula is always: physical address = (frame number × page size) + offset, with the offset preserved exactly.

Question 5

Why do TLB hit rates typically exceed 99% even though the TLB holds only a few dozen to a few hundred entries — a tiny fraction of a process's virtual address space?

Model answer: Programs exhibit strong spatial and temporal locality: they repeatedly access the same variables, loop through the same arrays, and call the same functions. At any moment, most memory accesses cluster in a small working set of pages. The TLB only needs to cache the currently active pages. Because the same pages are accessed over and over in tight loops, a small cache covering those few active pages achieves near-perfect hit rates even though the full address space is enormous.

This matters enormously for performance. Without a TLB, every memory access would require 3–4 additional memory reads to walk a multi-level page table — reducing effective memory bandwidth by 4–5×. With >99% hit rates, translation overhead is nearly zero. Programs with poor locality (random memory access patterns) suffer lower TLB hit rates and significant slowdowns — TLB 'thrashing' — analogous to cache thrashing but at the page-table level.