101
0/240
Loading 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.