Random Partially Pre-Loaded Page Replacement Algorithms.
Abstract
The replacement problem arises in computer system management whenever the executable memory space available is insufficient to contain all data and code which may be accessed during the execution of an ensemble of programs. An example of this is the page replacement problem in virtual memory computers. The problem is solved by using a replacement algorithm which selects code or data items which are to be removed from executable memory whenever new items must be brought in an no more free storage space remains. An automaton theoretic model of replacement algorithms is introduced for the class of 'random, partially pre-loaded' replacement algorithms, which contains certain algorithms of practical and theoretical interest. An analysis of this class is provided in order to evaluate their performance, using the assumption that the references to the items to be stored are identically distributed independent random variables. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 30, 1972
- Accession Number
- AD0755491
Entities
People
- Sami E. Gelenbe
Organizations
- University of Michigan