[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Previous forms of address translation: base and bound registers, segmentation. These are not very flexible.

Today: paging.

1. Basic idea

2. Translation Lookaside Buffer

3. Page table tricks

4. Page table structures

Hierarchical paging
  • Basic multi-level approach with fixed-size directories/tables/etc.
  • Page table can be very big: e.g. 64-bit addresses with 4K pages → 252 page table entries per process.

  • Multi-level directory reduces cost but not enough.
Hashed page tables
  • The answer to all data structure problems: use a hash table.
  • May require following long hash chains if we get a lot of collisions.
  • Variant: clustered page tables which are essentially multi-level page tables where top levels are hashed.

Inverted page tables
  • Idea: store table as (physical frame, logical page) instead of (logical page, physical frame)
  • Selling point: page table bounded by (size of physical memory) / (page size)
  • Cost: can't do address translation without searching the entire table
    • So use a hash table
  • Subtler cost: can't implement shared pages, since each physical frame maps to exactly one logical page


2014-06-17 11:58