Analysis of the PFF Replacement Algorithm via a Semi-Markov Model An analytical model is presented to estimate the performance of the Page Fault Frequency (PFF) replacement algorithm. In this model, program behavior is represented by the LRU stack distance model and the PFF replacement algorithm is represented by a semi-Markov model. Using these models, such parameters as the inter-page-fault interval distribution, the probability of the number of distinct pages being referenced during an inter-page-fault interval, etc. are able to be analytically determined. Using these models to evaluate these parameter values permits study of the performance of the replacement algorithm by simulating the page fault events rather than every page reference event. This significantly reduces the required computation time in estimating the performance of the PFF algorithm. CACM May, 1976 Chu, W. W. Opderbeck, H. PFF replacement algorithm, semi-Markov model, simulation of replacement algorithm 4.31 4.32 CA760509 JB January 4, 1978 2:59 PM 1892 4 2862 1924 4 2862 2095 4 2862 2218 4 2862 2297 4 2862 2374 4 2862 2526 4 2862 2667 4 2862 2668 4 2862 2862 4 2862 2863 4 2862 1728 5 2862 2862 5 2862 2862 5 2862 2862 5 2862