Dashboard/Block 3: Memory Hierarchy/Week 9
Week 9Memory Hierarchy

Virtual Memory

Virtual memory provides each process with its own address space, mapping virtual addresses to physical addresses through page tables. The TLB (Translation Lookaside Buffer) caches recent translations to avoid the cost of page table walks.

Learning Objectives

Explain virtual-to-physical address translation via page tables
Calculate page table size and number of entries
Trace TLB lookups and compute effective memory access time
Understand multi-level page tables and memory protection

Key Concepts

Virtual Memory Concepts

Virtual memory divides addresses into fixed-size pages (virtual) and frames (physical). A page table maps virtual page numbers (VPN) to physical frame numbers (PFN). Benefits: memory protection, process isolation, and the illusion of more memory than physically available.

  • -

    Virtual address = VPN | Page Offset

  • -

    Physical address = PFN | Page Offset (offset is the same, not translated)

  • -

    Page table stored in main memory — one per process

  • -

    Page fault: requested page not in physical memory → OS loads from disk

TLB (Translation Lookaside Buffer)

The TLB is a small, fast cache of recent page table entries. On every memory access, the TLB is checked first:

  • -TLB hit: translation found — use PFN directly (fast, ~1 cycle)
  • -TLB miss: must walk the page table in memory (slow, ~100+ cycles)

Typical TLB: 32-128 entries, fully-associative, access time ~0.5-1 cycle.

  • -

    TLB is typically fully-associative with 32-128 entries

  • -

    TLB hit rate is usually >99% due to locality

  • -

    On context switch, TLB must be flushed (or use ASIDs)

  • -

    TLB miss penalty = page table walk time (may involve multiple memory accesses for multi-level)

Multi-level Page Tables & Protection

Single-level page tables can be very large. Multi-level page tables split the VPN into multiple fields, creating a tree of smaller page tables. Only the needed portions are allocated in memory, saving space for sparse address spaces.

Memory protection bits in each PTE control read/write/execute permissions per page.

  • -

    2-level page table: VPN split into directory index + page table index

  • -

    Saves memory for sparse address spaces (only allocate needed 2nd-level tables)

  • -

    Protection bits: R (read), W (write), X (execute), U (user/kernel)

  • -

    Violation of protection bits triggers a protection fault (trap to OS)

W8: Cache DesignW10: I/O Systems