CS 134

Key Points: Paging and Address Translation

From Segments to Pages

  1. Evolution from Segmentation:
    • Segment prefixes in machine instructions are a hassle
      • If we have segments, they should be part of the logical address
    • Move from variable-size segments to fixed-size pages
    • Pages are typically 4 KB (some systems use other sizes, e.g., 16 KB)
    • Eliminates external fragmentation issues
  2. Key Terminology:
    • Pages: Fixed-size chunks of logical memory
    • Frames: Fixed-size chunks of physical memory
    • Page Tables: Map logical pages to physical frames
    • Page Table Entry (PTE): Single mapping in the page table

Address Translation

  1. Basic Translation Process:
    • Logical address divided into page number and offset
    • Page table maps page number to frame number
    • Offset remains unchanged in translation
  2. Translation Lookaside Buffer (TLB):
    • Cache for recent address translations
    • Speeds up translation by avoiding page table lookups
    • Most memory accesses hit in TLB
  3. Multi-Level Page Tables:
    • Reduces memory overhead for sparse address spaces
    • Common implementations:
      • 32-bit: Two-level page tables (10+10+12 bits)
      • 64-bit: Four-level page tables (9+9+9+9+12 bits)
    • Each level indexes into table for next level
  4. Hashed Page Tables:
    • Used in PowerPC architecture
    • Combines segmentation and paging
    • Global hash table maps page numbers to frames
  5. TLB-Only Translation:
    • Used in MIPS architecture (including OS/161)
    • No page tables, just TLB
    • OS handles TLB misses

Virtual Memory and Caching

  1. Virtual Memory:
    • Some memory of a process doesn't need to be in RAM
      • e.g., allocated but not yet used memory
  2. Virtual Address:
    • Another name for logical address in a world where we have virtual memory
  3. Page Faults:
    • Occur when the CPU can't find a page in the page table
    • OS can “materialize” the page it is supposed exist
  4. Memory Caching Strategies:
    • VIPT (Virtually Indexed, Physically Tagged)
    • PIPT (Physically Indexed, Physically Tagged)
    • VIVT (Virtually Indexed, Virtually Tagged)
    • Trade-offs between speed and correctness

Remember

  • Paging eliminates external fragmentation by using fixed-size memory chunks
  • Each process has its own page table for its logical address space
  • TLBs are crucial for making address translation efficient
  • Multi-level page tables help manage sparse address spaces
  • Different architectures use different approaches to address translation
  • Modern systems must balance between translation efficiency and cache performance

(When logged in, completion status appears here.)