Publication
Journal of the ACM
Paper

Some Distribution-Free Aspects of Paging Algorithm Performance

Download paper

Abstract

The topic of this paper is a probabilistic analysis of demand paging algorithms for storage hierarchies. Two aspects of algorithm performance are studied under the assumption that the sequence of page requests is statistically independent: the page fault probability for a fixed memory size and the variation of performance with memory. Performance bounds are obtained which are independent of the page request probabilities. It is shown that simple algorithms exist which yield fault probabilities close to optimal with only a modest increase in memory. © 1974, ACM. All rights reserved.

Date

01 Jan 1974

Publication

Journal of the ACM

Authors

Topics

Resources

Share