Adaptive Replacement Algorithms for Use in Paged Memory Computer Systems.

Virtual memory computers are studied with particular emphasis on paged memory systems. Existing replacement algorithms are analyzed and a need for new and improved algorithms is demonstrated. Three new replacement algorithms which utilize adaptive techniques are designed. A probability model that produces typical memory traces is developed and a FORTRAN 4 computer program that implements this model is provided. Using the memory traces generated by the probability model, a simulation study of the new adaptive algorithms and the extant algorithms is described. The results of this study indicate that one of the new algorithms is significantly better than any of the existing ones. A GPSS queuing model simulation of a complete multiprogrammed paged memory computer system is given. A discussion of the manner in which improved algorithms affect system performance is provided. Possible physical implementations of the best new algorithm are studied and a design, constructible with present state-of-the-art digital hardware, is derived. Author