Brief

Virtual Memory

  • illusion: large, sparse address space
    • ease of programming
  • Q1: What if a process uses a lot of memory (more than what exists in physical memory)
  • Q2: What if many programs use too much memory?
  • Mechanisms
  • Policies

Mechanisms

  • Add persistent storage device (Hard drive, SSD)
  • ![](https://i.imgur.com/P9iVYGP.jpg =260x)
  • Properties
    • Slow
    • Cheaper (per byte)
    • Larger
  • Hardware Support
    • Disk
      • Swap Space (Disk space to hold pages of process’s address spaces that don’t fit in memory)
    • Page Table Support (Per process)
      • Page Table Entry
        • |V|P|prot|------PFN------|
        • V: Valid
        • P: Present (if 1 -> in phys mem, if 0 -> not)
        • When P = 0, can use PFN for swap address
      • New Case
        • Valid, not present: What happens?
        • Fault => OS “Page fault handler”
          • If mem is full: evict a page (page replacement)
        • Have: PFN (going to hold the about to be fetched page)
        • Fetch page (disk I/O)
          • May put process to “sleep” (Blocked on I/O)
        • Update page table, TLB, etc.

Policy

Which Page to Evict

  • Considerations:
    • Recency of access
    • Random choice
    • Frequency
    • Clean / Dirty

Policies

  • Optimal: Kick out furthest page in future reference stream
  • Recency: Least recently used (LRU)
    • Problem w/ LRU:
      • Work to do, even on hits (rearrange this list)
    • Perfect LRU:
      • Hardware record time of every access to each page (store this in each page table entry)
      • Problem: too long to find LRU page
    • Approximate LRU:
      • 1 bit per page in PTE (“use” bit, “reference” bit)
      • When H/W accesses that page, set use bit to 1
      • Eviction: just find a page where (use bit == 0)
      • When scanning for a page to evict, if the use bit == 1, clear the bit, move to next page
  • FIFO
    • Larger cache might miss more (Bélády’s Anomaly)