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

Today: paging.

1. Basic idea

• Map logical addresses to physical addresses through a page table.

  • Typical multilevel page table: x.y.z → address at table[x][y]+z

    • x is offset into page directory (IA-32 terminology)

    • y is offset into page table pointed to by page directory (IA-32 terminology)

  • Page table pointed to by page table base register in MMU (CR3 on x86).

  • Actual contents stored in physical memory.
• On Intel machines, done after segmentation.
• Page table entries
  • Physical address
  • Flag bits
    • valid/invalid

      • Attempts to access an invalid page cause a page fault which is handled by the kernel

        • (more on what we can do with this soon)
    • Protection mode: readable, writable, executable
    • Protection mode: kernel vs user mode

    • Address of physical memory frame holding the page

    • Status bits: dirty, accessed

      • Used to manage VirtualMemory caching

2. Translation Lookaside Buffer

• Problem: table[x][y][z] requires three 50ns memory accesses!

• Solution: cache frequently-used page table entries in a translation lookaside buffer

• This is a special case of caching

• Associative memory of (key, value) pairs
• Page numbers are checked against all keys simultaneously

• TLB hit: use associated value! We just saved ~100ns.

• TLB miss: go to the page table.

  • Fetched entry goes in TLB
  • Somebody gets replaced! Random or LRU.
• Invalidating the TLB
  • If page table changes, TLB entries become out of date.
    • Any change to PTBR invalidates TLB

    • Kernel may invalidate specific entries (e.g. INVLPG instruction on x86)

    • Kernel may invalidate all entries
      • Note TLB is generally not very big, so cost is not necessarily that high
    • Invalidating TLB adds to effective cost of a context switch
• Address-space identifiers
  • Store ASID with each TLB entry
  • TLB hits must match page number and ASID
  • Now context switch doesn't require flushing entire TLB at once

3. Page table tricks

• Pages can be shared between processes
• Kernel space can be mapped to the same addresses in all page tables (with protection bit set)
  • Switching to kernel mode or between kernel threads doesn't flush TLB
• Invalid bits can be used to get full software control over memory accesses.

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 → 2⁵² 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

CategoryOperatingSystemsNotes