A Unified Approach to the Evaluation of a Class of Replacement Algorithms

The replacement problem arises in computer system management whenever the executable memory space available is insufficient to contain all data and code that may be accessed during the execution of an ensemble of programs. An example of this is the page replacement problem in virtual memory computers. The problem is solved by using a replacement algorithm that selects code or data items that are to be removed from executable memory whenever new items must be brought in and no more free storage space remains. An automaton theoretic model of replacement algorithms is introduced for the class of ``random partially preloaded´´ replacement algorithms, which contain certain algorithms of practical and theoretical interest. An analysis of this class is provided in order to evaluate their performance, using the assumption that the references to the items to be stored are identically distributed independent random variables. With this model, it is shown that the well-known page replacement algorithms FIFO and RAND yield the same long-run page-fault rates.