Operating SystemsOS Design & Interview

Numerical Problems in Operating Systems

LevelAdvanced

Duration180 mins

TopicOS Design & Interview

3 / 5

TLB Hit Ratio Calculations

The Translation Lookaside Buffer: Virtual Memory's Critical Bottleneck

Virtual memory's elegance comes with a cost: every memory access requires an address translation. Without optimization, this translation would require multiple memory accesses (one per page table level), making virtual memory prohibitively slow. The Translation Lookaside Buffer (TLB) is the hardware solution that makes virtual memory practical.

The TLB is a small, fast cache of recent address translations. When a virtual address translation is found in the TLB (a TLB hit), translation is nearly instantaneous. When it's not found (a TLB miss), the system must perform an expensive page table walk.

Understanding TLB hit ratio calculations is essential because:

They determine effective memory access time
They reveal the performance impact of page size decisions
They expose workload-dependent performance characteristics
They're extremely common in technical interviews

What You Will Master

By the end of this page, you will be able to calculate Effective Access Time (EAT) for any TLB configuration, analyze how TLB parameters affect performance, understand the relationship between working set size and TLB hit ratio, and solve complex multi-level TLB problems.

TLB Fundamentals

Before calculating TLB performance, we must understand TLB architecture and operation.

TLB Structure:

A TLB entry contains:

Virtual Page Number (VPN): The key for lookup
Physical Frame Number (PFN): The translated result
Valid Bit: Is this entry currently valid?
Protection Bits: R/W/X permissions
ASID (Address Space ID): Which process owns this entry
Other flags: Global, dirty, accessed, etc.

TLB Lookup Process:

CPU issues virtual address
TLB receives the VPN portion
TLB searches for matching entry (in parallel for fully-associative)
If found (hit): Return PFN, translation complete
If not found (miss): Page table walk required

Typical TLB Characteristics by System
System	TLB Size	Associativity	TLB Access Time	Memory Time
x86-64 (L1 DTLB)	64-96 entries	4-way/fully	1-3 cycles	100+ cycles
x86-64 (L2 TLB)	512-2048 entries	4-8 way	6-8 cycles	100+ cycles
ARM Cortex-A	32-128 entries	Fully assoc	1 cycle	50-100 cycles
RISC-V	16-64 entries	Fully assoc	1 cycle	Variable

TLB Miss Handling:

When a TLB miss occurs, one of two mechanisms handles it:

Hardware-Managed TLB (x86, ARM):

Hardware automatically walks the page table
Found entry loaded into TLB
Original instruction restarted
Typical cost: 10-100 cycles

Software-Managed TLB (MIPS, SPARC, some RISC-V):

TLB miss generates exception
OS handler walks page table
OS loads TLB entry with special instruction
Return from exception, instruction restarted
Typical cost: 100-1000 cycles

Page Fault (page not in memory):

Even after TLB miss handling, the page might not be in physical memory
This triggers a page fault: disk I/O required
Cost: millions of cycles (milliseconds)

TLB vs Page Table Entry Cache

The TLB caches complete virtual-to-physical translations. Some CPUs also cache intermediate page table entries (like PDEs, PDPEs) separately. This means a TLB miss might still be fast if upper-level page table entries are cached in the data cache or special paging caches.

Basic Effective Access Time (EAT) Calculation

The fundamental TLB performance metric is Effective Access Time (EAT), which represents the average time to access memory considering both TLB hits and misses.

Basic EAT Formula:

EAT = (Hit Rate × Hit Time) + (Miss Rate × Miss Time)

Where:
  Hit Rate = TLB hit probability (α)
  Miss Rate = 1 - Hit Rate = (1 - α)
  Hit Time = TLB access time + Memory access time
  Miss Time = TLB access time + Page table walk time + Memory access time

Simplified Formula (assuming TLB accessed in parallel with memory or very fast):

EAT = α × m + (1 - α) × (m + p)
    = α × m + (1 - α) × m + (1 - α) × p
    = m + (1 - α) × p

Where:
  m = Memory access time
  p = Page table walk penalty (additional memory accesses × m)
  α = TLB hit ratio

Example 1: Single-Level Page Table

Given:

Memory access time (m): 100 ns
TLB access time: 10 ns
TLB hit ratio (α): 98%
Single-level page table (1 memory access on miss)

TLB Hit Path:

Time = TLB lookup + Memory access
     = 10 + 100 = 110 ns

TLB Miss Path:

Time = TLB lookup + Page table access + Memory access
     = 10 + 100 + 100 = 210 ns

EAT Calculation:

EAT = (0.98 × 110) + (0.02 × 210)
    = 107.8 + 4.2
    = 112 ns

Performance Impact:

Without TLB (always walk): 200 ns
With TLB: 112 ns
Speedup: 200/112 = 1.79× (44% reduction in access time)

Example 2: Four-Level Page Table (x86-64)

Given:

Memory access time (m): 100 ns
TLB access time: 5 ns
TLB hit ratio (α): 99%
Four-level page table (4 memory accesses on miss)

TLB Hit Path:

Time = 5 + 100 = 105 ns

TLB Miss Path:

Time = 5 + (4 × 100) + 100 = 505 ns

EAT Calculation:

EAT = (0.99 × 105) + (0.01 × 505)
    = 103.95 + 5.05
    = 109 ns

Key Insight: Even with the 4-level page table penalty (500 ns on miss), the high TLB hit ratio keeps EAT reasonable. If hit ratio dropped to 90%:

EAT = (0.90 × 105) + (0.10 × 505)
    = 94.5 + 50.5
    = 145 ns (38% slower than 99% hit ratio)

eat_calculator.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
def calculate_eat(
    memory_time_ns: float,
    tlb_time_ns: float,
    tlb_hit_ratio: float,
    page_table_levels: int
) -> dict:
    """
    Calculate Effective Access Time for TLB-based memory system.
    
    Args:
        memory_time_ns: Time for single memory access
        tlb_time_ns: TLB lookup time
        tlb_hit_ratio: Probability of TLB hit (0 to 1)
        page_table_levels: Number of page table levels to walk on miss
        
    Returns:
        Dictionary with timing analysis
    """
    # Calculate hit and miss times
    hit_time = tlb_time_ns + memory_time_ns
    miss_time = tlb_time_ns + (page_table_levels * memory_time_ns) + memory_time_ns
    
    # Calculate EAT
    eat = (tlb_hit_ratio * hit_time) + ((1 - tlb_hit_ratio) * miss_time)
    
    # Calculate without TLB for comparison
    no_tlb_time = (page_table_levels + 1) * memory_time_ns
    
    # Calculate slowdown factors
    overhead = eat - memory_time_ns
    overhead_percent = (overhead / memory_time_ns) * 100
    
    speedup = no_tlb_time / eat
    
    return {
        'hit_time_ns': hit_time,
        'miss_time_ns': miss_time,
        'eat_ns': round(eat, 2),
        'no_tlb_time_ns': no_tlb_time,
        'speedup_from_tlb': round(speedup, 2),
        'overhead_ns': round(overhead, 2),
        'overhead_percent': round(overhead_percent, 1)
    }
 
# Example: 4-level page table with varying hit ratios
print("TLB Hit Ratio Analysis (4-level, m=100ns):")
print("-" * 60)
for hit_ratio in [0.90, 0.95, 0.98, 0.99, 0.999]:
    result = calculate_eat(
        memory_time_ns=100,
        tlb_time_ns=5,
        tlb_hit_ratio=hit_ratio,
        page_table_levels=4
    )
    print(f"Hit ratio {hit_ratio*100:5.1f}%: EAT = {result['eat_ns']:6.1f}ns, "
          f"Overhead = {result['overhead_percent']:4.1f}%")

The 99% Threshold

Notice how performance degrades rapidly below 99% hit ratio for systems with deep page table hierarchies. This is why TLB design focuses on maximizing hit ratios through size, associativity, and reach (via huge pages).

TLB Reach and Coverage

TLB Reach is the total amount of memory that can be accessed without TLB misses when the TLB is fully utilized.

TLB Reach Formula:

TLB Reach = Number of TLB Entries × Page Size

Example Calculations:

For a 64-entry TLB:

With 4 KB pages: Reach = 64 × 4 KB = 256 KB
With 2 MB pages: Reach = 64 × 2 MB = 128 MB
With 1 GB pages: Reach = 64 × 1 GB = 64 GB

Huge Pages Impact:

Huge pages dramatically increase TLB reach, which is why they're essential for applications with large working sets (databases, scientific computing, VMs).

TLB Reach by Configuration
TLB Entries	4 KB Pages	2 MB Pages	1 GB Pages
64	256 KB	128 MB	64 GB
128	512 KB	256 MB	128 GB
512	2 MB	1 GB	512 GB
2048	8 MB	4 GB	2 TB

Working Set and Hit Ratio Relationship:

The TLB hit ratio depends on the relationship between working set size and TLB reach:

Case 1: Working Set < TLB Reach

Almost all pages fit in TLB
Hit ratio ≈ 99%+
Example: 128 KB working set, 256 KB TLB reach

Case 2: Working Set ≈ TLB Reach

Frequent evictions and reloads
Hit ratio: 80-95% depending on access pattern
Example: 300 KB working set, 256 KB TLB reach

Case 3: Working Set >> TLB Reach

TLB thrashing if random access
Hit ratio can drop to 50% or lower
Sequential access patterns still achieve high hit ratios
Example: 100 MB working set, 256 KB TLB reach with random access

Estimating Hit Ratio from Working Set:

Approximate hit ratio (random access) = min(1.0, TLB_Reach / Working_Set_Size)

This is a rough lower bound; actual patterns often achieve higher ratios due to locality.

Multiple TLB Levels

Modern CPUs have multiple TLB levels (L1 DTLB, L1 ITLB, L2 STLB). The L1 TLBs are small and fast; the L2 TLB is larger and slower. EAT calculations become more complex with multi-level TLBs, requiring separate hit/miss paths for each level.

Multi-Level TLB EAT Example:

Given:

L1 TLB: 64 entries, 2 ns access, 95% hit rate
L2 TLB: 512 entries, 8 ns access, 99% hit rate (for L1 misses)
Memory access: 100 ns
Page table levels: 4

Paths:

L1 TLB Hit (95%):

Time = L1_TLB + Memory = 2 + 100 = 102 ns

L1 Miss, L2 Hit (5% × 99% = 4.95%):

Time = L1_TLB + L2_TLB + Memory = 2 + 8 + 100 = 110 ns

Both Miss (5% × 1% = 0.05%):

Time = L1_TLB + L2_TLB + (4 × Memory) + Memory
     = 2 + 8 + 400 + 100 = 510 ns

EAT:

EAT = (0.95 × 102) + (0.0495 × 110) + (0.0005 × 510)
    = 96.9 + 5.445 + 0.255
    = 102.6 ns

The two-level TLB reduces EAT from what would be 109 ns with a single-level design of equivalent size.

TLB Miss Rate Analysis

Understanding what causes TLB misses helps predict and optimize hit ratios.

Types of TLB Misses:

1. Compulsory Misses (Cold Misses):

First access to a page always misses
Unavoidable unless prefetching
Reduced by larger pages (fewer pages to miss on)

2. Capacity Misses:

Working set exceeds TLB capacity
Pages evicted and later re-accessed
Reduced by larger TLB or larger pages

3. Conflict Misses (Set-Associative TLBs):

Multiple pages map to same TLB set
Evictions despite overall TLB space available
Reduced by higher associativity

4. Coherency Misses (TLB Shootdowns):

Other CPU invalidates entry
Common in multi-processor systems with shared pages
Reduced by ASID tagging, careful memory layout

Miss Rate Estimation Techniques:

Analytical Estimation:

For a program accessing N unique pages with a TLB of size T entries:

Compulsory miss rate = N / Total_Accesses

Capacity miss rate (uniform random access) ≈ max(0, (N - T) / N)

Approximate total miss rate = Compulsory + Capacity (assuming high associativity)

Example:

Program accesses 10,000 unique pages
1,000,000 total memory accesses
TLB has 128 entries

Compulsory miss rate = 10,000 / 1,000,000 = 1%

If random access pattern:
  Capacity miss rate ≈ (10,000 - 128) / 10,000 = 98.7%
  (Effectively, TLB provides minimal benefit)

If sequential with temporal locality:
  Capacity miss rate ≈ Pages / (Accesses per page × TLB_Size)
  = 10,000 / (100 × 128) ≈ 0.78%
  Total miss rate ≈ 1.78%

Access Pattern Matters Enormously

The same working set can have vastly different TLB miss rates depending on access pattern. Random access through 10,000 pages thrashes the TLB. Sequential access through the same 10,000 pages achieves near-optimal hit rate. This is why databases and scientific applications carefully optimize memory access patterns.

Locality and TLB Performance:

Temporal Locality:

Recently accessed pages likely accessed again soon
TLB naturally exploits this (recently used entries still present)
LRU replacement policy optimizes for temporal locality

Spatial Locality:

Nearby addresses accessed together
A single TLB entry covers entire page
4 KB page: 1024 consecutive 4-byte accesses with 1 TLB miss
2 MB page: 524,288 consecutive 4-byte accesses with 1 TLB miss

Stride Access Pattern:

When accessing memory with stride S:

If S < Page_Size:
  Multiple accesses per TLB entry
  Effective miss rate = 1 / (Page_Size / S)
  
If S >= Page_Size:
  One access per TLB entry
  Miss rate depends entirely on TLB size vs working set

Example: Matrix Column Access

Accessing a column of a row-major matrix:

Matrix: 4096 × 4096 floats (4 bytes each)
Row size: 4096 × 4 = 16 KB = 4 pages
Column access stride: 16 KB

With 4 KB pages and 128-entry TLB:

Each column element is on a different page
4096 unique pages accessed
TLB can only hold 128
Miss rate ≈ (4096 - 128) / 4096 = 96.9%

With 2 MB huge pages:

Row size = 16 KB, Page size = 2 MB
128 rows fit per huge page
Only 32 huge pages for entire matrix
All 32 fit in TLB!
Miss rate = 32 / 4096 = 0.78%

TLB Shootdowns and Context Switches

TLB hit ratio isn't just about TLB size—it's also affected by TLB invalidation events.

Context Switch TLB Behavior:

When switching between processes:

Without ASID (older systems):

All TLB entries become invalid
New process starts with empty TLB
Every memory access initially misses
Compulsory misses until working set cached

With ASID (modern systems):

Entries retain ASID tags
New process's entries missed, but old entries preserved
Switching back finds entries still valid
Reduces overhead of rapid context switches

ASID Impact Calculation:

Given:

TLB: 256 entries, ASID-tagged
Process A working set: 128 pages
Process B working set: 64 pages
Context switch frequency: Every 1,000 memory accesses

Without ASID:

Every switch: 128 or 64 compulsory misses
Miss overhead per 1,000 accesses: ~10% (if 100 misses average)

With ASID:

Both working sets fit in TLB: 128 + 64 = 192 < 256
After initial warmup: ~0% switch-related misses

TLB Shootdowns in Multiprocessor Systems:

When page mappings change (munmap, mprotect, page migration), all CPUs must invalidate the affected TLB entries.

Shootdown Process:

CPU 0 modifies page table
CPU 0 sends IPI (Inter-Processor Interrupt) to other CPUs
Each CPU handles interrupt, invalidates specified entries
Each CPU acknowledges completion
CPU 0 continues after all acknowledgments

Shootdown Cost:

Shootdown latency = IPI_latency + Handler_time + Acknowledgment_latency
Typically: 5-50 microseconds per shootdown

Impact on Performance:

Each shootdown invalidates entries across all CPUs
Subsequent accesses miss until TLB re-warmed
Frequent page mapping changes cause cascading misses

Example: Memory-Mapped File Updates

Database unmaps and remaps 1 GB file region frequently
With 4 KB pages: 262,144 pages to invalidate
With 2 MB pages: 512 pages to invalidate

Shootdown entries per operation:
  4 KB: 262,144 entries (may require batching)
  2 MB: 512 entries (single shootdown possible)

PCID (Process-Context Identifiers)

Modern x86-64 processors with PCID (similar to ASID) can avoid flushing TLB entries on context switch and can even do lazy TLB shootdowns. The kernel tracks which entries need invalidation and batches the work, significantly improving multicore scalability.

Advanced EAT Calculations

Real systems have additional complexity that affects EAT calculations.

Including Page Faults:

Page faults are rare but extremely expensive:

EAT = (Hit_Rate × Hit_Time) + 
      (TLB_Miss_Rate × In_Memory × Miss_Time) +
      (TLB_Miss_Rate × Not_In_Memory × Page_Fault_Time)

Example with Page Faults:

Given:

Memory access time: 100 ns
TLB access time: 5 ns
TLB hit ratio: 98%
Page table levels: 4
Page fault probability (when TLB misses): 0.1%
Page fault time: 10 ms = 10,000,000 ns

Calculation:

TLB Hit: 5 + 100 = 105 ns (98%)
TLB Miss, No Page Fault: 5 + 400 + 100 = 505 ns (2% × 99.9% = 1.998%)
TLB Miss, Page Fault: 5 + 10,000,000 = 10,000,005 ns (2% × 0.1% = 0.002%)

EAT = (0.98 × 105) + (0.01998 × 505) + (0.00002 × 10,000,005)
    = 102.9 + 10.09 + 200
    = 312.99 ns

Key Insight: Even at 0.002% occurrence rate, page faults triple the EAT! This is why page fault minimization is critical for performance.

Hierarchical Caching Effects:

Modern systems have multiple cache levels. Page table walks often hit data caches:

Given:

L1 cache: 32 KB, 1 ns access
L2 cache: 256 KB, 10 ns access
L3 cache: 8 MB, 40 ns access
Memory: 100 ns access
Page table entries are 8 bytes each

Page Table Entry Cache Behavior:

Page table entries are just memory—they get cached like any data.

PML4 entry: Accessed every translation, almost always in L1
PDPT entry: One per 512 GB, usually in L1/L2
PD entry: One per 1 GB, often in L2/L3
PT entry: One per 2 MB, may miss caches

Effective Page Walk Cost:

With cold caches: 4 × 100 = 400 ns
With warm caches: 1 + 1 + 10 + 40 = 52 ns
Typical (mixed): 1 + 1 + 10 + 60 = 72 ns

This significantly reduces the TLB miss penalty in practice.

advanced_eat.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
73
74
75
def advanced_eat(
    tlb_hit_ratio: float,
    tlb_time: float,
    mem_time: float,
    pt_levels: int,
    page_fault_rate: float = 0.0,
    page_fault_time: float = 0.0,
    pt_cache_hit_ratio: float = 0.0,
    cache_time: float = 0.0
) -> dict:
    """
    Calculate EAT with page faults and cache effects.
    
    Args:
        tlb_hit_ratio: TLB hit probability
        tlb_time: TLB lookup time (ns)
        mem_time: Memory access time (ns)
        pt_levels: Page table levels
        page_fault_rate: P(page fault | TLB miss)
        page_fault_time: Page fault handling time (ns)
        pt_cache_hit_ratio: P(PT entries in cache)
        cache_time: Average cache access time for PT (ns)
    """
    # TLB hit time
    hit_time = tlb_time + mem_time
    
    # Page table walk time (considering cache)
    if pt_cache_hit_ratio > 0:
        pt_walk_time = pt_levels * (
            pt_cache_hit_ratio * cache_time + 
            (1 - pt_cache_hit_ratio) * mem_time
        )
    else:
        pt_walk_time = pt_levels * mem_time
    
    # TLB miss, page in memory
    miss_in_mem_time = tlb_time + pt_walk_time + mem_time
    
    # TLB miss, page fault
    miss_page_fault_time = tlb_time + page_fault_time
    
    # Calculate probabilities
    p_hit = tlb_hit_ratio
    p_miss_in_mem = (1 - tlb_hit_ratio) * (1 - page_fault_rate)
    p_miss_fault = (1 - tlb_hit_ratio) * page_fault_rate
    
    # EAT
    eat = (p_hit * hit_time + 
           p_miss_in_mem * miss_in_mem_time +
           p_miss_fault * miss_page_fault_time)
    
    return {
        'eat_ns': round(eat, 2),
        'hit_time_ns': hit_time,
        'miss_in_mem_time_ns': round(miss_in_mem_time, 2),
        'miss_fault_time_ns': miss_page_fault_time,
        'p_hit': p_hit,
        'p_miss_in_mem': round(p_miss_in_mem, 6),
        'p_miss_fault': round(p_miss_fault, 6)
    }
 
# Example with page faults and cache effects
result = advanced_eat(
    tlb_hit_ratio=0.98,
    tlb_time=5,
    mem_time=100,
    pt_levels=4,
    page_fault_rate=0.001,
    page_fault_time=10_000_000,  # 10ms
    pt_cache_hit_ratio=0.75,
    cache_time=20
)
 
for k, v in result.items():
    print(f"{k}: {v}")

Practice Problems with Solutions

Work through these problems to solidify your understanding of TLB performance calculations.

Problem 1: Basic EAT

A system has 100ns memory access time, 10ns TLB access time, two-level page table, and 95% TLB hit ratio. Calculate the EAT. How much faster would it be with 99% hit ratio?

With 95% hit ratio:

TLB Hit: 10 + 100 = 110 ns (95%)
TLB Miss: 10 + (2 × 100) + 100 = 310 ns (5%)

EAT = 0.95 × 110 + 0.05 × 310
    = 104.5 + 15.5
    = 120 ns

With 99% hit ratio:

EAT = 0.99 × 110 + 0.01 × 310
    = 108.9 + 3.1
    = 112 ns

Speedup = 120/112 = 1.07× (7% faster)

Alternatively: Going from 5% to 1% miss rate reduces miss-related time from 15.5ns to 3.1ns = 12.4ns savings per access.

Problem 2: TLB Reach

A program has a 4 MB working set. The TLB has 64 entries. (a) With 4 KB pages, what is the TLB reach? (b) What hit ratio can be expected (assume random access)? (c) What page size would achieve 95%+ hit ratio?

(a) TLB Reach with 4 KB pages:

Reach = 64 × 4 KB = 256 KB

(b) Expected hit ratio:

Working set = 4 MB = 4096 KB
Pages in working set = 4096 / 4 = 1024 pages
TLB can hold: 64 pages

Approximate hit ratio (random) = 64 / 1024 = 6.25%

(Very poor performance due to TLB thrashing)

(c) Page size for 95% hit ratio:

Need: TLB Reach ≥ Working Set × 0.95
64 × Page_Size ≥ 4 MB × 0.95 = 3.8 MB
Page_Size ≥ 3.8 MB / 64 ≈ 60.8 KB

Nearest standard size: 64 KB or 2 MB huge pages

With 2 MB pages:

Reach = 64 × 2 MB = 128 MB >> 4 MB
Expected hit ratio ≈ 100% (after warmup)

Problem 3: Two-Level TLB

A system has: L1 TLB (32 entries, 1 cycle, 90% hit), L2 TLB (256 entries, 4 cycles, 98% hit of L1 misses), memory (200 cycles), 4-level page table. CPU clock: 2 GHz. Calculate EAT in nanoseconds.

Convert cycles to ns:

1 cycle at 2 GHz = 0.5 ns
L1 TLB: 1 × 0.5 = 0.5 ns
L2 TLB: 4 × 0.5 = 2 ns
Memory: 200 × 0.5 = 100 ns

Calculate paths:

L1 Hit: 0.5 + 100 = 100.5 ns (90%)

L1 Miss, L2 Hit: 0.5 + 2 + 100 = 102.5 ns 
  (10% × 98% = 9.8%)

Both Miss: 0.5 + 2 + (4 × 100) + 100 = 502.5 ns
  (10% × 2% = 0.2%)

EAT:

EAT = 0.90 × 100.5 + 0.098 × 102.5 + 0.002 × 502.5
    = 90.45 + 10.045 + 1.005
    = 101.5 ns

Problem 4: Page Fault Impact

Continuing from Problem 3, if 0.01% of TLB misses result in page faults taking 5 ms, what is the new EAT?

New path breakdown:

L1 Hit: 100.5 ns (90%)
L1 Miss, L2 Hit, No Fault: 102.5 ns (9.8% × 99.99% = 9.799%)
L1 Miss, L2 Hit, Fault: 5,000,000 ns (9.8% × 0.01% = 0.00098%)
Both Miss, No Fault: 502.5 ns (0.2% × 99.99% = 0.19998%)
Both Miss, Fault: 5,000,000 ns (0.2% × 0.01% = 0.00002%)

EAT:

EAT = 0.90 × 100.5 
    + 0.09799 × 102.5 
    + 0.0000098 × 5,000,000
    + 0.0019998 × 502.5
    + 0.0000002 × 5,000,000

    = 90.45 + 10.04 + 49 + 1.00 + 1
    = 151.49 ns

Impact: Page faults at 0.01% rate increased EAT from 101.5 to 151.5 ns—a 49% increase from 0.001% of accesses!

Summary: TLB Hit Ratio Calculations

Key Takeaways

•EAT = α × Hit_Time + (1-α) × Miss_Time — The fundamental TLB performance equation
•TLB Reach = Entries × Page_Size — Determines how much working set fits without misses
•Access pattern dominates hit ratio — Sequential access can achieve 99%+ even with large working sets
•Multi-level TLBs reduce miss penalty — L2 TLB catches most L1 misses cheaply
•Page faults are extremely costly — Even 0.01% fault rate significantly impacts EAT
•Cache effects help page walks — Page table entries get cached, reducing miss penalty

Essential Formulas:

EAT = (TLB_Hit_Rate × Hit_Time) + (TLB_Miss_Rate × Miss_Time)

TLB Reach = TLB_Entries × Page_Size

Estimated Hit Ratio (random) ≈ min(1.0, TLB_Reach / Working_Set)

Page Walk Time = Page_Table_Levels × Memory_Access_Time

What's Next:

We've analyzed TLB performance. Next, we'll examine disk scheduling seek time calculations, applying similar quantitative analysis to storage I/O.

Page Complete

You now have comprehensive knowledge of TLB hit ratio calculations, including basic EAT, multi-level TLBs, TLB reach analysis, and the impact of page faults and caching. Practice with various configurations to build speed and accuracy.

3 / 5

Loading learning content...

Operating SystemsOS Design & Interview

Numerical Problems in Operating Systems

LevelAdvanced

Duration180 mins

TopicOS Design & Interview

3 / 5

TLB Hit Ratio Calculations

The Translation Lookaside Buffer: Virtual Memory's Critical Bottleneck

Understanding TLB hit ratio calculations is essential because:

They determine effective memory access time
They reveal the performance impact of page size decisions
They expose workload-dependent performance characteristics
They're extremely common in technical interviews

What You Will Master

TLB Fundamentals

Before calculating TLB performance, we must understand TLB architecture and operation.

TLB Structure:

A TLB entry contains:

Virtual Page Number (VPN): The key for lookup
Physical Frame Number (PFN): The translated result
Valid Bit: Is this entry currently valid?
Protection Bits: R/W/X permissions
ASID (Address Space ID): Which process owns this entry
Other flags: Global, dirty, accessed, etc.

TLB Lookup Process:

CPU issues virtual address
TLB receives the VPN portion
TLB searches for matching entry (in parallel for fully-associative)
If found (hit): Return PFN, translation complete
If not found (miss): Page table walk required

Typical TLB Characteristics by System
System	TLB Size	Associativity	TLB Access Time	Memory Time
x86-64 (L1 DTLB)	64-96 entries	4-way/fully	1-3 cycles	100+ cycles
x86-64 (L2 TLB)	512-2048 entries	4-8 way	6-8 cycles	100+ cycles
ARM Cortex-A	32-128 entries	Fully assoc	1 cycle	50-100 cycles
RISC-V	16-64 entries	Fully assoc	1 cycle	Variable

TLB Miss Handling:

When a TLB miss occurs, one of two mechanisms handles it:

Hardware-Managed TLB (x86, ARM):

Hardware automatically walks the page table
Found entry loaded into TLB
Original instruction restarted
Typical cost: 10-100 cycles

Software-Managed TLB (MIPS, SPARC, some RISC-V):

TLB miss generates exception
OS handler walks page table
OS loads TLB entry with special instruction
Return from exception, instruction restarted
Typical cost: 100-1000 cycles

Page Fault (page not in memory):

Even after TLB miss handling, the page might not be in physical memory
This triggers a page fault: disk I/O required
Cost: millions of cycles (milliseconds)

TLB vs Page Table Entry Cache

Basic Effective Access Time (EAT) Calculation

The fundamental TLB performance metric is Effective Access Time (EAT), which represents the average time to access memory considering both TLB hits and misses.

Basic EAT Formula:

EAT = (Hit Rate × Hit Time) + (Miss Rate × Miss Time)

Where:
  Hit Rate = TLB hit probability (α)
  Miss Rate = 1 - Hit Rate = (1 - α)
  Hit Time = TLB access time + Memory access time
  Miss Time = TLB access time + Page table walk time + Memory access time

Simplified Formula (assuming TLB accessed in parallel with memory or very fast):

EAT = α × m + (1 - α) × (m + p)
    = α × m + (1 - α) × m + (1 - α) × p
    = m + (1 - α) × p

Where:
  m = Memory access time
  p = Page table walk penalty (additional memory accesses × m)
  α = TLB hit ratio

Example 1: Single-Level Page Table

Given:

Memory access time (m): 100 ns
TLB access time: 10 ns
TLB hit ratio (α): 98%
Single-level page table (1 memory access on miss)

TLB Hit Path:

Time = TLB lookup + Memory access
     = 10 + 100 = 110 ns

TLB Miss Path:

Time = TLB lookup + Page table access + Memory access
     = 10 + 100 + 100 = 210 ns

EAT Calculation:

EAT = (0.98 × 110) + (0.02 × 210)
    = 107.8 + 4.2
    = 112 ns

Performance Impact:

Without TLB (always walk): 200 ns
With TLB: 112 ns
Speedup: 200/112 = 1.79× (44% reduction in access time)

Example 2: Four-Level Page Table (x86-64)

Given:

Memory access time (m): 100 ns
TLB access time: 5 ns
TLB hit ratio (α): 99%
Four-level page table (4 memory accesses on miss)

TLB Hit Path:

Time = 5 + 100 = 105 ns

TLB Miss Path:

Time = 5 + (4 × 100) + 100 = 505 ns

EAT Calculation:

EAT = (0.99 × 105) + (0.01 × 505)
    = 103.95 + 5.05
    = 109 ns

Key Insight: Even with the 4-level page table penalty (500 ns on miss), the high TLB hit ratio keeps EAT reasonable. If hit ratio dropped to 90%:

EAT = (0.90 × 105) + (0.10 × 505)
    = 94.5 + 50.5
    = 145 ns (38% slower than 99% hit ratio)

eat_calculator.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
def calculate_eat(
    memory_time_ns: float,
    tlb_time_ns: float,
    tlb_hit_ratio: float,
    page_table_levels: int
) -> dict:
    """
    Calculate Effective Access Time for TLB-based memory system.
    
    Args:
        memory_time_ns: Time for single memory access
        tlb_time_ns: TLB lookup time
        tlb_hit_ratio: Probability of TLB hit (0 to 1)
        page_table_levels: Number of page table levels to walk on miss
        
    Returns:
        Dictionary with timing analysis
    """
    # Calculate hit and miss times
    hit_time = tlb_time_ns + memory_time_ns
    miss_time = tlb_time_ns + (page_table_levels * memory_time_ns) + memory_time_ns
    
    # Calculate EAT
    eat = (tlb_hit_ratio * hit_time) + ((1 - tlb_hit_ratio) * miss_time)
    
    # Calculate without TLB for comparison
    no_tlb_time = (page_table_levels + 1) * memory_time_ns
    
    # Calculate slowdown factors
    overhead = eat - memory_time_ns
    overhead_percent = (overhead / memory_time_ns) * 100
    
    speedup = no_tlb_time / eat
    
    return {
        'hit_time_ns': hit_time,
        'miss_time_ns': miss_time,
        'eat_ns': round(eat, 2),
        'no_tlb_time_ns': no_tlb_time,
        'speedup_from_tlb': round(speedup, 2),
        'overhead_ns': round(overhead, 2),
        'overhead_percent': round(overhead_percent, 1)
    }
 
# Example: 4-level page table with varying hit ratios
print("TLB Hit Ratio Analysis (4-level, m=100ns):")
print("-" * 60)
for hit_ratio in [0.90, 0.95, 0.98, 0.99, 0.999]:
    result = calculate_eat(
        memory_time_ns=100,
        tlb_time_ns=5,
        tlb_hit_ratio=hit_ratio,
        page_table_levels=4
    )
    print(f"Hit ratio {hit_ratio*100:5.1f}%: EAT = {result['eat_ns']:6.1f}ns, "
          f"Overhead = {result['overhead_percent']:4.1f}%")

The 99% Threshold

TLB Reach and Coverage

TLB Reach is the total amount of memory that can be accessed without TLB misses when the TLB is fully utilized.

TLB Reach Formula:

TLB Reach = Number of TLB Entries × Page Size

Example Calculations:

For a 64-entry TLB:

With 4 KB pages: Reach = 64 × 4 KB = 256 KB
With 2 MB pages: Reach = 64 × 2 MB = 128 MB
With 1 GB pages: Reach = 64 × 1 GB = 64 GB

Huge Pages Impact:

Huge pages dramatically increase TLB reach, which is why they're essential for applications with large working sets (databases, scientific computing, VMs).

TLB Reach by Configuration
TLB Entries	4 KB Pages	2 MB Pages	1 GB Pages
64	256 KB	128 MB	64 GB
128	512 KB	256 MB	128 GB
512	2 MB	1 GB	512 GB
2048	8 MB	4 GB	2 TB

Working Set and Hit Ratio Relationship:

The TLB hit ratio depends on the relationship between working set size and TLB reach:

Case 1: Working Set < TLB Reach

Almost all pages fit in TLB
Hit ratio ≈ 99%+
Example: 128 KB working set, 256 KB TLB reach

Case 2: Working Set ≈ TLB Reach

Frequent evictions and reloads
Hit ratio: 80-95% depending on access pattern
Example: 300 KB working set, 256 KB TLB reach

Case 3: Working Set >> TLB Reach

TLB thrashing if random access
Hit ratio can drop to 50% or lower
Sequential access patterns still achieve high hit ratios
Example: 100 MB working set, 256 KB TLB reach with random access

Estimating Hit Ratio from Working Set:

Approximate hit ratio (random access) = min(1.0, TLB_Reach / Working_Set_Size)

This is a rough lower bound; actual patterns often achieve higher ratios due to locality.

Multiple TLB Levels

Multi-Level TLB EAT Example:

Given:

L1 TLB: 64 entries, 2 ns access, 95% hit rate
L2 TLB: 512 entries, 8 ns access, 99% hit rate (for L1 misses)
Memory access: 100 ns
Page table levels: 4

Paths:

L1 TLB Hit (95%):

Time = L1_TLB + Memory = 2 + 100 = 102 ns

L1 Miss, L2 Hit (5% × 99% = 4.95%):

Time = L1_TLB + L2_TLB + Memory = 2 + 8 + 100 = 110 ns

Both Miss (5% × 1% = 0.05%):

Time = L1_TLB + L2_TLB + (4 × Memory) + Memory
     = 2 + 8 + 400 + 100 = 510 ns

EAT:

EAT = (0.95 × 102) + (0.0495 × 110) + (0.0005 × 510)
    = 96.9 + 5.445 + 0.255
    = 102.6 ns

The two-level TLB reduces EAT from what would be 109 ns with a single-level design of equivalent size.

TLB Miss Rate Analysis

Understanding what causes TLB misses helps predict and optimize hit ratios.

Types of TLB Misses:

1. Compulsory Misses (Cold Misses):

First access to a page always misses
Unavoidable unless prefetching
Reduced by larger pages (fewer pages to miss on)

2. Capacity Misses:

Working set exceeds TLB capacity
Pages evicted and later re-accessed
Reduced by larger TLB or larger pages

3. Conflict Misses (Set-Associative TLBs):

Multiple pages map to same TLB set
Evictions despite overall TLB space available
Reduced by higher associativity

4. Coherency Misses (TLB Shootdowns):

Other CPU invalidates entry
Common in multi-processor systems with shared pages
Reduced by ASID tagging, careful memory layout

Miss Rate Estimation Techniques:

Analytical Estimation:

For a program accessing N unique pages with a TLB of size T entries:

Compulsory miss rate = N / Total_Accesses

Capacity miss rate (uniform random access) ≈ max(0, (N - T) / N)

Approximate total miss rate = Compulsory + Capacity (assuming high associativity)

Example:

Program accesses 10,000 unique pages
1,000,000 total memory accesses
TLB has 128 entries

Compulsory miss rate = 10,000 / 1,000,000 = 1%

If random access pattern:
  Capacity miss rate ≈ (10,000 - 128) / 10,000 = 98.7%
  (Effectively, TLB provides minimal benefit)

If sequential with temporal locality:
  Capacity miss rate ≈ Pages / (Accesses per page × TLB_Size)
  = 10,000 / (100 × 128) ≈ 0.78%
  Total miss rate ≈ 1.78%

Access Pattern Matters Enormously

Locality and TLB Performance:

Temporal Locality:

Recently accessed pages likely accessed again soon
TLB naturally exploits this (recently used entries still present)
LRU replacement policy optimizes for temporal locality

Spatial Locality:

Nearby addresses accessed together
A single TLB entry covers entire page
4 KB page: 1024 consecutive 4-byte accesses with 1 TLB miss
2 MB page: 524,288 consecutive 4-byte accesses with 1 TLB miss

Stride Access Pattern:

When accessing memory with stride S:

If S < Page_Size:
  Multiple accesses per TLB entry
  Effective miss rate = 1 / (Page_Size / S)
  
If S >= Page_Size:
  One access per TLB entry
  Miss rate depends entirely on TLB size vs working set

Example: Matrix Column Access

Accessing a column of a row-major matrix:

Matrix: 4096 × 4096 floats (4 bytes each)
Row size: 4096 × 4 = 16 KB = 4 pages
Column access stride: 16 KB

With 4 KB pages and 128-entry TLB:

Each column element is on a different page
4096 unique pages accessed
TLB can only hold 128
Miss rate ≈ (4096 - 128) / 4096 = 96.9%

With 2 MB huge pages:

Row size = 16 KB, Page size = 2 MB
128 rows fit per huge page
Only 32 huge pages for entire matrix
All 32 fit in TLB!
Miss rate = 32 / 4096 = 0.78%

TLB Shootdowns and Context Switches

TLB hit ratio isn't just about TLB size—it's also affected by TLB invalidation events.

Context Switch TLB Behavior:

When switching between processes:

Without ASID (older systems):

All TLB entries become invalid
New process starts with empty TLB
Every memory access initially misses
Compulsory misses until working set cached

With ASID (modern systems):

Entries retain ASID tags
New process's entries missed, but old entries preserved
Switching back finds entries still valid
Reduces overhead of rapid context switches

ASID Impact Calculation:

Given:

TLB: 256 entries, ASID-tagged
Process A working set: 128 pages
Process B working set: 64 pages
Context switch frequency: Every 1,000 memory accesses

Without ASID:

Every switch: 128 or 64 compulsory misses
Miss overhead per 1,000 accesses: ~10% (if 100 misses average)

With ASID:

Both working sets fit in TLB: 128 + 64 = 192 < 256
After initial warmup: ~0% switch-related misses

TLB Shootdowns in Multiprocessor Systems:

When page mappings change (munmap, mprotect, page migration), all CPUs must invalidate the affected TLB entries.

Shootdown Process:

CPU 0 modifies page table
CPU 0 sends IPI (Inter-Processor Interrupt) to other CPUs
Each CPU handles interrupt, invalidates specified entries
Each CPU acknowledges completion
CPU 0 continues after all acknowledgments

Shootdown Cost:

Shootdown latency = IPI_latency + Handler_time + Acknowledgment_latency
Typically: 5-50 microseconds per shootdown

Impact on Performance:

Each shootdown invalidates entries across all CPUs
Subsequent accesses miss until TLB re-warmed
Frequent page mapping changes cause cascading misses

Example: Memory-Mapped File Updates

Database unmaps and remaps 1 GB file region frequently
With 4 KB pages: 262,144 pages to invalidate
With 2 MB pages: 512 pages to invalidate

Shootdown entries per operation:
  4 KB: 262,144 entries (may require batching)
  2 MB: 512 entries (single shootdown possible)

PCID (Process-Context Identifiers)

Advanced EAT Calculations

Real systems have additional complexity that affects EAT calculations.

Including Page Faults:

Page faults are rare but extremely expensive:

EAT = (Hit_Rate × Hit_Time) + 
      (TLB_Miss_Rate × In_Memory × Miss_Time) +
      (TLB_Miss_Rate × Not_In_Memory × Page_Fault_Time)

Example with Page Faults:

Given:

Memory access time: 100 ns
TLB access time: 5 ns
TLB hit ratio: 98%
Page table levels: 4
Page fault probability (when TLB misses): 0.1%
Page fault time: 10 ms = 10,000,000 ns

Calculation:

TLB Hit: 5 + 100 = 105 ns (98%)
TLB Miss, No Page Fault: 5 + 400 + 100 = 505 ns (2% × 99.9% = 1.998%)
TLB Miss, Page Fault: 5 + 10,000,000 = 10,000,005 ns (2% × 0.1% = 0.002%)

EAT = (0.98 × 105) + (0.01998 × 505) + (0.00002 × 10,000,005)
    = 102.9 + 10.09 + 200
    = 312.99 ns

Key Insight: Even at 0.002% occurrence rate, page faults triple the EAT! This is why page fault minimization is critical for performance.

Hierarchical Caching Effects:

Modern systems have multiple cache levels. Page table walks often hit data caches:

Given:

L1 cache: 32 KB, 1 ns access
L2 cache: 256 KB, 10 ns access
L3 cache: 8 MB, 40 ns access
Memory: 100 ns access
Page table entries are 8 bytes each

Page Table Entry Cache Behavior:

Page table entries are just memory—they get cached like any data.

PML4 entry: Accessed every translation, almost always in L1
PDPT entry: One per 512 GB, usually in L1/L2
PD entry: One per 1 GB, often in L2/L3
PT entry: One per 2 MB, may miss caches

Effective Page Walk Cost:

With cold caches: 4 × 100 = 400 ns
With warm caches: 1 + 1 + 10 + 40 = 52 ns
Typical (mixed): 1 + 1 + 10 + 60 = 72 ns

This significantly reduces the TLB miss penalty in practice.

advanced_eat.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
73
74
75
def advanced_eat(
    tlb_hit_ratio: float,
    tlb_time: float,
    mem_time: float,
    pt_levels: int,
    page_fault_rate: float = 0.0,
    page_fault_time: float = 0.0,
    pt_cache_hit_ratio: float = 0.0,
    cache_time: float = 0.0
) -> dict:
    """
    Calculate EAT with page faults and cache effects.
    
    Args:
        tlb_hit_ratio: TLB hit probability
        tlb_time: TLB lookup time (ns)
        mem_time: Memory access time (ns)
        pt_levels: Page table levels
        page_fault_rate: P(page fault | TLB miss)
        page_fault_time: Page fault handling time (ns)
        pt_cache_hit_ratio: P(PT entries in cache)
        cache_time: Average cache access time for PT (ns)
    """
    # TLB hit time
    hit_time = tlb_time + mem_time
    
    # Page table walk time (considering cache)
    if pt_cache_hit_ratio > 0:
        pt_walk_time = pt_levels * (
            pt_cache_hit_ratio * cache_time + 
            (1 - pt_cache_hit_ratio) * mem_time
        )
    else:
        pt_walk_time = pt_levels * mem_time
    
    # TLB miss, page in memory
    miss_in_mem_time = tlb_time + pt_walk_time + mem_time
    
    # TLB miss, page fault
    miss_page_fault_time = tlb_time + page_fault_time
    
    # Calculate probabilities
    p_hit = tlb_hit_ratio
    p_miss_in_mem = (1 - tlb_hit_ratio) * (1 - page_fault_rate)
    p_miss_fault = (1 - tlb_hit_ratio) * page_fault_rate
    
    # EAT
    eat = (p_hit * hit_time + 
           p_miss_in_mem * miss_in_mem_time +
           p_miss_fault * miss_page_fault_time)
    
    return {
        'eat_ns': round(eat, 2),
        'hit_time_ns': hit_time,
        'miss_in_mem_time_ns': round(miss_in_mem_time, 2),
        'miss_fault_time_ns': miss_page_fault_time,
        'p_hit': p_hit,
        'p_miss_in_mem': round(p_miss_in_mem, 6),
        'p_miss_fault': round(p_miss_fault, 6)
    }
 
# Example with page faults and cache effects
result = advanced_eat(
    tlb_hit_ratio=0.98,
    tlb_time=5,
    mem_time=100,
    pt_levels=4,
    page_fault_rate=0.001,
    page_fault_time=10_000_000,  # 10ms
    pt_cache_hit_ratio=0.75,
    cache_time=20
)
 
for k, v in result.items():
    print(f"{k}: {v}")

Practice Problems with Solutions

Work through these problems to solidify your understanding of TLB performance calculations.

Problem 1: Basic EAT

A system has 100ns memory access time, 10ns TLB access time, two-level page table, and 95% TLB hit ratio. Calculate the EAT. How much faster would it be with 99% hit ratio?

With 95% hit ratio:

TLB Hit: 10 + 100 = 110 ns (95%)
TLB Miss: 10 + (2 × 100) + 100 = 310 ns (5%)

EAT = 0.95 × 110 + 0.05 × 310
    = 104.5 + 15.5
    = 120 ns

With 99% hit ratio:

EAT = 0.99 × 110 + 0.01 × 310
    = 108.9 + 3.1
    = 112 ns

Speedup = 120/112 = 1.07× (7% faster)

Alternatively: Going from 5% to 1% miss rate reduces miss-related time from 15.5ns to 3.1ns = 12.4ns savings per access.

Problem 2: TLB Reach

(a) TLB Reach with 4 KB pages:

Reach = 64 × 4 KB = 256 KB

(b) Expected hit ratio:

Working set = 4 MB = 4096 KB
Pages in working set = 4096 / 4 = 1024 pages
TLB can hold: 64 pages

Approximate hit ratio (random) = 64 / 1024 = 6.25%

(Very poor performance due to TLB thrashing)

(c) Page size for 95% hit ratio:

Need: TLB Reach ≥ Working Set × 0.95
64 × Page_Size ≥ 4 MB × 0.95 = 3.8 MB
Page_Size ≥ 3.8 MB / 64 ≈ 60.8 KB

Nearest standard size: 64 KB or 2 MB huge pages

With 2 MB pages:

Reach = 64 × 2 MB = 128 MB >> 4 MB
Expected hit ratio ≈ 100% (after warmup)

Problem 3: Two-Level TLB

A system has: L1 TLB (32 entries, 1 cycle, 90% hit), L2 TLB (256 entries, 4 cycles, 98% hit of L1 misses), memory (200 cycles), 4-level page table. CPU clock: 2 GHz. Calculate EAT in nanoseconds.

Convert cycles to ns:

1 cycle at 2 GHz = 0.5 ns
L1 TLB: 1 × 0.5 = 0.5 ns
L2 TLB: 4 × 0.5 = 2 ns
Memory: 200 × 0.5 = 100 ns

Calculate paths:

L1 Hit: 0.5 + 100 = 100.5 ns (90%)

L1 Miss, L2 Hit: 0.5 + 2 + 100 = 102.5 ns 
  (10% × 98% = 9.8%)

Both Miss: 0.5 + 2 + (4 × 100) + 100 = 502.5 ns
  (10% × 2% = 0.2%)

EAT:

EAT = 0.90 × 100.5 + 0.098 × 102.5 + 0.002 × 502.5
    = 90.45 + 10.045 + 1.005
    = 101.5 ns

Problem 4: Page Fault Impact

Continuing from Problem 3, if 0.01% of TLB misses result in page faults taking 5 ms, what is the new EAT?

New path breakdown:

L1 Hit: 100.5 ns (90%)
L1 Miss, L2 Hit, No Fault: 102.5 ns (9.8% × 99.99% = 9.799%)
L1 Miss, L2 Hit, Fault: 5,000,000 ns (9.8% × 0.01% = 0.00098%)
Both Miss, No Fault: 502.5 ns (0.2% × 99.99% = 0.19998%)
Both Miss, Fault: 5,000,000 ns (0.2% × 0.01% = 0.00002%)

EAT:

EAT = 0.90 × 100.5 
    + 0.09799 × 102.5 
    + 0.0000098 × 5,000,000
    + 0.0019998 × 502.5
    + 0.0000002 × 5,000,000

    = 90.45 + 10.04 + 49 + 1.00 + 1
    = 151.49 ns

Impact: Page faults at 0.01% rate increased EAT from 101.5 to 151.5 ns—a 49% increase from 0.001% of accesses!

Summary: TLB Hit Ratio Calculations

Key Takeaways

•EAT = α × Hit_Time + (1-α) × Miss_Time — The fundamental TLB performance equation
•TLB Reach = Entries × Page_Size — Determines how much working set fits without misses
•Access pattern dominates hit ratio — Sequential access can achieve 99%+ even with large working sets
•Multi-level TLBs reduce miss penalty — L2 TLB catches most L1 misses cheaply
•Page faults are extremely costly — Even 0.01% fault rate significantly impacts EAT
•Cache effects help page walks — Page table entries get cached, reducing miss penalty

Essential Formulas:

EAT = (TLB_Hit_Rate × Hit_Time) + (TLB_Miss_Rate × Miss_Time)

TLB Reach = TLB_Entries × Page_Size

Estimated Hit Ratio (random) ≈ min(1.0, TLB_Reach / Working_Set)

Page Walk Time = Page_Table_Levels × Memory_Access_Time

What's Next:

We've analyzed TLB performance. Next, we'll examine disk scheduling seek time calculations, applying similar quantitative analysis to storage I/O.

Page Complete

3 / 5