Interview Problem Types
Memory Calculations
Read aloud is unavailable in this browser.
Numerical Precision in Memory Problems
Memory calculation problems are the most numerically intensive category in OS interviews. They test your understanding of virtual memory architecture through precise arithmetic: computing page table sizes, translating virtual addresses, calculating TLB hit ratios, and determining effective memory access times.
These problems have exact answers. Unlike system design questions with multiple valid approaches, memory calculations require correct formulas applied with perfect precision. An error in understanding bit allocations, a confusion between logical and physical address sizes, or misremembering the multi-level page table formula will produce a completely wrong answer.
This page provides the complete mathematical framework for every memory calculation type you'll encounter.
By the end of this page, you will: (1) Parse virtual addresses into page number and offset components, (2) Calculate page table sizes for single and multi-level schemes, (3) Compute effective access time given TLB hit ratios, (4) Perform address translation through page tables, (5) Analyze memory requirements for inverted page tables and segmented systems.
Address Space Fundamentals
Every memory calculation builds on understanding address spaces. You must be fluent with these foundational concepts.
Key Parameters and Symbols:
- Virtual Address Space (VAS): 2^v bytes, where v = number of virtual address bits
- Physical Address Space (PAS): 2^p bytes, where p = number of physical address bits
- Page Size: 2^d bytes, where d = number of offset bits
- Number of Virtual Pages: 2^(v-d) = Virtual Address Space / Page Size
- Number of Physical Frames: 2^(p-d) = Physical Address Space / Page Size
Virtual Address Decomposition:
|<--- Virtual Page Number (VPN) --->|<--- Page Offset --->|
| (v - d) bits | d bits |
|<-------------- v bits total ------------------------------>|
The page offset remains unchanged during translation—it specifies the byte position within the page/frame. The VPN is used to look up the Physical Frame Number (PFN) in the page table.
| System | Virtual Addr Bits | Physical Addr Bits | Page Size | VPN Bits | Offset Bits |
|---|---|---|---|---|---|
| 32-bit, 4KB pages | 32 | 32 | 4 KB (2¹²) | 20 | 12 |
| 32-bit, 4MB pages | 32 | 32 | 4 MB (2²²) | 10 | 22 |
| 64-bit, 4KB pages (48-bit used) | 48 | 52 | 4 KB (2¹²) | 36 | 12 |
| PAE (Physical Address Extension) | 32 | 36 | 4 KB (2¹²) | 20 | 12 |
Virtual and physical address sizes may differ! 32-bit virtual addresses with 36-bit physical addresses (PAE) allow more physical RAM than one process can address. 64-bit systems typically use only 48 bits of the 64-bit virtual address space (canonical addresses).
Address Translation Formula:
Physical Address = (Physical Frame Number × Page Size) + Page Offset
= (PFN << d) | Offset
Or equivalently:
Physical Address = (Page Table[VPN].PFN << d) | (Virtual Address & (Page Size - 1))
Example:
- Virtual Address: 0x12345678 (32-bit)
- Page Size: 4 KB = 2^12 bytes
- Offset bits: 12
- Page Offset: 0x678 (last 12 bits = 3 hex digits)
- VPN: 0x12345 (upper 20 bits)
- If Page Table[0x12345] contains PFN = 0xABCDE
- Physical Address: 0xABCDE678
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
def parse_virtual_address(virtual_addr: int, page_size_bits: int, virtual_addr_bits: int) -> tuple[int, int]: """ Parse a virtual address into VPN and offset. Args: virtual_addr: The virtual address to parse page_size_bits: Number of bits for page offset (log2 of page size) virtual_addr_bits: Total bits in virtual address Returns: (vpn, offset) tuple """ offset_mask = (1 << page_size_bits) - 1 # e.g., 0xFFF for 12 bits offset = virtual_addr & offset_mask vpn = virtual_addr >> page_size_bits return vpn, offset def translate_address(virtual_addr: int, page_table: dict[int, int], page_size_bits: int) -> int: """ Translate virtual address to physical address using page table. Args: virtual_addr: Virtual address to translate page_table: Dict mapping VPN -> PFN page_size_bits: Number of offset bits Returns: Physical address """ vpn, offset = parse_virtual_address(virtual_addr, page_size_bits, 32) if vpn not in page_table: raise PageFaultException(f"VPN {vpn:x} not in page table") pfn = page_table[vpn] physical_addr = (pfn << page_size_bits) | offset return physical_addr # Example usagepage_table = {0x12345: 0xABCDE} # VPN -> PFN mappingvirtual_addr = 0x12345678physical = translate_address(virtual_addr, page_table, 12)print(f"Virtual: 0x{virtual_addr:x} -> Physical: 0x{physical:x}")# Output: Virtual: 0x12345678 -> Physical: 0xabcde678Single-Level Page Table Size Calculations
The most fundamental memory calculation is determining page table size. Master this formula and its derivation.
Page Table Entry (PTE) Contents:
Each page table entry typically contains:
- Physical Frame Number (PFN): (p - d) bits, where p = physical address bits, d = offset bits
- Valid/Present bit: 1 bit
- Protection bits: 2-3 bits (read, write, execute)
- Dirty bit: 1 bit
- Accessed/Reference bit: 1 bit
- Other bits: User/supervisor, caching control, etc.
PTE sizes are typically rounded to powers of 2: 4 bytes (32-bit) or 8 bytes (64-bit).
Page Table Size Formula:
Page Table Size = Number of PTEs × Size per PTE
= (Number of Virtual Pages) × (PTE Size)
= (Virtual Address Space / Page Size) × (PTE Size)
= (2^(v-d)) × (PTE Size)
If the problem specifies PTE size, use it directly. Otherwise, calculate minimum required bits (PFN + control bits) and round up to 4 or 8 bytes. Common convention: 32-bit systems use 4-byte PTEs; 64-bit systems use 8-byte PTEs.
Worked Example 1: Basic Page Table Size
Given:
- 32-bit virtual address space
- 32-bit physical address space
- 4 KB page size
- 4-byte PTEs
Solution:
- Virtual address bits: v = 32
- Page size: 4 KB = 2^12 → Offset bits: d = 12
- VPN bits: 32 - 12 = 20 → Number of PTEs = 2^20 = 1,048,576
- Page table size = 2^20 × 4 bytes = 4 MB
Critical Insight: Every process needs 4 MB just for its page table! This is why single-level page tables are impractical for large address spaces.
Worked Example 2: 64-bit Address Space (Impractical)
Given:
- 64-bit virtual address space
- 4 KB pages
- 8-byte PTEs
Solution:
- VPN bits: 64 - 12 = 52
- Number of PTEs: 2^52 ≈ 4.5 × 10^15
- Page table size: 2^52 × 8 bytes = 2^55 bytes = 32 Petabytes!
This is astronomically larger than any RAM—clearly impossible. This is precisely why 64-bit systems:
- Only use 48 bits of virtual address (still needs multi-level)
- Use multi-level page tables to avoid allocating unused PTEs
- Use inverted page tables in some architectures
| Configuration | VPN Bits | PTEs | PTE Size | Table Size |
|---|---|---|---|---|
| 32-bit, 4KB pages, 4B PTEs | 20 | 2²⁰ = 1M | 4 B | 4 MB |
| 32-bit, 4MB pages, 4B PTEs | 10 | 2¹⁰ = 1K | 4 B | 4 KB |
| 32-bit, 8KB pages, 4B PTEs | 19 | 2¹⁹ = 512K | 4 B | 2 MB |
| 48-bit, 4KB pages, 8B PTEs | 36 | 2³⁶ = 64G | 8 B | 512 GB |
Multi-Level Page Table Calculations
Multi-level (hierarchical) page tables solve the memory waste problem by only allocating page table pages for used regions of the address space.
Key Insight:
Instead of one giant page table, we have a tree:
- Level 1 (top): Page directory, always allocated
- Level 2+: Secondary tables, allocated only when needed
Most of a process's virtual address space is unused. Multi-level tables avoid allocating PTEs for unmapped regions.
Two-Level Page Table (32-bit x86):
|<-- 10 bits -->|<-- 10 bits -->|<-- 12 bits -->|
Page Dir Page Table Offset
Index (PDI) Index (PTI)
Page Directory: 2^10 = 1024 entries × 4 bytes = 4 KB
Each Page Table: 2^10 = 1024 entries × 4 bytes = 4 KB
Translation Steps:
- PDI = VA[31:22] → Index into page directory
- Page directory entry points to page table
- PTI = VA[21:12] → Index into page table
- Page table entry contains PFN
- Combine PFN with offset VA[11:0]
Multi-Level Memory Overhead Formula:
Minimum memory (only used pages):
Minimum = Size of top-level directory + Size of used page tables
Maximum memory (fully populated):
Maximum = Sum of all levels fully allocated
Example: Two-Level for 32-bit, 4KB pages
For a process using only 1 MB of virtual memory (contiguous):
- Pages used: 1 MB / 4 KB = 256 pages
- These 256 pages fit in one second-level table (1024 entries)
- Memory needed: Outer directory (4 KB) + 1 inner table (4 KB) = 8 KB
Compare to single-level: 4 MB Savings: 99.8%!
Multi-level page tables are designed so each table fits exactly in one page frame. This simplifies allocation and allows page tables themselves to be paged. For 4 KB pages with 4-byte PTEs: 4096/4 = 1024 = 2^10 entries, requiring 10 index bits per level.
Four-Level Page Table (x86-64)
Intel x86-64 uses 48-bit virtual addresses with four levels:
|<- 16 unused ->|<- 9 bits ->|<- 9 bits ->|<- 9 bits ->|<- 9 bits ->|<- 12 bits ->|
PML4 PDPT PD PT Offset
Index Index Index Index
Each level: 2^9 = 512 entries × 8 bytes = 4 KB (one page)
Why 9 bits per level?
8-byte PTEs with 4 KB pages: 4096 bytes / 8 bytes per entry = 512 entries = 2^9
Total index bits: 9 × 4 = 36 Total address bits: 36 + 12 = 48 ✓
Memory Calculation: Walk through levels
For translation, we access 4 levels of page tables plus the final memory access = 5 memory accesses without TLB.
| Level | Name | Index Bits | Entries per Table | Table Size |
|---|---|---|---|---|
| 4 (top) | PML4 (Page Map Level 4) | VA[47:39] | 512 | 4 KB |
| 3 | PDPT (Page Dir Pointer Table) | VA[38:30] | 512 | 4 KB |
| 2 | PD (Page Directory) | VA[29:21] | 512 | 4 KB |
| 1 | PT (Page Table) | VA[20:12] | 512 | 4 KB |
| — | Offset | VA[11:0] | — | 4 KB page |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
def calculate_multilevel_page_table_memory( virtual_addr_bits: int, page_size_bits: int, pte_size_bytes: int, pages_used: int, numa_levels: int = None) -> dict: """ Calculate memory usage for multi-level page table. Assumes even division of index bits across levels and that each level table fits in one page. """ page_size = 1 << page_size_bits entries_per_table = page_size // pte_size_bytes bits_per_level = page_size_bits - int.bit_length(pte_size_bytes) + 1 vpn_bits = virtual_addr_bits - page_size_bits if numa_levels is None: # Calculate number of levels needed import math num_levels = math.ceil(vpn_bits / bits_per_level) else: num_levels = numa_levels # Calculate minimum memory (sparse usage) # Outer-most level always allocated # Each inner level: number of contiguous regions # Simplification: assume pages_used are contiguous inner_tables_needed = (pages_used + entries_per_table - 1) // entries_per_table # Each inner table requires ancestor tables # For now, simple calculation assuming contiguous allocation level_tables = [1] # Top level always 1 table remaining = inner_tables_needed for level in range(num_levels - 1): tables_this_level = (remaining + entries_per_table - 1) // entries_per_table level_tables.append(tables_this_level) remaining = tables_this_level level_tables.reverse() # Now [innermost, ..., outermost] total_tables = sum(level_tables) minimum_memory = total_tables * page_size # Maximum memory (fully populated) max_memory = page_size # Top level for _ in range(num_levels - 1): max_memory = max_memory * entries_per_table + page_size return { "num_levels": num_levels, "bits_per_level": bits_per_level, "entries_per_table": entries_per_table, "minimum_memory_bytes": minimum_memory, "maximum_memory_bytes": max_memory, "level_tables": level_tables } # Example: x86-64 style (48-bit, 4KB pages, 8B PTEs, 4 levels)result = calculate_multilevel_page_table_memory( virtual_addr_bits=48, page_size_bits=12, pte_size_bytes=8, pages_used=256, # 1 MB of virtual memory numa_levels=4)print(f"Config: 48-bit addr, 4KB pages, 4 levels")print(f"Entries per table: {result['entries_per_table']}")print(f"Min memory: {result['minimum_memory_bytes'] / 1024:.1f} KB")TLB Performance and Effective Access Time
The Translation Lookaside Buffer (TLB) caches recent address translations. TLB-related calculations are among the most common interview problems.
TLB Miss Penalty:
Without TLB: Each memory access requires page table walks = multiple memory accesses.
- Single-level: 2 memory accesses (1 for PTE + 1 for data)
- Two-level: 3 memory accesses (2 for page tables + 1 for data)
- Four-level (x86-64): 5 memory accesses
With TLB hit: Just 1 memory access (TLB lookup is parallel with cache)
Effective Access Time (EAT) Formula:
EAT = (TLB Hit Rate × TLB Hit Time) + (TLB Miss Rate × TLB Miss Time)
Where:
- TLB Hit Time = TLB lookup time + Memory access time
- TLB Miss Time = TLB lookup time + Page table walk time + Memory access time
Simplified (assuming TLB lookup is negligible or overlapped):
EAT = (Hit Rate × Memory Access Time) + (Miss Rate × (Page Table Accesses + 1) × Memory Access Time)
Some problems ignore TLB lookup time (it's very fast, ~1 cycle). Others include it explicitly (e.g., 2ns). Read the problem carefully to see which model is expected. If not specified, assume TLB lookup is included in the timing.
Worked Example 1: Basic EAT Calculation
Given:
- Memory access time: 100 ns
- TLB hit ratio: 98%
- Single-level page table (1 PTE access on miss)
- TLB lookup time: included in hit time
Solution:
TLB Hit Time = 100 ns (just access memory) TLB Miss Time = 100 ns (PTE) + 100 ns (data) = 200 ns
EAT = 0.98 × 100 + 0.02 × 200 = 98 + 4 = 102 ns
Slowdown factor: 102/100 = 2% overhead from paging.
Worked Example 2: Multi-Level with TLB
Given:
- Memory access time: 100 ns
- TLB hit ratio: 95%
- Four-level page table
- TLB lookup time: 10 ns (not overlapped)
Solution:
TLB Hit Time = 10 ns + 100 ns = 110 ns TLB Miss Time = 10 ns + 4 × 100 ns + 100 ns = 10 + 400 + 100 = 510 ns
EAT = 0.95 × 110 + 0.05 × 510 = 104.5 + 25.5 = 130 ns
Analysis: Without TLB, every access would be 510 ns. TLB provides 4× speedup!
Worked Example 3: Hierarchical TLB
Given:
- Memory access: 100 ns
- L1 TLB: 99% hit rate, 1 ns lookup
- L2 TLB: 90% hit rate (of L1 misses), 10 ns lookup
- Two-level page table
Solution:
L1 hit: 1 + 100 = 101 ns (probability: 0.99) L2 hit: 1 + 10 + 100 = 111 ns (probability: 0.01 × 0.90 = 0.009) Full miss: 1 + 10 + 200 + 100 = 311 ns (probability: 0.01 × 0.10 = 0.001)
EAT = 0.99 × 101 + 0.009 × 111 + 0.001 × 311 = 99.99 + 0.999 + 0.311 = 101.3 ns
The hierarchical TLB nearly eliminates miss penalty!
| TLB Hit Rate | EAT | Slowdown vs Ideal |
|---|---|---|
| 100% | 100 ns | 0% |
| 99% | 105 ns | 5% |
| 98% | 110 ns | 10% |
| 95% | 125 ns | 25% |
| 90% | 150 ns | 50% |
| 80% | 200 ns | 100% |
| 0% (no TLB) | 500 ns | 400% |
TLB coverage = TLB entries × Page size. A TLB with 1024 entries and 4 KB pages covers 4 MB. If the working set exceeds this, TLB misses increase. Large pages (2 MB, 1 GB) dramatically increase coverage.
Inverted Page Table Calculations
Inverted page tables are an alternative design that scales with physical memory rather than virtual address space. They're used in PowerPC, IA-64, and some other architectures.
Key Insight:
Normal page table: One entry per virtual page → Size ∝ Virtual address space Inverted page table: One entry per physical frame → Size ∝ Physical memory
Structure:
One system-wide table with entries for each physical frame:
- PID (process identifier)
- Virtual page number
- Pointer for hash chain (for collision resolution)
Inverted Page Table Size:
Inverted PT Size = Number of Physical Frames × Entry Size
= (Physical Memory / Page Size) × Entry Size
Worked Example: Inverted Page Table Size
Given:
- Physical memory: 4 GB
- Page size: 4 KB
- Entry size: 16 bytes (PID + VPN + hash chain pointer + flags)
Solution:
Number of frames = 4 GB / 4 KB = 2^32 / 2^12 = 2^20 = 1,048,576 frames
Inverted PT size = 2^20 × 16 bytes = 16 MB
Compare to per-process PT: With 64-bit virtual addresses (48-bit used) and 8-byte PTEs: Single-level would be astronomically large. Multi-level still requires potentially large per-process overhead.
Inverted PT Advantage: Only 16 MB regardless of number of processes!
Inverted Page Table Lookup:
Problem: Given (PID, VPN), find the frame number.
Naive approach: Linear search through all entries → O(n) — Too slow!
Solution: Hash table
- Hash (PID, VPN) to get bucket index
- Search chain at that bucket for matching (PID, VPN)
- Return frame number (= position in table)
Average lookup time:
Average = Hash computation + (Chain length / 2) × Memory access
With good hash function and load factor < 0.7: Average chain length ≈ 1-2 Average lookup ≈ 1-2 memory accesses
TLB is still critical for inverted page tables — hash lookups are still slower than direct indexing.
Advantages: Fixed memory overhead regardless of address space size or process count.
Disadvantages: (1) No support for shared memory (same frame, different VPNs) without extension, (2) Hash collisions add lookup overhead, (3) More complex implementation.
Complex Memory Access Time Problems
Advanced interview problems combine multiple factors: cache, TLB, page faults, and disk access. Here's the complete framework.
Full Memory Hierarchy Access Time:
Effective Access Time =
P(L1 hit) × L1_time +
P(L1 miss, L2 hit) × L2_time +
P(L1 miss, L2 miss, TLB hit) × (TLB_lookup + RAM_time) +
P(TLB miss, no page fault) × (TLB_lookup + Page_table_walk + RAM_time) +
P(TLB miss, page fault) × (TLB_lookup + Page_table_walk + Disk_access + RAM_time)
Simplified version often used:
EAT = TLB_component + Cache_component + Page_fault_component
Worked Example: Combined TLB + Page Fault
Given:
- Memory access time: 100 ns
- TLB hit ratio: 98%
- TLB lookup: 10 ns
- Two-level page table
- Page fault rate: 0.1% (1 in 1000 accesses)
- Disk access time: 10 ms = 10,000,000 ns
Solution:
Case 1: TLB hit, no page fault (P = 0.98 × 0.999 = 0.97902) Time = 10 + 100 = 110 ns
Case 2: TLB miss, no page fault (P = 0.02 × 0.999 = 0.01998) Time = 10 + 2×100 + 100 = 310 ns
Case 3: TLB hit, page fault (P = 0.98 × 0.001 = 0.00098) Time = 10 + 10,000,000 + 100 = 10,000,110 ns
Case 4: TLB miss, page fault (P = 0.02 × 0.001 = 0.00002) Time = 10 + 2×100 + 10,000,000 + 100 = 10,000,310 ns
EAT = 0.97902 × 110 + 0.01998 × 310 + 0.00098 × 10,000,110 + 0.00002 × 10,000,310 = 107.69 + 6.19 + 9,800.11 + 200.01 = 10,114 ns ≈ 10.1 μs
Critical insight: Even 0.1% page faults increase EAT by 100×! The 10ms disk penalty dominates.
Disk access is ~100,000× slower than RAM. Even a tiny page fault rate (0.1%) can make EAT 100× worse. This is why working set management and avoiding thrashing is critical for performance.
Calculating Required Hit Ratio for Target EAT:
Sometimes the problem is inverted: given a target EAT, find the required TLB hit ratio.
Example: What TLB hit ratio is needed to keep EAT ≤ 110 ns?
Given:
- Memory access: 100 ns
- Two-level page table (miss cost = 300 ns with 2 PT accesses + data)
- Target EAT: 110 ns
Let h = hit ratio:
EAT = h × 100 + (1-h) × 300 ≤ 110 100h + 300 - 300h ≤ 110 -200h ≤ -190 h ≥ 0.95
Answer: Need at least 95% TLB hit ratio.
Complete Address Translation Walkthroughs
Let's work through complete address translation problems that combine all concepts.
Problem 1: Two-Level Page Table Walk
Given:
- 32-bit virtual address: 0x80401234
- Page size: 4 KB (12-bit offset)
- Two-level paging: 10-bit PDI, 10-bit PTI
- Page Directory Base: 0x1000 (physical)
- Page Directory contents at index 0x201: PTE = 0x5000 (points to page table)
- Page Table contents at index 0x001: PTE = 0x7000 (points to data frame)
Find the physical address.
Solution:
-
Parse virtual address:
- Binary: 1000 0000 0100 0000 0001 0010 0011 0100
- PDI: bits[31:22] = 10 0000 0001 = 0x201
- PTI: bits[21:12] = 00 0000 0001 = 0x001
- Offset: bits[11:0] = 0010 0011 0100 = 0x234
-
Access Page Directory:
- PD entry address = PDBR + PDI × 4 = 0x1000 + 0x201 × 4 = 0x1804
- Content: 0x5000 → Page Table at physical 0x5000
-
Access Page Table:
- PT entry address = 0x5000 + PTI × 4 = 0x5000 + 0x001 × 4 = 0x5004
- Content: 0x7000 → Data frame at physical 0x7000
-
Combine:
- Physical address = 0x7000 + 0x234 = 0x7234
Problem 2: TLB + Page Table Translation
Given:
TLB Contents:
VPN PFN Valid
0x00 0x10 1
0x01 0x20 1
0x02 0x30 0 (invalid)
Page Table Contents:
VPN PFN Valid
0x00 0x10 1
0x01 0x20 1
0x02 0x40 1
0x03 0x50 1
Page size: 256 bytes (8-bit offset)
Translate virtual addresses: 0x0100, 0x0164, 0x0201, 0x0300
Solutions:
| Virtual Addr | VPN | Offset | TLB? | PFN | Physical Addr |
|---|---|---|---|---|---|
| 0x0100 | 0x01 | 0x00 | Hit | 0x20 | 0x2000 |
| 0x0164 | 0x01 | 0x64 | Hit | 0x20 | 0x2064 |
| 0x0201 | 0x02 | 0x01 | Miss→PT | 0x40 | 0x4001 |
| 0x0300 | 0x03 | 0x00 | Miss→PT | 0x50 | 0x5000 |
Note: For 0x0201, TLB has entry but it's invalid (perhaps evicted). Must consult page table.
For each translation: (1) Extract VPN and offset, (2) Check TLB for VPN, (3) If TLB miss, walk page table, (4) Check valid bit, (5) If invalid, page fault, (6) Combine PFN with offset for physical address.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.