An analysis of the performance of the page fault frequency (PFF) replacement algorithm

摘要

Most of the replacement algorithms devised and implemented largely depend on program behavior, in other words, to optimally select the parameters of these algorithms program behavior or at least a probability model of it should be known. The page fault frequency (PFF) algorithm adapts to dynamic changes in program behavior during execution. Therefore its performance is expected to be less dependent on prior knowledge of the program behavior during execution. Therefore its performance is expected to be less dependent on prior knowledge of the program behavior and input data.

The PFF algorithm uses the measured page fault frequency (by actually monitoring the inter-page fault interval) as the basic parameter for memory allocation decision process.

In order to analyze the performance of the PFF algorithm, a mathematical model was developed. The resultant random process is the memory space allocation for a program as a function of the processor time (virtual time). This random processcan be analyzed using the method of imbedded Markov chains. The parameter obtained from this analysis are the distributions of the memory allocation during processing interval and during page waiting intervals, the average page fault rate and the expected space time product accumulated by the program.

The input parameters for the model were obtained from address traces of two programs. The results of the model were validated by simulation.