Adaptive Replacement Algorithms for Use in Paged Memory Computer Systems.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1971
- Accession Number
- AD0725989
Entities
People
- C. C. Carroll
Organizations
- Auburn University