"An Experimental Evaluation of Page Replacement Policies in
a Multi-Programming Environment", (Joint work With Raj Yavatkar),
submitted for publication.
Abstract: Our research is motivated by the increasing availability of
larger memories and the surprisingly high paging rates encountered on
such machines. This paper compares the effectiveness of the
one-handed and two-handed Global Clock policies, an LRU algorithm, and
a frequency-based replacement policy by running synthetic benchmark
applications designed to compare and contrast their behaviors. We
show that Global Clock poorly approximates LRU in common
configurations, mistakenly targeting in-use pages of a process's
working set. We then show that a better approximation of LRU can be
implemented efficiently, but that LRU implementations are inherently
unstable on today's larger memory machines. Running the same
application repeatedly can result in widely differing page fault
behavior, dependent on random startup conditions. Finally, we present
preliminary results showing that a frequency-based replacement policy
can outperform both Global Clock and LRU in cases where some pages are
referenced only once, while others are referenced repeatedly over long
periods of time.