Paging, TLBs and Page Tables

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size. Any page can go into any free frame, so a process no longer needs one contiguous block, and external fragmentation disappears.

Address translation

With page size 2ᵈ bytes, a logical address splits into a page number (high bits) and an offset (the low d bits). The page table maps each page number to a frame number; the offset stays the same.

PAGE_SIZE = 4096
page_table = {0: 5, 1: 9, 2: 2, 3: 7}          # page -> frame

for logical in [100, 4100, 13000]:
    page, offset = divmod(logical, PAGE_SIZE)
    frame = page_table[page]
    physical = frame * PAGE_SIZE + offset
    print(f"logical {logical:5} = page {page}, offset {offset:4} -> frame {frame} -> physical {physical}")

logical   100 = page 0, offset  100 -> frame 5 -> physical 20580
logical  4100 = page 1, offset    4 -> frame 9 -> physical 36868
logical 13000 = page 3, offset  712 -> frame 7 -> physical 29384

Page table size

A 32-bit logical address with 4 KB (2¹²) pages has 2³² / 2¹² = 2²⁰ pages. If each page-table entry is 4 bytes, one process's page table needs 2²⁰ × 4 bytes = 4 MB. That is too big to keep for every process, which leads to multilevel and inverted page tables.

The TLB

Each memory access now needs two memory accesses: one for the page table and one for the data. A translation lookaside buffer (TLB) is a small, fast cache of recent page → frame translations.

Effective memory access time (EMAT) with TLB access time t, memory access time m and hit ratio h:

EMAT = h × (t + m) + (1 − h) × (t + 2m)

Example: t = 20 ns, m = 100 ns, h = 0.8: EMAT = 0.8 × 120 + 0.2 × 220 = 96 + 44 = 140 ns.

def emat(tlb, mem, hit, levels=1):
    """Effective access time for a TLB plus a page table with the given number of levels."""
    return hit * (tlb + mem) + (1 - hit) * (tlb + (levels + 1) * mem)

print("1-level, 80% hits:", round(emat(20, 100, 0.80), 2), "ns")
print("1-level, 98% hits:", round(emat(20, 100, 0.98), 2), "ns")
print("2-level, 98% hits:", round(emat(20, 100, 0.98, levels=2), 2), "ns")

1-level, 80% hits: 140.0 ns
1-level, 98% hits: 122.0 ns
2-level, 98% hits: 124.0 ns

Multilevel paging

Instead of one huge table, page the page table. With 32-bit addresses, 4 KB pages and 4-byte entries, one page holds 4096 / 4 = 1024 = 2¹⁰ entries, so the 20-bit page number splits into a 10-bit outer index and a 10-bit inner index:

Only the inner page tables that are actually used need to exist, which saves a lot of memory for sparse address spaces. The cost: a TLB miss now needs one memory access per level, plus one for the data.

Inverted page tables keep one entry per physical frame (not per page), so their size depends only on the RAM size; looking up a page then needs a search, usually through a hash table.

GATE-style practice questions