An evaluation of three globally and locally implemented page replacement algorithms using a demand paged virtual memory simulator

This paper presents a survey of some of the more practical methods of page replacement in a demand-paged virtual memory system, and an evaluation of three of these methods is given that was performed using a reference-driven simulator program. A discussion of several page replacement algorithms is given with particular emphasis on a least recently used (LRU) approximation algorithm, a random (RAND) page replacement scheme and a round robin method, also referred to as first in, first out (FIFO). Each of these page replacement algorithms was evaluated in a global application ("paged against the system") and a local implementation ("paged against the process"). Nine sets of test data were used to gather page reference success statistics on each implementation of each page replacement algorithm. These test data made considerations for such factors as performance characteristics of processor-intensive tasks versus those of peripheral-intensive tasks, the interactions between such types of tasks, and physical memory capacity. Results are presented in tabular and graphical form, and related to findings in earlier literature.