Virtual Memory

Provides a virtual address space that maps to physical memory

How It Works

• Steps
  1. The process is provided (by the OS) with a virtual address space broken into pages or segments (on 64 bit systems, only pages)
  2. A running process generates virtual addresses
  3. The OS translates virtual address into physical addresses, swapping pages or segments as needed
• In modern systems, the CPU uses a memory management unit (MMU) to convert virtual addresses to physical ones quickly

Implementation

Segmentation

• Main goal: To allow programs and data to be broken up into logically independent address spaces to aid sharing and protection
• Breaks up processes into individual segments which the OS swaps in and out
  • Looks at memory space per segment of a process (data, text, heap)
  • Could combine multiple of those into one segment
  • The process defines its own segments (so the programmer needs to be aware of this)
• Allows processes to share segments easily (like how threads work)
• Only used on 32bit systems

Paging

• Main goal: To get a large linear address space without needing more physical memory
• Breaks memory space into evenly sized chunks (pages) which are loaded into and out of physical memory
• Page size is determined by the hardware (typically 4KiB)
• Form of fixed size partitioning
  • Page sizes are the unit of allocation to processes
  • Generates internal fragmentation, but no external fragmentation
• Paging System
  • Pages can be in main memory, in cache, or on disk
  • Page Table
    • Used to map virtual addresses to physical addresses
    • Stores
      • Cache?
      • Referenced?
      • Modified?
      • Protection (RW)?
      • Present? (in physical memory)
      • Page frame number (physical page)
  • MMU Operations
    • Memory addresses are broken down into a page (the most significant n bits) and an offset (the rest of the bits)
    • The page is converted and the offset is appended to that
• Translation Lookaside Buffer
  • Quick access is essential, so common entries are stored in a specialized cache
  • Grows as needed, but can still get large
  • Keeping it small
    • Page table per process
    • Multilevel page tables
• Memory accessed when on disk → Page fault
  • It restarts the instruction and tries again (as it moves to main memory or cache)
  • In modern systems, it looks ahead to try to move memory out of disk ahead of time
• Page Replacement
  • Decides what pages to keep quicker access to
  • Stores a reference string that tracks what pages were accessed
    • Removes consecutive accesses
  • Algorithms
    • Fist in, first out
      • The oldest page is evicted first
      • Belady’s Anomaly: There are situations where the fault rate increases when the memory amount increases
    • Least Recently Used
      • Evicts the most ‘stale’ page
      • Adding new memory will never increase the fault rate
      • Inefficient because it requires in-place list of modifications
    • Not Frequently Used
      • Tracks the number of times that pages are used, evicting the least used page
      • Good locally but it remembers everything so it suffers when task types change
    • Aging
      • Approximates LRU
      • Uses the referenced and modified tags (to avoid the in-place list)
        • Reference bit
          • Set on load or access
          • Cleared on a clock tick (only times when the current process is running)
        • Modified bit
          • Set on write
          • Cleared when the page is copied back to disk (swapped)
      • The referenced and modified bits represent numbers zero to four in binary
      • On page fault, evict the lowest (numerically)
    • Clock (Second Chance)
      • Proceeds using a round robin approach
      • Upon a page fault, if the reference bit of the current target is
        • 0 → that page is replaced and the target moves
        • 1 → the target’s reference bit is cleared, the target moves, and the process repeats
      • Very resilient when tasks change behaviors
    • Working Set
      • Uses a time window to define a working set of pages that are most active
      • On a fault, remove the first page that is outside of the working set time range. If none, just remove the oldest.
      • Prevents having to go over every page during a page fault
• Handling page faults
  1. Save remaining context. Identify needed page
  2. If the page number is not legitimate or the process is not able to access it→ terminate the process
  3. Select victim page (what to replace)
  4. If the victim page has been modified, save the victim
  5. Load the new page
• Can share pages to save memory when loading dynamic libraries
  • Requires explicit OS and compiler support