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.

Page State

In order to keep the TLB up-to-date we need to be able to:

  • Store information about each virtual page.

  • Locate that information quickly.

Page Table Entries (PTEs)

We refer to a single entry storing information about a single virtual page used by a single process a page table entry (PTE).

  • (We will see in a few slides why we call them page table entries.)

  • Can usually jam everything into one 32-bit machine word:

    • Location: 20 bits. (Physical Page Number or location on disk.)

    • Permissions: 3 bits. (Read, Write, Execute.)

    • Valid: 1 bits. Is the page located in memory?

    • Referenced: 1 bits. Has the page been read/written to recently?

Locating Page State

  • Process: "Machine! Store to address 0x10000!"

  • MMU: "Where the heck is virtual address 0x10000 supposed to map to? Kernel…​help!"

  • (Exception.)

  • Kernel: Let’s see…​ where did I put that page table entry for 0x10000…​ just give me a minute…​ I know it’s around here somewhere…​ I really should be more organized!

Created 2/17/2017
Updated 9/18/2020
Commit 4eceaab // History // View
Built 3/8/2016 @ 19:00 EDT