Loading learning content...
We've explored each component of address translation: page number extraction, offset extraction, frame lookup, and physical address formation. Now it's time to synthesize this knowledge through comprehensive worked examples.
These examples go beyond simple calculations—they explore real-world scenarios, edge cases, multi-level page tables, performance implications, and the kind of reasoning expected from systems engineers. By working through these examples, you'll develop the intuition to analyze any address translation scenario.
By the end of this page, you will have practiced complete address translations with various parameters, analyzed multi-level page table walks, calculated effective access times with TLB considerations, handled edge cases and boundary conditions, and developed the skills to perform these calculations confidently on any paging system.
Let's start with fundamental examples using 32-bit addresses and 4KB pages—the classic configuration for understanding paging.
System Parameters:
╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 1: Basic Translation ║╠════════════════════════════════════════════════════════════════════╣║ Given: ║║ Virtual Address: 0x00008A4C ║║ Page Table Entry for Page 8: Contains Frame Number 0x2F1 ║║ Page Size: 4 KB ║╠════════════════════════════════════════════════════════════════════╣║ Step 1: Convert to Binary ║║ ║║ 0x00008A4C = 0000 0000 0000 0000 1000 1010 0100 1100 ║║ |——————— Page # ———————| |—— Offset ——| ║║ 20 bits 12 bits ║╠════════════════════════════════════════════════════════════════════╣║ Step 2: Extract Page Number ║║ ║║ Page Number = VA >> 12 ║║ = 0x00008A4C >> 12 ║║ = 0x00008 ║║ = 8 (decimal) ║║ ║║ Verification: 8 × 4096 = 32,768 = 0x8000 (page base) ║╠════════════════════════════════════════════════════════════════════╣║ Step 3: Extract Offset ║║ ║║ Offset = VA & 0xFFF ║║ = 0x00008A4C & 0x00000FFF ║║ = 0x00000A4C ║║ = 2636 (decimal) ║║ ║║ Verification: 2636 < 4096 ✓ ║╠════════════════════════════════════════════════════════════════════╣║ Step 4: Page Table Lookup ║║ ║║ PageTable[8] = Frame 0x2F1 ║║ Frame Number = 0x2F1 = 753 (decimal) ║║ Frame Base = 753 × 4096 = 3,084,288 = 0x002F1000 ║╠════════════════════════════════════════════════════════════════════╣║ Step 5: Form Physical Address ║║ ║║ Physical = (Frame << 12) | Offset ║║ = (0x2F1 << 12) | 0xA4C ║║ = 0x002F1000 | 0x00000A4C ║║ = 0x002F1A4C ║╠════════════════════════════════════════════════════════════════════╣║ Result: ║║ ║║ Virtual: 0x00008A4C ───────────────→ Physical: 0x002F1A4C ║║ │ │ ║║ Page 8, Offset 2636 Frame 753, Offset 2636 ║║ ║║ Key Observation: Only the page/frame changed; offset preserved. ║╚════════════════════════════════════════════════════════════════════╝╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 2: Page Boundary Address ║╠════════════════════════════════════════════════════════════════════╣║ Given: ║║ Virtual Address: 0x00005000 (exactly at page 5 start) ║║ Page Table Entry for Page 5: Contains Frame Number 0x123 ║╠════════════════════════════════════════════════════════════════════╣║ Analysis: ║║ ║║ VA = 0x00005000 = 5 × 4096 = 20,480 ║║ ║║ Page Number = 0x00005000 >> 12 = 0x5 = 5 ║║ Offset = 0x00005000 & 0xFFF = 0x000 = 0 ║║ ║║ This is the FIRST byte of page 5. ║║ ║║ Physical = (0x123 << 12) | 0x000 ║║ = 0x00123000 ║║ ║║ This is the FIRST byte of frame 0x123. ║╠════════════════════════════════════════════════════════════════════╣║ Special Case: Last Byte of Previous Page ║║ ║║ VA = 0x00004FFF (one byte before page 5) ║║ ║║ Page Number = 0x00004FFF >> 12 = 0x4 = 4 (different page!) ║║ Offset = 0x00004FFF & 0xFFF = 0xFFF = 4095 ║║ ║║ If Page 4 → Frame 0x789: ║║ Physical = (0x789 << 12) | 0xFFF = 0x00789FFF ║║ ║║ Key Insight: 0x00004FFF and 0x00005000 are virtual neighbors ║║ but may map to completely non-adjacent physical locations. ║╚════════════════════════════════════════════════════════════════════╝Addresses ending in 0x000 (offset = 0) are at page starts. Addresses ending in 0xFFF (offset = 4095) are at page ends. Sequential virtual pages may map to non-sequential physical frames—this is the power of paging for non-contiguous allocation.
Real systems support multiple page sizes. Let's work through translations with 2MB and 1GB huge pages to see how the address decomposition changes.
╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 3: 2MB Huge Pages ║╠════════════════════════════════════════════════════════════════════╣║ System Parameters: ║║ Page Size: 2 MB = 2,097,152 bytes = 2^21 bytes ║║ Offset Bits: 21 ║║ Offset Mask: 0x1FFFFF (21 ones) ║║ Page Number Bits: 32 - 21 = 11 (for 32-bit address) ║╠════════════════════════════════════════════════════════════════════╣║ Given: ║║ Virtual Address: 0x00345678 ║║ Page Table Entry: Frame Number 0x7 ║╠════════════════════════════════════════════════════════════════════╣║ Step 1: Decompose Address ║║ ║║ Page Number = VA >> 21 ║║ = 0x00345678 >> 21 ║║ = 0x001 = 1 ║║ ║║ Offset = VA & 0x1FFFFF ║║ = 0x00345678 & 0x001FFFFF ║║ = 0x00145678 ║║ = 1,333,880 bytes into the page ║║ ║║ Verification: 1,333,880 < 2,097,152 ✓ ║╠════════════════════════════════════════════════════════════════════╣║ Step 2: Form Physical Address ║║ ║║ Physical = (Frame << 21) | Offset ║║ = (0x7 << 21) | 0x00145678 ║║ = 0x00E00000 | 0x00145678 ║║ = 0x00F45678 ║╠════════════════════════════════════════════════════════════════════╣║ Result: ║║ ║║ Virtual: 0x00345678 ──→ Physical: 0x00F45678 ║║ Page 1 Frame 7 ║║ Each 2MB page covers addresses 0x000000 - 0x1FFFFF within it. ║║ ║║ TLB Benefit: ║║ One TLB entry now covers 2MB instead of 4KB - 512x improvement! ║╚════════════════════════════════════════════════════════════════════╝╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 4: 1GB Huge Pages ║╠════════════════════════════════════════════════════════════════════╣║ System Parameters: ║║ Page Size: 1 GB = 1,073,741,824 bytes = 2^30 bytes ║║ Offset Bits: 30 ║║ Offset Mask: 0x3FFFFFFF (30 ones) ║║ Page Number Bits: 32 - 30 = 2 (only 4 pages in 32-bit space!) ║╠════════════════════════════════════════════════════════════════════╣║ Given: ║║ Virtual Address: 0x87654321 (64-bit address) ║║ Page Table Entry: Frame Number 0x3 ║╠════════════════════════════════════════════════════════════════════╣║ Step 1: Decompose Address ║║ ║║ Page Number = VA >> 30 ║║ = 0x87654321 >> 30 ║║ = 0x2 = 2 ║║ ║║ Offset = VA & 0x3FFFFFFF ║║ = 0x87654321 & 0x3FFFFFFF ║║ = 0x07654321 ║║ = 124,076,833 bytes into the page ║║ ║║ This offset represents ~118 MB into the 1GB page! ║╠════════════════════════════════════════════════════════════════════╣║ Step 2: Form Physical Address ║║ ║║ Physical = (Frame << 30) | Offset ║║ = (0x3 << 30) | 0x07654321 ║║ = 0xC0000000 | 0x07654321 ║║ = 0xC7654321 ║╠════════════════════════════════════════════════════════════════════╣║ Result: ║║ ║║ Virtual: 0x87654321 ──→ Physical: 0xC7654321 ║║ Page 2 Frame 3 ║║ ║║ Extreme TLB Efficiency: ║║ One TLB entry covers 1GB - 262,144x better than 4KB pages! ║║ Ideal for: databases, virtual machines, HPC applications ║║ Downside: minimum allocation unit is 1GB (potential waste) ║╚════════════════════════════════════════════════════════════════════╝| Page Size | Offset Bits | Coverage per TLB Entry | Internal Frag (avg) | Best For |
|---|---|---|---|---|
| 4 KB | 12 | 4 KB | ~2 KB | General use, small allocations |
| 2 MB | 21 | 2 MB | ~1 MB | Database buffers, VMs |
| 1 GB | 30 | 1 GB | ~512 MB | Large dataset processing |
While huge pages dramatically improve TLB hit rates, they can waste significant memory if allocations don't align well with the page size. Allocating 100 MB with 1GB pages wastes 924 MB! Systems typically use huge pages selectively for known large-memory workloads.
64-bit systems use multi-level page tables to handle sparse address spaces. Let's trace a complete 4-level page walk on x86-64.
╔════════════════════════════════════════════════════════════════════════════╗║ EXAMPLE 5: x86-64 Four-Level Page Table Walk ║╠════════════════════════════════════════════════════════════════════════════╣║ System: x86-64 with 48-bit virtual addresses, 4KB pages ║║ ║║ Virtual Address: 0x00007FFFF7DD5123 ║║ (Typical address in libc.so text segment) ║╠════════════════════════════════════════════════════════════════════════════╣║ Address Bit Layout (48 bits): ║║ ║║ 47 39 38 30 29 21 20 12 11 0 ║║ ├────────┼──────────┼──────────┼──────────┼──────────┤ ║║ │ PML4 │ PDPT │ PD │ PT │ Offset │ ║║ │ 9 bits │ 9 bits │ 9 bits │ 9 bits │ 12 bits │ ║║ └────────┴──────────┴──────────┴──────────┴──────────┘ ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 0: Decompose the Virtual Address ║║ ║║ 0x00007FFFF7DD5123 in binary (48 bits): ║║ 0000 0000 0000 0111 1111 1111 1111 1111 0111 1101 1101 0101 0001 0010 0011║║ ║║ Bit Extraction: ║║ PML4 [47:39] = (VA >> 39) & 0x1FF = (0x7FFFF7DD5123 >> 39) & 0x1FF ║║ = 0xFF = 255 ║║ ║║ PDPT [38:30] = (VA >> 30) & 0x1FF = 0x1FF = 511 ║║ ║║ PD [29:21] = (VA >> 21) & 0x1FF = 0x1BE = 446 ║║ ║║ PT [20:12] = (VA >> 12) & 0x1FF = 0x1D5 = 469 ║║ ║║ Offset [11:0] = VA & 0xFFF = 0x123 = 291 ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 1: Read PML4 Entry ║║ ║║ CR3 Register: 0x00000000001A2000 (PML4 physical base) ║║ PML4 Entry Address = CR3 + (PML4_Index × 8) ║║ = 0x1A2000 + (255 × 8) ║║ = 0x1A2000 + 0x7F8 ║║ = 0x1A27F8 ║║ ║║ Memory Read #1: Fetch 8 bytes from physical 0x1A27F8 ║║ PML4[255] = 0x00000000001B3023 ║║ = Present=1, R/W=1, User=1, PDPT_Frame=0x1B3 ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 2: Read PDPT Entry ║║ ║║ PDPT Base = Frame × 4096 = 0x1B3 × 0x1000 = 0x1B3000 ║║ PDPT Entry Address = 0x1B3000 + (511 × 8) = 0x1B3FF8 ║║ ║║ Memory Read #2: Fetch 8 bytes from physical 0x1B3FF8 ║║ PDPT[511] = 0x00000000001C4023 ║║ = Present=1, Not Huge, PD_Frame=0x1C4 ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 3: Read PD Entry ║║ ║║ PD Base = 0x1C4 × 0x1000 = 0x1C4000 ║║ PD Entry Address = 0x1C4000 + (446 × 8) = 0x1C4DF0 ║║ ║║ Memory Read #3: Fetch 8 bytes from physical 0x1C4DF0 ║║ PD[446] = 0x00000000001D5023 ║║ = Present=1, Not Huge, PT_Frame=0x1D5 ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 4: Read PT Entry ║║ ║║ PT Base = 0x1D5 × 0x1000 = 0x1D5000 ║║ PT Entry Address = 0x1D5000 + (469 × 8) = 0x1D5EA8 ║║ ║║ Memory Read #4: Fetch 8 bytes from physical 0x1D5EA8 ║║ PT[469] = 0x80000000ABCDE025 ║║ = Present=1, R/W=0 (read-only), User=1 ║║ = NX=1 (bit 63 - but this is code, so NX=0 actually) ║║ = Frame=0xABCDE ║╠════════════════════════════════════════════════════════════════════════════╣║ Step 5: Form Physical Address ║║ ║║ Frame Number = 0xABCDE ║║ Offset = 0x123 ║║ ║║ Physical Address = (0xABCDE << 12) | 0x123 ║║ = 0xABCDE000 | 0x123 ║║ = 0xABCDE123 ║╠════════════════════════════════════════════════════════════════════════════╣║ RESULT ║║ ║║ Virtual: 0x00007FFFF7DD5123 ║║ ↓ ║║ Physical: 0x0000000ABCDE123 ║║ ║║ Total Memory Accesses: 4 (for page table walk) ║║ + 1 for actual data = 5 memory accesses without TLB! ║║ ║║ With TLB hit: 1 memory access (translation is instant) ║╚════════════════════════════════════════════════════════════════════════════╝Modern CPUs cache intermediate page walk results. If you've recently visited another address under the same PML4 entry, the PML4 read is cached. Walking to addresses in the same 512GB region reuses PML4 results; same 1GB region reuses PDPT; same 2MB region reuses PD. This dramatically reduces average walk cost.
The Effective Access Time (EAT) measures the average time to access memory considering TLB hits and misses. This is a crucial metric for understanding real-world paging performance.
The EAT Formula:
EAT = (TLB_hit_rate × TLB_hit_time) + (TLB_miss_rate × TLB_miss_time)
Where:
╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 6: Effective Access Time Calculation ║╠════════════════════════════════════════════════════════════════════╣║ System Parameters: ║║ Memory access time: 100 ns ║║ TLB lookup time: 10 ns (parallel with cache lookup typically) ║║ TLB hit rate: 98% ║║ Single-level page table ║╠════════════════════════════════════════════════════════════════════╣║ Analysis: ║║ ║║ TLB Hit Case (98% of accesses): ║║ Time = TLB lookup + Memory access ║║ = 10 ns + 100 ns = 110 ns ║║ ║║ TLB Miss Case (2% of accesses): ║║ Time = TLB lookup + Page table read + Memory access ║║ = 10 ns + 100 ns + 100 ns = 210 ns ║║ (Page table read is a memory access) ║╠════════════════════════════════════════════════════════════════════╣║ Effective Access Time: ║║ ║║ EAT = 0.98 × 110 ns + 0.02 × 210 ns ║║ = 107.8 ns + 4.2 ns ║║ = 112 ns ║║ ║║ Overhead compared to no translation: 112/100 = 12% slowdown ║╠════════════════════════════════════════════════════════════════════╣║ Sensitivity Analysis: ║║ ║║ If TLB hit rate drops to 90%: ║║ EAT = 0.90 × 110 ns + 0.10 × 210 ns = 99 ns + 21 ns = 120 ns ║║ Overhead: 20% slowdown ║║ ║║ If TLB hit rate is only 80%: ║║ EAT = 0.80 × 110 ns + 0.20 × 210 ns = 88 ns + 42 ns = 130 ns ║║ Overhead: 30% slowdown ║║ ║║ Key insight: TLB hit rate is CRITICAL for performance! ║╚════════════════════════════════════════════════════════════════════╝╔════════════════════════════════════════════════════════════════════╗║ EXAMPLE 7: EAT with Multi-Level Page Tables ║╠════════════════════════════════════════════════════════════════════╣║ System Parameters: ║║ Memory access time: 100 ns ║║ TLB lookup time: ~0 ns (parallel with cache) ║║ TLB hit rate: 95% ║║ 4-level page table (x86-64 style) ║╠════════════════════════════════════════════════════════════════════╣║ TLB Hit Case (95%): ║║ Time = Memory access = 100 ns ║║ (TLB lookup overlaps with cache access) ║║ ║║ TLB Miss Case (5%): ║║ Time = 4 page table reads + Memory access ║║ = 4 × 100 ns + 100 ns = 500 ns ║║ ║║ (Without page walk caching - worst case) ║╠════════════════════════════════════════════════════════════════════╣║ Effective Access Time (Worst Case): ║║ ║║ EAT = 0.95 × 100 ns + 0.05 × 500 ns ║║ = 95 ns + 25 ns ║║ = 120 ns ║║ ║║ 20% overhead from paging ║╠════════════════════════════════════════════════════════════════════╣║ With Page Walk Cache (Realistic): ║║ ║║ Assume intermediate entries often cached: ║║ Average page walk = 1.5 memory accesses (not 4) ║║ ║║ TLB Miss Time = 1.5 × 100 ns + 100 ns = 250 ns ║║ ║║ EAT = 0.95 × 100 ns + 0.05 × 250 ns ║║ = 95 ns + 12.5 ns ║║ = 107.5 ns ║║ ║║ Only 7.5% overhead! ║╠════════════════════════════════════════════════════════════════════╣║ Key Factors Affecting Real-World EAT: ║║ ║║ 1. Workload locality - affects TLB hit rate ║║ 2. Working set size - larger = more TLB misses ║║ 3. Page walk caching - reduces miss penalty ║║ 4. Huge pages - dramatically improve hit rate ║║ 5. TLB size - more entries = better coverage ║╚════════════════════════════════════════════════════════════════════╝In modern systems with large TLBs, ASID tagging, and page walk caches, the effective overhead from paging is typically 5-15% for well-behaved workloads. The key is TLB hit rate: with 99% hits, overhead is negligible; with 90% hits, it becomes noticeable; below 80%, something is wrong with the workload's locality.
Test your understanding with these practice problems. Solutions are provided after each problem.
Problem 1: Basic Translation
Given:
Find:
Page size = 8 KB = 8192 = 2^13, so 13 offset bits
32 - 13 = 19 page number bits
Page Number = 0x00074AC0 >> 13 = 0x0003A = 58 Offset = 0x00074AC0 & 0x1FFF = 0x0AC0 = 2752
Physical = (0x1FF << 13) | 0x0AC0 = 0x003FE000 | 0x0AC0 = 0x003FEAC0
For any paging problem: (1) Determine page size in bytes and bits, (2) Calculate offset bits = log₂(page size), (3) Calculate page number bits = address size - offset bits, (4) Apply extraction formulas, (5) Form physical address. Always verify: offset < page size, and page#/frame# fit in their bit counts.
Understanding edge cases reveals deeper insights about how paging works:
| Scenario | Virtual Address | Analysis | Result |
|---|---|---|---|
| Null pointer | 0x00000000 | Page 0, offset 0. Usually unmapped. | Page fault (intentional) |
| First valid page | 0x00001000 | Page 1, offset 0 (if page 0 unmapped) | Normal translation |
| Maximum offset | 0x00000FFF | Page 0, offset 4095 | Last byte of page 0 |
| Page boundary | 0x00000FFF → 0x00001000 | Different pages, possibly different frames | Non-contiguous physical |
| Kernel boundary | 0x7FFFFFFF → 0x80000000 | User→kernel transition | Protection fault if user accessing kernel |
| Maximum VA (32-bit) | 0xFFFFFFFF | Page 0xFFFFF, offset 0xFFF | Last byte of address space |
Scenario: Cross-Page Access
What happens when a multi-byte access spans a page boundary?
Access: 4-byte read at virtual address 0x00001FFE
Bytes needed:
0x00001FFE (Page 1, offset 0xFFE) - byte 0
0x00001FFF (Page 1, offset 0xFFF) - byte 1
0x00002000 (Page 2, offset 0x000) - byte 2
0x00002001 (Page 2, offset 0x001) - byte 3
This requires TWO page translations!
- Page 1 might map to Frame 0x100
- Page 2 might map to Frame 0x500
Physical accesses:
0x00100FFE, 0x00100FFF (contiguous)
0x00500000, 0x00500001 (far away!)
The hardware (or microcode) handles this transparently,
but it's slower than a single-page access.
Misaligned accesses that span page boundaries are expensive. A 4-byte access at offset 0xFFE hits two pages, requiring two translations and potentially two cache lines. This is why compilers align data to natural boundaries and why performance-critical code avoids cross-page spanning.
You've now completed a comprehensive exploration of paging address translation. Let's consolidate the essential knowledge:
The Complete Translation Algorithm:
function translate(virtual_address):
page_number = virtual_address >> offset_bits
offset = virtual_address & (page_size - 1)
if tlb.contains(page_number):
frame_number = tlb.get(page_number) // Fast path
else:
pte = page_table[page_number] // May involve multi-level walk
if not pte.present:
raise PageFault(virtual_address)
if not check_permissions(pte, access_type):
raise ProtectionFault(virtual_address)
frame_number = pte.frame_number
tlb.insert(page_number, frame_number)
physical_address = (frame_number << offset_bits) | offset
return physical_address
You have achieved mastery of paging address translation—the fundamental mechanism enabling virtual memory, process isolation, and modern operating systems. You can now decompose addresses, perform manual translations, calculate EAT, and reason about multi-level page tables. This knowledge is essential for systems programming, OS development, and understanding computer architecture.