Accession Number : AD0725989

Title :   Adaptive Replacement Algorithms for Use in Paged Memory Computer Systems.

Descriptive Note : Technical rept.,

Corporate Author : AUBURN UNIV ALA

Personal Author(s) : Carroll,C. C.

Report Date : JUL 1971

Pagination or Media Count : 179

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)

Descriptors :   (*DATA STORAGE SYSTEMS, MANAGEMENT PLANNING AND CONTROL), (*COMPUTER PROGRAMMING, INSTRUCTION MANUALS), ALGORITHMS, COMPUTER PROGRAMS, ADAPTIVE SYSTEMS, MULTIPLE OPERATION

Subject Categories : Computer Programming and Software
      Computer Hardware
      Computer Systems Management and Standards

Distribution Statement : APPROVED FOR PUBLIC RELEASE