An analysis of WS and PFF algorithms
Tóm tắt
In order to analyzeWS andPFF algorithms, mathematical models have been developed. The results obtained from the analysis in this paper areT
min andT
max of the parameterT for the two algorithms respectively. The input parameters for the models were obtained from the address traces fof three programs. The results of the models were validated by simulation.
WS algorithm has better performance. It adapts to dynamic changes in program behavior during execution. Therefore its performance is expected to be less dependent on prior knowledge of program behavior. The parameterT can vary in a wider range. Therefore the value ofT can be easily selected to make the algorithm work well.
Tài liệu tham khảo
P.J. Denning and K.C. kahn, A study of program locality and lifetime function, Proc. ACM Symposium on Op. Sys. Prin., Austin, Texas, 1975.
W.W. Chu and H. Opderbeck, Analysis of the PFF replacement algorithm via a Semi-Markov model,CACM,19: 5 (1976).
R. Turnor and B. Strecker, Use of the LRU stack depth distribution for simulation of paging behavior,CACM,20: 11 (1977).
J.R. Spirn and P.J. Denning, Experiments with program locality, Fall Joint Computer Conference, 1972.
R.E. Barlow and F. Proschan, Mathematical Theory of Reliability, Wiley, New York, 1965.