Faster address translation

Translation costs memory reads

The page table says which frame holds each page, and it lives in RAM. So with no help, every access needs two reads: the page table entry, then the data. Memory work becomes about twice as slow.

The TLB

The CPU keeps a TLB (translation lookaside buffer): a small, fast store of recent page-to-frame translations. If the translation is there, that is a hit, and the page table is skipped. If not, it is a miss: the page table is read, and the translation is saved in the TLB for next time. A TLB miss is not a page fault: the page is still in RAM.

Locality

Programs touch addresses next to recent ones (spatial locality), and they come back to the same addresses soon (temporal locality). With 4 KB pages and 4-byte numbers, one page holds 1,024 numbers. A loop reading them in order misses once, then hits 1,023 times.

Multi-level page tables

A plain page table has one entry per page, used or not. A 4 GB address space with 4 KB pages has about a million pages, and at 4 bytes each that is 4 MB per process. A multi-level page table cuts the table into page-sized chunks, with a small directory that lists which chunks exist. Unused stretches get no chunk, but a TLB miss now reads more than one table.

Huge pages

A TLB holds few translations, say 64. With 4 KB pages that covers 256 KB, so a program using gigabytes misses a lot. A huge page, for example 2 MB, lets the same 64 entries cover 128 MB. The cost: a partly used huge page still takes all 2 MB.

Remember

• Without a TLB, each access also reads the page table.
• TLB hit skips the table; a miss reads it and saves the result.
• Locality is why most lookups hit.
• Levels save table memory but cost more reads on a miss.
• Huge pages cover more per entry but can waste space.