YouTube placeholder

Page Translation

Let’s Regroup

Ideally, what would we like?

  • Fast mapping from any virtual byte to any physical byte.

  • Operating system cannot do this. Can hardware help?

Translation Lookaside Buffer

  • Common systems trick: when something is too slow, throw a cache at it.

TLB Example

tlb 1
tlb 2
tlb 3
tlb 4

What’s the Catch?

  • CAMs are limited in size. We cannot make them arbitrarily large.

So at this point:

  • Segments are too large and lead to internal fragmentation.

  • Mapping individual bytes would mean that the TLB would not be able to cache many entries and performance would suffer.

  • Is there a middle ground?

Pages

Modern solution is to choose a translation granularity that is small enough to limit internal fragmentation but large enough to allow the TLB to cache entries covering a significant amount of memory.

  • Also limits the size of kernel data structures associated with memory management.

Execution locality also helps here: processes memory accesses are typically highly spatially clustered, meaning that even a small cache can be very effective.

Page Size

  • 4K is a very common page size. 8K or larger pages are also sometimes used.

  • 4K pages and a 128-entry TLB allow caching translations for 512 KB of memory.

  • You can think of pages as fixed size segments, so the bound is the same for each.

Page Translation

  • We refer to the portion of the virtual address that identifies the page as the virtual page number (VPN) and the remainder as the offset.

  • Virtual pages map to physical pages.

  • All addresses inside a single virtual page map to the same physical page.

  1. Check: for 4K pages, split 32-bit address into virtual page number (top 20 bits) and offset (bottom 12 bits). Check if a virtual page to physical page translation exists for this page.

  2. Translate: Physical Address = Physical Page + offset.

TLB Example

Assume we are using 4K pages.

pagetranslation 1
pagetranslation 2
pagetranslation 3
pagetranslation 4
pagetranslation 5
pagetranslation 6
pagetranslation 7
pagetranslation 8
pagetranslation 9
pagetranslation 10
pagetranslation 11
pagetranslation 12
pagetranslation 13

TLB Management

Where do entries in the TLB come from?

  • The operating system loads them.

What happens if a process tries to access an address that is not in the TLB?

  • The TLB asks the operating system for help via a TLB exception. The operating system must either load the mapping or figure out what to do with the process. (Maybe boom.)

Paging: Pros

  • Maintains many of the pros of segmentation, which can be layered on top of paging.

  • Pro: can organize and protect regions of memory appropriately.

  • Pro: better fit for address spaces. Even less internal fragmentation than segmentation due to smaller allocation size.

  • Pro: no external fragmentation due to fixed allocation size!

Paging: Cons

  • Con: requires per-page hardware translation. Use hardware to help us.

  • Con: requires per-page operating system state. A lot of clever engineering here.

Created 3/11/2017
Updated 9/18/2020
Commit 4eceaab // History // View
Built 3/12/2017 @ 20:00 EDT