Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

3 / 5

Memory Calculations

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.

What You Will Master

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.

Common Address Space Configurations
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

Critical: Virtual vs Physical Address Sizes

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

address_translation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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 usage
page_table = {0x12345: 0xABCDE}  # VPN -> PFN mapping
virtual_addr = 0x12345678
physical = translate_address(virtual_addr, page_table, 12)
print(f"Virtual: 0x{virtual_addr:x} -> Physical: 0x{physical:x}")
# Output: Virtual: 0x12345678 -> Physical: 0xabcde678

Single-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)

PTE Size Determination

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

Page Table Size Quick Reference
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%!

Design Rule: Each Level Fits in One Page

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.

x86-64 Four-Level Page Table Bits
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

multilevel_calculation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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)

TLB Lookup 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 Ratio Impact on EAT (100ns memory, 4-level PT)
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 Calculation

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.

Inverted PT Tradeoffs

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.

Page Faults Dominate Everything

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.

Translation Checklist

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.

Summary: Memory Calculation Mastery

Essential Formulas

•Page offset bits = log₂(page size)
•VPN bits = Virtual address bits - Offset bits
•Number of PTEs = 2^(VPN bits) = Virtual address space / Page size
•Page table size = Number of PTEs × PTE size
•EAT = (Hit rate × Hit time) + (Miss rate × Miss time)
•Multi-level indices = VPN bits / log₂(entries per table)
•Inverted PT size = Physical frames × Entry size

Common Pitfalls

•Confusing virtual and physical address sizes
•Forgetting to include all page table levels in miss penalty
•Using wrong PTE size (check if specified)
•Not accounting for page faults in EAT
•Incorrect bit extraction for multi-level indices

Page Complete

You now have comprehensive knowledge of memory calculations for OS interviews. The next page covers file system calculations—computing disk block allocations, FAT sizes, inode requirements, and access patterns.

3 / 5

Loading learning content...

Operating SystemsInterview Problem Types

Interview Problem Types

LevelAdvanced

Duration180 mins

TopicInterview Problem Types

3 / 5

Memory Calculations

Numerical Precision in Memory Problems

This page provides the complete mathematical framework for every memory calculation type you'll encounter.

What You Will Master

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.

Common Address Space Configurations
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

Critical: Virtual vs Physical Address Sizes

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

address_translation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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 usage
page_table = {0x12345: 0xABCDE}  # VPN -> PFN mapping
virtual_addr = 0x12345678
physical = translate_address(virtual_addr, page_table, 12)
print(f"Virtual: 0x{virtual_addr:x} -> Physical: 0x{physical:x}")
# Output: Virtual: 0x12345678 -> Physical: 0xabcde678

Single-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)

PTE Size Determination

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

Page Table Size Quick Reference
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%!

Design Rule: Each Level Fits in One Page

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.

x86-64 Four-Level Page Table Bits
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

multilevel_calculation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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)

TLB Lookup Time

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 Ratio Impact on EAT (100ns memory, 4-level PT)
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 Calculation

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

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.

Inverted PT Tradeoffs

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.

Page Faults Dominate Everything

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.

Translation Checklist

Summary: Memory Calculation Mastery

Essential Formulas

•Page offset bits = log₂(page size)
•VPN bits = Virtual address bits - Offset bits
•Number of PTEs = 2^(VPN bits) = Virtual address space / Page size
•Page table size = Number of PTEs × PTE size
•EAT = (Hit rate × Hit time) + (Miss rate × Miss time)
•Multi-level indices = VPN bits / log₂(entries per table)
•Inverted PT size = Physical frames × Entry size

Common Pitfalls

•Confusing virtual and physical address sizes
•Forgetting to include all page table levels in miss penalty
•Using wrong PTE size (check if specified)
•Not accounting for page faults in EAT
•Incorrect bit extraction for multi-level indices

Page Complete

3 / 5