Virtual Memory

Page Replacement Algorithms

The page replacement algorithm determines which page currently in memory should be replaced when the frames in main memory are full.

  • Page removed should be the page least likely to be referenced in the near future
  • Most policies predict the future behavior on the basis of past behavior

Optimal policy

  • Selects for replacement that page for which the time to the next reference is the longest
  • Impossible to have perfect knowledge of future events

LRU Policy (see page)

FIFO policy

  • Page that has been in memory the longest is replaced
  • Bases on the assumption that an ‘old’ page will not be referenced soon again.
  • Treats page frames allocated to a process as a circular buffer
  • Pages are removed in round-robin style
  • Simplest replacement policy to implement

Clock Policy