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