Paging: Faster Translations (TLBs)

Why Address Translation Must Be Fast

Dividing the address space into many small pages means the mapping tables become large and reside in memory. Every load, store, or instruction fetch would then require an additional memory round-trip just to discover the physical location. That extra latency would dominate execution time, rendering paging unusable for real programs.

The TLB: A Dedicated Translation Cache

Modern processors therefore embed a tiny, extremely fast cache of recent translations inside the MMU. When a virtual address arrives, the hardware first probes this TLB. A hit supplies the physical frame immediately. A miss walks the page table, installs the new mapping, and restarts the memory operation. Because the TLB sits on-chip, hits cost only a few cycles.

Spatial Locality Turns Sequential Access into Hits

Programs often stream through arrays or execute loops whose instructions occupy consecutive pages. Once the first reference to a page fills the TLB, nearby addresses on the same page hit without further table walks. Even a cold TLB therefore yields a respectable hit rate simply because data and code are packed together.

Pitfalls

• Forgetting to flush or ASID-tag the TLB on a context switch
• Skipping protection-bit checks inside TLB entries
• Underestimating TLB thrashing when the working set exceeds TLB capacity

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    const int page_size = 16;
    const int start_va = 100;
    const int n = 10;
    const int elem_size = 4;

    int hits = 0;
    int misses = 0;
    int prev_vpn = -1;

    printf("Simulating sequential array accesses with page size %d\n", page_size);
    printf("Array of %d ints starting at VA %d\n\n", n, start_va);

    for (int i = 0; i < n; i++) {
        int va = start_va + i * elem_size;
        int vpn = va / page_size;
        int is_hit = (vpn == prev_vpn);
        if (is_hit) {
            hits++;
        } else {
            misses++;
        }
        printf("a[%d] VA=%d VPN=%d %s\n", i, va, vpn, is_hit ? "HIT" : "MISS");
        prev_vpn = vpn;
    }

    printf("\nHits: %d  Misses: %d  Hit rate: %.0f%%\n", hits, misses, 100.0 * hits / n);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-19-tlb.c -o example && ./example

Expected result

Simulating sequential array accesses with page size 16
Array of 10 ints starting at VA 100

a[0] VA=100 VPN=6 MISS
a[1] VA=104 VPN=6 HIT
a[2] VA=108 VPN=6 HIT
a[3] VA=112 VPN=7 MISS
a[4] VA=116 VPN=7 HIT
a[5] VA=120 VPN=7 HIT
a[6] VA=124 VPN=7 HIT
a[7] VA=128 VPN=8 MISS
a[8] VA=132 VPN=8 HIT
a[9] VA=136 VPN=8 HIT

Hits: 7  Misses: 3  Hit rate: 70%

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

For a 10-element array of 4-byte integers starting at virtual address 100 with 16-byte pages, considering only those accesses, what is the TLB hit rate? Why is it not zero even on the first pass?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.