CS 134

Key Points: Demand Paging and Page Replacement

Demand Paging

  1. Basic Concept:
    • Only load pages when they are actually needed
    • Pages marked “not present” until accessed
    • Page fault triggers loading of needed page
  2. Efficiency:
    • Programs often use small portion of their code
    • Example: Neovim uses only 7.7% of its code pages
    • Loading on demand usually faster than loading everything
  3. Implementation Challenges:
    • Must handle architectural corner cases
    • CPU instructions can interact with page faults
      • Example: Pre-decrement addressing modes

Page Replacement

  1. Key Strategies:
    • First-In, First-Out (FIFO)
    • Least Recently Used (LRU)
    • Least Frequently Used (LFU)
    • Random
    • Optimal (theoretical best case)
  2. Performance Characteristics:
    • LRU often approaches optimal performance
    • LFU can perform poorly due to historical bias
    • Random can work surprisingly well
    • Performance depends heavily on access patterns
  3. Thrashing:
    • Occurs when too few frames are available
    • System spends more time swapping than executing
    • Critical threshold depends on program behavior

Memory Management Considerations

  1. Pre-Paging:
    • Can load likely-needed pages in advance (based on previous program behavior)
    • Trade-off between complexity and benefit
  2. Page Release:
    • Programs can hint about unneeded pages
    • posix_madvise system call options:
      • POSIX_MADV_DONTNEED
      • POSIX_MADV_WILLNEED
  3. Access Patterns:
    • Some patterns can be pathological for certain strategies
    • Sequential access can make LRU perform poorly
    • Real programs often have phase changes in access patterns

Remember

  • Demand paging loads pages only when needed, improving startup time
  • Page replacement strategy significantly impacts system performance
  • LRU provides good real-world performance
  • Too few frames leads to thrashing
  • Access patterns matter more than replacement strategy
  • No single strategy is best for all situations

(When logged in, completion status appears here.)