Eventually the memory will become full and some pages will need to be removed from memory in order to allow other processes to execute. There are a number of replacement strategies.
Identify the page which won't be needed for the longest period of time and pick that one for replacement. THis is the ideal strategy but requires knowledge of the future so cannot be realistically implemented, however it gives us a benchmark against which to measure other strategies.
The first page to be written into memory is the first to be replaced when space is needed. This is done regardless of whether the page is currently active. A very simple replacement policy but runs the risk of removing heavily used pages.
Doesn't write dirty pages back to disk immediately but puts it on the tail of a dirty page list. If a page fault occurs then search the dirty page list first in case the page is there, before fetching a page in from disk. The entire dirty page list is written back to disk at intervals.
Time-stamp the page table entry with the value from a cpu counter when the page is accessed. Search through the page tables for the oldest time stamp and replace that page. Major problems are the time taken to searh the entire set of page table entries and the counter will roll over to zero at some point. On occasion it may swap out a page that is about to be used eg. a loop executing over 9 virtual pages on an 8 page machine. (from O'Gorman).
A compromise on the complexity of LRU. A single bit identifies whether a page has been accessed. The system can then identify which pages have been used. A circular search is performed, wrapping around at the end of the page tables. All the access bits are cleared on the first time round. If the access bits are clear on the second time round the loop then the page has not been accessed recently and can be replaced.
Linux uses a modified version of NRU. kswapd checks once a second to see if the number of free pages is below a critical value. If true then it performs the NRU algorithm.
Any page replacement algorithm should select unmodified (clean) pages for replacement in preference to dirty pages as no write-back to disk is needed.