Principles of Optimal Page Replacement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Principles of Optimal Page Replacement

Full text

Pdf (875 KB)

Source

Journal of the ACM (JACM) archive
Volume 18 , Issue 1 (January 1971) table of contents

Pages: 80 - 93

Year of Publication: 1971

ISSN:0004-5411

Authors

Alfred V. Aho	Bell Telephone Laboratories, Inc., Murray Hill, New Jersey
Peter J. Denning	Princeton University, Princeton, New Jersey
Jeffrey D. Ullman	Princeton University, Princeton, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 41, Downloads (12 Months): 224, Citation Count: 58

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321623.321632 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	KILBURN, T., EDWARDS, D. B. G., LANIGAN, M. J., AND SUMNER, F.H. One-level storage system. IRE Trans. EC-11, 2 (April 1962), 223-235.
	2	Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
	3	B. W. Arden , B. A. Galler , T. C. O'Brien , F. H. Westervelt, Program and Addressing Structure in a Time-Sharing Environment, Journal of the ACM (JACM), v.13 n.1, p.1-16, Jan. 1966 [doi>10.1145/321312.321313]
	4	Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
	5	BELADY, L .A . A study of replacement algorithms for virtual storage computers. IBM Sys. J . 5, 2 (1966), 78--101.
	6	Gerald H. Fine , Calvin W. Jackson , Paul V. Mc Isaac, Dynamic program behavior under paging, Proceedings of the 1966 21st national conference, p.223-228, January 1966 [doi>10.1145/800256.810701]
	7	SHEMER, J. E., AND SHIPPEY, B. Statistical analysis of paged and segmented computer systems. IEEE Trans. EC-15, 6 (Dec. 1966), 855-863.
	8	CORBA~O, F .J . A Paging experiment with the multics system. Proj. MAC Rep. MAC-M- 384, M.I.T., Cambridge, Mass., May 1968.
	9	E. G. Coffman , L. C. Varian, Further experimental data on the behavior of programs in a paging environment, Communications of the ACM, v.11 n.7, p.471-474, July 1968 [doi>10.1145/363397.363398]
	10	John L. Smith, Microprogamming under a page on demand strategy, Communications of the ACM, v.10 n.10, p.636-646, Oct. 1967 [doi>10.1145/363717.363763]
	11	Tad Brian Pinkerton, Program behavior and control in virtual storage computer systems, 1968
	12	Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
	13	~ ~ CHEN, Y. C., AND SHEDI~ER, G.S. A model for program behavior under demand paging. Report RC-2301, IBM T. J . Watson Research Center, Yorktown Heights, N. Y. (Sept. 1968).
	14	H. Hellerman, Complementary replacement: a meta scheduling principle, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961070]
	15	MATTSON, R. L., GECSEI, J., SLUTN, D. R., AND TRAIOER, I .L . Evaluation technlques for storage hierarchies. IBM Sys. J . 9, 2 (1970), 78-117.
	16	L. A. Belady , R. A. Nelson , G. S. Shedler, An anomaly in space-time characteristics of certain programs running in a paging machine, Communications of the ACM, v.12 n.6, p.349-353, June 1969 [doi>10.1145/363011.363155]

CITED BY 58

	Dominique Potier, Analysis of demand paging policies with swapped working sets, ACM SIGOPS Operating Systems Review, v.11 n.5, p.125-131, November 1977
	A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989
	R. L. Ashenhurst, Curriculum recommendations for graduate professional programs in information systems, Communications of the ACM, v.15 n.5, p.363-398, May 1972
	Greg Henderson , Juan Rodriguez-Rosell, The optimal choice of window sizes for working set dispatching, ACM SIGMETRICS Performance Evaluation Review, v.3 n.4, p.10-33, December 1974
	P. C. Yue , C. K. Wong, On the Optimality of the Probability Ranking Scheme in Storage Applications, Journal of the ACM (JACM), v.20 n.4, p.624-633, Oct. 1973
	J. Daniel Couger, Curriculum recommendations for undergraduate programs in information systems, Communications of the ACM, v.16 n.12, p.727-749, Dec. 1973
	Richard E. Ladner , James D. Fix , Anthony LaMarca, Cache performance analysis of traversals and random accesses, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.613-622, January 17-19, 1999, Baltimore, Maryland, United States
	Udo W. Pooch, A dynamic clustering strategy in a demand paging environment, ACM SIGSIM Simulation Digest, v.7 n.4, p.11-22, July 1976
	P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974
	Giorgio Ingargiola , James F. Korsh, Finding Optimal Demand Paging Algorithms, Journal of the ACM (JACM), v.21 n.1, p.40-53, Jan. 1974
	Vincenzo Liberatore, Empirical investigation of the Markov reference model, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.653-662, January 17-19, 1999, Baltimore, Maryland, United States
	Yannis Smaragdakis , Scott Kaplan , Paul Wilson, The EELRU adaptive replacement algorithm, Performance Evaluation, v.53 n.2, p.93-123, July 2003
	Ronald Fagin , Malcolm C. Easton, The independence of miss ratio on page size, Journal of the ACM (JACM), v.23 n.1, p.128-146, Jan. 1976
	Mohammad Malkawi , Janek Patel, Compiler directed memory management policy for numerical programs, ACM SIGOPS Operating Systems Review, v.19 n.5, p.97-106, Dec. 1-4, 1985
	Alan Jay Smith, On the effectiveness of set associative page mapping and its application to main memory management, Proceedings of the 2nd international conference on Software engineering, p.286-292, October 13-15, 1976, San Francisco, California, United States
	Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, ACM SIGMOD Record, v.22 n.2, p.297-306, June 1, 1993
	Ronald Fagin, A counterintuitive example of computer paging, Communications of the ACM, v.19 n.2, p.96-97, Feb. 1976
	Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972
	Yannis Smaragdakis , Scott Kaplan , Paul Wilson, EELRU: simple and effective adaptive page replacement, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.122-133, June 1999
	Percy Tzelnic , Izidor Gertner, An Approach to Program Behavior Modeling and Optimal Memory Control, Journal of the ACM (JACM), v.29 n.2, p.527-554, April 1982
	Debasis Mitra, Some Aspects of Hierarchical Memory Systems, Journal of the ACM (JACM), v.21 n.1, p.54-65, Jan. 1974
	Gideon Glass , Pei Cao, Adaptive page replacement based on memory reference behavior, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.115-126, June 1997
	Lee J. Scheffier, Optimal folding of a paging drum in a three level memory system, ACM SIGOPS Operating Systems Review, v.7 n.4, p.58-65, October 1973
	Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, ACM SIGPLAN Notices, v.34 n.5, p.1-12, May 1999
	M. A. Franklin , R. K. Gupta, Computation of page fault probability from program transition diagram, Communications of the ACM, v.17 n.4, p.186-191, April 1974
	Windsor W. Hsu , Alan Jay Smith , Honesty C. Young, I/O reference behavior of production database workloads and the TPC benchmarks—an analysis at the logical level, ACM Transactions on Database Systems (TODS), v.26 n.1, p.96-143, March 2001
	Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, An optimality proof of the LRU-K page replacement algorithm, Journal of the ACM (JACM), v.46 n.1, p.92-112, Jan. 1999
	Udo W. Pooch , David M. Burris, A Modified Locality Matrix Model (MLMM) - dynamic clustering in a demand paging environment, Proceedings of the annual conference, p.337-343, October 20-22, 1976, Houston, Texas, United States
	E. G. Coffman, Jr. , Thomas A. Ryan, Jr., A study of storage partitioning using a mathematical model of locality, Communications of the ACM, v.15 n.3, p.185-190, March 1972
	Alan Jay Smith, Sequentiality and prefetching in database systems, ACM Transactions on Database Systems (TODS), v.3 n.3, p.223-247, Sept. 1978
	Ekow Otoo , Frank Olken , Arie Shoshani, Disk cache replacement algorithm for storage resource managers in data grids, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-15, November 16, 2002, Baltimore, Maryland
	Alan Jay Smith, Bibliography on paging and related topics, ACM SIGOPS Operating Systems Review, v.12 n.4, p.39-56, October 1978
	V. F. Russo , R. H. Campbell, Virtual memory and backing storage management in multiprocessor operating systems using object-oriented design techniques, ACM SIGPLAN Notices, v.24 n.10, p.267-278, Oct. 1989
	Song Jiang , Xiaodong Zhang, TPF: a dynamic system thrashing protection facility, Software—Practice & Experience, v.32 n.3, p.295-318, March 2002
	Michael W. Condry, Paging as a "language processing" task, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.63-76, January 26-28, 1981, Williamsburg, Virginia
	Peter J. Denning , Bruce A. Eisenstein, Statistical methods in performance evaluation, Proceedings of the SIGOPS workshop on System performance evaluation, p.284-307, January 1971
	Özalp Babaoǧlu, Hierarchical replacement decisions in hierarchical stores, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
	Masamichi Takagi , Kei Hiraki, Inter-reference gap distribution replacement: an improved replacement algorithm for set-associative caches, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Yannis Smaragdakis, General adaptive replacement policies, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	W. W. Hsu , A. Jay Smith , H. C. Young, Characteristics of production database workloads and the TPC benchmarks, IBM Systems Journal, v.40 n.3, p.781-802, March 2001
	Russ Blake, Optimal control of thrashing, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
	Silvano Maffeis, Cache management algorithms for flexible filesystems, ACM SIGMETRICS Performance Evaluation Review, v.21 n.2, p.16-25, Dec. 1993
	Nimrod Megiddo , Dharmendra S. Modha, Outperforming LRU with an Adaptive Replacement Cache Algorithm, Computer, v.37 n.4, p.58-65, April 2004
	Saied Hosseini-Khayat, On Optimal Replacement of Nonuniform Cache Objects, IEEE Transactions on Computers, v.49 n.8, p.769-778, August 2000
	Junyi Xie , Jun Yang , Yuguo Chen, On joining and caching stochastic streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Song Jiang , Xiaodong Zhang, Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems, Performance Evaluation, v.60 n.1-4, p.5-29, May 2005
	Y. C. Tay , Min Zou, A page fault equation for modeling the effect of memory size, Performance Evaluation, v.63 n.2, p.99-130, February 2006
	Jay Nelson, Concurrent caching, Proceedings of the 2006 ACM SIGPLAN workshop on Erlang, September 16-16, 2006, Portland, Oregon, USA
	Jonathan Weinberg , Allan Edward Snavely, Accurate memory signatures and synthetic address traces for HPC applications, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Yong Tan , Yonghua Ji , Vijay S. Mookerjee, Analyzing Document-Duplication Effects on Policies for Browser and Proxy Caching, INFORMS Journal on Computing, v.18 n.4, p.506-522, January 2006
	John E. Pomeranz, Some comments on Denning's principle of optimality, ACM SIGOPS Operating Systems Review, v.4 n.3, p.19-20, December 1970
	Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
	Sorav Bansal , Dharmendra S. Modha, CAR: Clock with Adaptive Replacement, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
	David S. Burris , Udo W. Pooch, The dynamic matrix model, Proceedings of the 1977 annual conference, p.386-391, January 1977
	Stephen R. Kimbleton, Core complement policies for memory allocation and analysis, Proceedings of the December 5-7, 1972, fall joint computer conference, part II, December 05-07, 1972, Anaheim, California
	Jeffrey R. Spirn , Peter J. Denning, Experiments with program locality, Proceedings of the December 5-7, 1972, fall joint computer conference, part I, December 05-07, 1972, Anaheim, California
	Benjamin Aminof , Orna Kupferman , Robby Lampert, Reasoning about online algorithms with weighted automata, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.835-844, January 04-06, 2009, New York, New York
	Fadi N. Sibai , Maria Ma , David A. Lill, Teaching page replacement algorithms with a Java-based VM simulator, Proceedings of the 14th Western Canadian Conference on Computing Education, May 01-02, 2009, Burnaby, British Columbia, Canada