Page replacement algorithms
Not Frequently Used
As its name suggests, this examines the frequency of use of particular
pages. Each PTE contains a frequency counter. In principle this would be
incremented on every memory access, but as we have seen this is not efficient.
An adequate alternative is for a background OS process to sweep round all
processes in memory periodically, add the accessed bit to the frequency
counter, and clear the accessed bit. This way the page replacement algorithm
'samples' the memory usage of the processes in the system every clock tick,
rather than every instruction.
Trouble is that it never forgets---the counter never decreases, so that
pages which were used heavily, but are now entirely unused, retain their
high frequency count.
A better solution is NFU with aging: Each time the background
process examines a page, it shifts its counter right by one (divide counter
value by 2), then adds the accessed bit to the most significant
bit in the counter. As before, the pages with the lowest counter
values are the ones scheduled for eviction. Pages which have not been used
for many clock ticks eventually have their counter reduced to 0, and all
become equally likely to be evicted.
last updated 6 March 1998