A strongly competitive randomized paging algorithm. (English) Zbl 0731.68040

Summary: The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the partitioning algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor of \(H_ k\) of optimum. \((H_ k\) is the k-th harmonic number, which is about ln(k).) No on-line algorithm can perform better by this measure. Our result improves by a factor of two the best previous algorithm.


68W10 Parallel algorithms in computer science
68N25 Theory of operating systems
Full Text: DOI


[1] Belady, L. A. A study of replacement algorithms for virtual storage computers.IBM Systems Journal,5:78–101, 1966.
[2] Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. Competitive paging algorithms.Journal of Algorithms, to appear, 1991. · Zbl 0753.68018
[3] Manasse, M. S., McGeoch, L. A., and Sleator, D. D. Competitive algorithms for on-line problems. InProceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, 1988, pages 322–333. · Zbl 0796.68042
[4] Manasse, M. S., McGeoch, L. A., and Sleator, D. D. Competitive algorithms for server problems.Journal of Algorithms, 11(2):208–230, June 1990. · Zbl 0705.68023
[5] Sleator, D. D., and Tarjan, R. E. Amortized efficiency of list update and paging rules.Communications of the ACM, 28(2):202–208, February 1985.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.