Liam's UF Notes

Search

SearchSearch

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

Graph View

Backlinks