Page Replacement Algorithms

Figure 4.13: Page Replacement.

• Prevent over-allocation of memory by modifying page-fault service routine to include page replacement
• Use dirty (modify) bit to reduce overhead of page transfers; only modified pages written back to disk
• Page replacement completes separation between logical memory and physical memory; large virtual memory can be provided on smaller physical memory
• Find location of desired page on disk
• Find free frame:
  • if free frame, use it.
  • if no free frame, page replacement algorithm selects victim frame
  • If victim dirty write back to disk
• Read desired page into (newly) free frame; update page and frame tables
• Restart faulting process
• Want lowest page-fault rate
• Evaluate algorithm by running on given string of memory references (reference string) and compute number of page faults
• The Optimal Page Replacement Algorithm; the page that will not be referenced again for the longest time is replaced ( prediction of the future; purely theoretical, but useful for comparison.)
• The Not Recently Used Page Replacement Algorithm; algorithm removes a page at random
• The First-In, First-Out (FIFO) Page Replacement Algorithm; FIFO the frames are treated as a circular list; the oldest (longest resident) page is replaced
• The Second Chance Page Replacement Algorithm; look for an old page that has not been referenced in the previous clock interval, avoids the problem of throwing out of heavily used page
• The Least Recently Used (LRU) Page Replacement Algorithm; LRU the frame whose contents have not been used for the longest time is replaced
• Summary of Page Replacement Algorithms
  

  Table 4.1: Page replacement algorithms

  Algorithm	Comment
  Optimal	Not implementable, but useful as a benchmark
  NRU	Very crude
  FIFO	Might throw out important pages
  Second Chance	Big improvement over FIFO
  Clock	Realistic
  LRU	Excellent, but difficult to implement exactly
  NFU	Fairly crude approximation to LRU
  Aging	Efficient algorithm that approximates LRU well
  Working set	Somewhat expensive to implement
  WSClock	Good efficient algorithm