Two-Level Replacement Decisions in Paging Stores
- 1 December 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (12), 1151-1159
- https://doi.org/10.1109/tc.1983.1676176
Abstract
One of the primary motivations for implementing virtual memory is its ability to automatically manage a hierarchy of storage systems with different characteristics. The composite system behaves as if it were a single-level system having the more desirable characteristics of each of its constituent levels. In this paper we extend the virtual memory concept to within the top level of a two-level hierarchy. Here, the top level is thought of as containing two additional levels within it. This hierarchy is not a physical one, but rather an artificial one arising from the employment of two different replacement algorithms. Given two replacement algorithms, one of which has good performance but high implementation cost and the other poor performance but low implementation cost, we propose and analyze schemes that result in an overall algorithm having the performance characteristics of the former and the cost characteristics of the latter. We discuss the suitability of such schemes in the management of storage hierarchies that lack page reference bits.Keywords
This publication has 16 references indexed in Scilit:
- Converting a swap-based system to do paging in an architecture lacking page-referenced bitsPublished by Association for Computing Machinery (ACM) ,1981
- Use Bit Scanning in Replacement DecisionsIEEE Transactions on Computers, 1979
- Some Results on Distribution-Free Analysis of Paging AlgorithmsIEEE Transactions on Computers, 1976
- The VMOS paging algorithmACM SIGOPS Operating Systems Review, 1974
- A Unified Approach to the Evaluation of a Class of Replacement AlgorithmsIEEE Transactions on Computers, 1973
- Virtual MemoryACM Computing Surveys, 1970
- The working set model for program behaviorCommunications of the ACM, 1968
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966
- One-Level Storage SystemIEEE Transactions on Electronic Computers, 1962
- Dynamic storage allocation in the Atlas computer, including an automatic use of a backing storeCommunications of the ACM, 1961