A Comparison of Page Replacement Algorithms

Abstract

One of the objectives of virtual memory systems is to provide more virtual memory than actually exists as real memory. Thus only a subset of the addressable pages are kept in the real memory of the system. The page replacement algorithm selects this subset through the decisions that it makes to remove pages from real memory. This algorithm is key to the performance of any paging system. This paper briefly reviews the history and structure of virtual memory systems. Several simple replacement algorithms are discussed. The primary focus is on the page replacement algorithms used in five production operating systems which are all approximations to the Least Recently Used (LRU) algorithm. Systems that do block paging use Local LRU and the others use Global LRU. Some systems allow installation control for classes of work and some use scheduler information to predict future reference. The particular systems described are MVS, VM/SP, VM/ESA, BSD Unix, and VAX segmented FIFO.