article

Free access

MIN—an optimal variable-space page replacement algorithm

Authors:

Barton G. Prieve,

R. S. FabryAuthors Info & Claims

Communications of the ACM, Volume 19, Issue 5

Pages 295 - 297

https://doi.org/10.1145/360051.360231

Published: 01 May 1976 Publication History

PDF eReader

Abstract

A criterion for comparing variable space page replacement algorithms is presented. An optimum page replacement algorithm, called VMIN, is described and shown to be optimum with respect to this criterion. The results of simulating VMIN, Denning's working set, and the page partitioning replacement algorithms on five virtual memory programs are presented to demonstrate the improvement possible over the known realizable variable space algorithms.

References

[1]

Belady, L.A. A study of replacement algorithms for a virtualstorage computer. IBM Systems J. 5, 2 (1966), 78-101.

Digital Library

Google Scholar

[2]

Coffman, E.G., and Varian, L.C. Further experimental data on the behavior of programs in a paging environment. Comm. ACM 11, 7 (July 1968), 471-474.

Digital Library

Google Scholar

[3]

Brawn, B.S., and Gustavson, F.G. Program behavior in a paging environment. AFIPS Conf. Proc., Vol. 33, 1968 FJCC, AFIPS Press, Montvale, N.J., 1968, pp. 1019-1032.

Digital Library

Google Scholar

[4]

Thorington, J.M., and Irwin, J.O. An adaptive replacement algorithm for paged-memory computer systems. IEEE Trans. Comp. C-21, 10 (Oct. 1972), 1053-1061.

Digital Library

Google Scholar

[5]

Denning, P.J. The working set model for program behavior. Comm. ACM 11, 5 (May 1968), 323-333.

Digital Library

Google Scholar

[6]

Prieve, B.G. A page partition replacement algorithm. Ph.D. Th., U. of California, Berkeley, Dec. 1973.

Google Scholar

[7]

Prieve, B.G., and Fabry, R.S. Evaluation of a page partition replacement algorithm. Comm. ACM (to appear).

Digital Library

Google Scholar

[8]

Belady, L.A., and Kuehner, C.J. Dynamic space-sharing in computer systems. Comm. ACM 12, 5 (May 1969), 282-288.

Digital Library

Google Scholar

[9]

Chu, W.W., and Opderbeck, H. The page fault frequency replacement algorithm. AFIPS Conf. Proc., Vol. 41, 1972 FJCC, AFIPS Press, Montvale, N.J., 1972, pp. 597-609.

Digital Library

Google Scholar

Cited By

View all

COŞAR BSAY BDÖKEROĞLU T(2023)A New Greedy Algorithm for the Curriculum-based Course Timetabling ProblemMüfredat Tabanlı Ders Çizelgeleme Problemi için Yeni Bir Açgözlü AlgoritmaDüzce Üniversitesi Bilim ve Teknoloji Dergisi10.29130/dubited.1113519Online publication date: 30-Apr-2023
https://doi.org/10.29130/dubited.1113519
(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Thomasian A(2022)IntroductionStorage Systems10.1016/B978-0-32-390796-5.00010-3(1-87)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00010-3
Show More Cited By

Recommendations

The EELRU adaptive replacement algorithm

The wide performance gap between processors and disks ensures that effective page replacement remains an important consideration in modern systems. This paper presents early eviction LRU (EELRU), an adaptive replacement algorithm. EELRU uses aggregate ...
Working Set Analytics
Invited Tutorial and Regular Papers

The working set model for program behavior was invented in 1965. It has stood the test of time in virtual memory management for over 50 years. It is considered the ideal for managing memory in operating systems and caches. Its superior performance was ...
A page replacement algorithm based on a fuzzy approach to improve cache memory performance
Abstract
The memory management in the operating system includes a part called the page replacement algorithms. Replacement algorithms in environments that require high-performance computing are considered as an important issue. For example, these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 19, Issue 5

May 1976

83 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/360051

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1976

Published in CACM Volume 19, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
1,021
Total Downloads

Downloads (Last 12 months)194
Downloads (Last 6 weeks)34

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

COŞAR BSAY BDÖKEROĞLU T(2023)A New Greedy Algorithm for the Curriculum-based Course Timetabling ProblemMüfredat Tabanlı Ders Çizelgeleme Problemi için Yeni Bir Açgözlü AlgoritmaDüzce Üniversitesi Bilim ve Teknoloji Dergisi10.29130/dubited.1113519Online publication date: 30-Apr-2023
https://doi.org/10.29130/dubited.1113519
(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Thomasian A(2022)IntroductionStorage Systems10.1016/B978-0-32-390796-5.00010-3(1-87)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00010-3
Denning P(2021)Working Set AnalyticsACM Computing Surveys10.1145/339970953:6(1-36)Online publication date: 2-Feb-2021
https://dl.acm.org/doi/10.1145/3399709
Li PPronovost CWilson WTait BZhou JDing CCriswell JBahar IHerlihy MWitchel ELebeck A(2019)Beating OPT with Statistical Clairvoyance and Variable Size CachingProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304067(243-256)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304067
Brock JDing CXu XZhang YDubach CXue J(2018)PAYJIT: space-optimal JIT compilation and its practical implementationProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179523(71-81)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179523
Brock JYe CDing CJacob B(2016)Replacement Policies for Heterogeneous MemoriesProceedings of the Second International Symposium on Memory Systems10.1145/2989081.2989123(232-237)Online publication date: 3-Oct-2016
https://dl.acm.org/doi/10.1145/2989081.2989123
Denning P(2014)Virtual MemoryComputing Handbook, Third Edition10.1201/b16812-62(1-22)Online publication date: 8-May-2014
https://doi.org/10.1201/b16812-62
Denning P(2014)Structure and Organization of Computing*Computing Handbook, Third Edition10.1201/b16812-3(1-14)Online publication date: 8-May-2014
https://doi.org/10.1201/b16812-3
Kakeshita TKambayashi Y(2007)Optimal Concurrency Control Schedulers in Terms of Secondary Storage AccessSystems and Computers in Japan10.1002/scj.469021030821:3(76-86)Online publication date: 6-Sep-2007
https://doi.org/10.1002/scj.4690210308
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

The EELRU adaptive replacement algorithm

Working Set Analytics

A page replacement algorithm based on a fuzzy approach to improve cache memory performance

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations