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.
- Typical multilevel page table: x.y.z → address at table[x][y]+z
- 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
- valid/invalid
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
- If page table changes, TLB entries become out of date.
- 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 → 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