Paging & Address Translation (TLB)

Why translate addresses?

Every program believes it owns a large, continuous block of memory starting at address 0. Its virtual (logical) addresses don’t directly name bytes in RAM. The operating system and the CPU’s memory management unit (MMU) translate each one to a physical address. This lets many programs share RAM safely, lets a program be bigger than RAM, and removes the external fragmentation of contiguous allocation.

Pages, frames and the page table

Virtual memory is cut into fixed-size pages, and RAM into frames of the same size. A page can live in any free frame. The page table stores, for every page, which frame holds it, or that the page is not in RAM at the moment.

A virtual address splits into two parts:

virtual address  = | page number | offset |
physical address = | frame number | offset |     (offset copied unchanged)

With 256-byte pages the offset is the low 8 bits. Address 1030 = 4 × 256 + 6 → page 4, offset 6. If page 4 is in frame 0, the physical address is 0 × 256 + 6 = 6.

The TLB: a cache for translations

The page table lives in main memory, so a naive translation costs an extra memory access for every access a program makes, doubling memory time. The Translation Lookaside Buffer (TLB) is a tiny, very fast cache inside the CPU that remembers recent page → frame translations:

1. TLB hit: the frame comes straight from the TLB.
2. TLB miss: read the page table in memory, then store the translation in the TLB, evicting an old entry (often the least recently used).
3. Page fault: the page-table entry says the page is not in RAM. The OS loads it from disk, which takes milliseconds. Which page to throw out when RAM is full is the subject of page replacement.

Worked example

Page size 256 bytes, a 4-entry TLB that starts empty, and the page table from the 3D model (page 7 is not in RAM). Addresses: 1030, 520, 1100, 300, 2000, 1050, 600, 760.

4 hits out of 8 gives a hit ratio of 50 %.

Effective access time (EAT)

With TLB time t, memory time m and hit ratio h:

EAT = h · (t + m) + (1 − h) · (t + 2m)

The classic exam numbers are t = 20 ns, m = 100 ns, h = 80 %: EAT = 0.8 × 120 + 0.2 × 220 = 140 ns. Without a TLB every access would take 2m = 200 ns. Real programs reach hit ratios above 99 % thanks to locality: loops and nearby data keep reusing the same few pages.

Code

PAGE = 256
page_table = [5, 2, 7, None, 0, None, 3, None]     # page -> frame (None = on disk)
tlb, TLB_SIZE = [], 4                               # (page, frame), most recent last

def translate(addr):
    page, offset = divmod(addr, PAGE)
    for entry in tlb:
        if entry[0] == page:                        # TLB hit
            tlb.remove(entry)
            tlb.append(entry)
            return entry[1] * PAGE + offset, "hit"
    if page_table[page] is None:                    # page fault: load from disk
        used = {f for f in page_table if f is not None}
        page_table[page] = min(set(range(8)) - used)
    frame = page_table[page]
    if len(tlb) == TLB_SIZE:
        tlb.pop(0)                                  # evict least recently used
    tlb.append((page, frame))
    return frame * PAGE + offset, "miss"

for a in [1030, 520, 1100, 300, 2000, 1050, 600, 760]:
    print(a, translate(a))
# 1030 (6, 'miss')   520 (1800, 'miss')   1100 (76, 'hit')   300 (556, 'miss') ...

Bigger page tables

With 4 KB pages and 48-bit addresses, a flat page table would need 2³⁶ entries per process. Real systems use multi-level page tables (x86-64 uses 4 or 5 levels), so only the parts that are actually used take memory. A TLB miss then costs several memory reads, which makes the TLB even more important.

Common mistakes

• Translating the offset. Only the page number changes; the offset is copied unchanged.
• Forgetting the extra memory access for the page table on a TLB miss. That is the 2m in the formula.
• Mixing up a TLB miss (cheap, fixed by reading the page table) with a page fault (expensive, needs the disk).
• Calculating the page number with the wrong page size. Page size 2ⁿ means the low n bits are the offset.