Some Distribution-Free Aspects of Paging Algorithm Performance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Distribution-Free Aspects of Paging Algorithm Performance

Full text

Pdf (480 KB)

Source

Journal of the ACM (JACM) archive
Volume 21 , Issue 1 (January 1974) table of contents

Pages: 31 - 39

Year of Publication: 1974

ISSN:0004-5411

Authors

P. A. Franaszek	IBM Thomas J. Watson Research Center, Yorktown Heights, New York
T. J. Wagner	University of Texas, Austin, TX and IBM Thomas J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 37, Citation Count: 20

Additional Information:

abstract 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/321796.321800 What is a DOI?

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.

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	GECSEI, J., SLUTZ, D. R., TRAIGER, I., AND MATTSON, R. Evaluation techniques for storage hierarchies. IBM Syst. J. 11 (1970), 78-117.
	2	BELADY, L.A. A study of replacement algorithms for a virtual storage computer. IBM Syst. J. 5 (1966), 78-101.
	3	B. Randell , C. J. Kuehner, Dynamic storage allocation systems, Communications of the ACM, v.11 n.5, p.297-306, May 1968 [doi>10.1145/363095.363138]
	4	K~NG, W. F., III. Analysis of demand paging algorithms. Proc. IFIP Congr. 1971, North-Holland Pub. Co., Amsterdam, pp. 155-159.
	5	Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
	6	LIPTAY, J.S. The cache. IBM Syst. J. Issue on Structural Aspects of System/360 Model 85, 7, 1 (1968), 15-21.
	7	Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
	8	ALEXAND~a, M.T. Time sharing supervisor programs. U. of Michigan Computing Center Rep., Ann Arbor, Mich., May 1970.
	9	DooB, J. L. Stochastic Processes. Wiley, New York, 1953.
	10	ACEVEDO, M.F. A probabilistic study of two-level storage hierarchies. M.S. Th., U. of Texas, Austin, Texas, Dec. 1972.

CITED BY 20

	Avi Bittan , Yaakov Kogan , Philip S. Yu, Asymptotic performance of a buffer model in a data sharing environment, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.67-76, May 1994
	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985
	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
	Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976
	Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978
	Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Gopal Pandurangan , Eli Upfal, Can entropy characterize performance of online algorithms?, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.727-734, January 07-09, 2001, Washington, D.C., United States
	Friedhelm Meyer auf der Heide , Berthold Vöcking , Matthias Westermann, Caching in networks (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.430-439, January 09-11, 2000, San Francisco, California, United States
	Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States
	Asit Dan , Don Towsley, An approximate analysis of the LRU and FIFO buffer replacement schemes, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.143-152, May 1990
	J. van den Berg , D. Toswley, Properties of the Miss Ratio for a 2-Level Storage Model with LRU or FIFO Replacement Strategy and Independent References, IEEE Transactions on Computers, v.42 n.4, p.508-512, April 1993
	Alan Jay Smith, Bibliography on paging and related topics, ACM SIGOPS Operating Systems Review, v.12 n.4, p.39-56, October 1978
	Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly competitive algorithms for paging with locality of reference, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.228-236, September 1992, Orlando, Florida, United States
	Allan Borodin, Can competitive analysis be made competitive?, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Daniel Dominic Sleator , Robert Endre Tarjan, Amortized efficiency of list update rules, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.488-492, December 1984
	Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Journal of Computer and System Sciences, v.70 n.2, p.145-175, March 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
	Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	P. Brighten Godfrey , Scott Shenker , Ion Stoica, Minimizing churn in distributed systems, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
	Giovanni Maria Sacco, Index Access with a Finite Buffer, Proceedings of the 13th International Conference on Very Large Data Bases, p.301-309, September 01-04, 1987