Finding Optimal Demand Paging Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding Optimal Demand Paging Algorithms

Full text

Pdf (849 KB)

Source

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

Pages: 40 - 53

Year of Publication: 1974

ISSN:0004-5411

Authors

Giorgio Ingargiola	California Institute of Technology, Pasadena, California
James F. Korsh	Department of Information Sciences, Temple University, School of Business Adminsitration, Philadelphia, PA and California Institute of Technology, Pasadena, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 31, Citation Count: 3

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.321801 What is a DOI?

ABSTRACT

A cost is defined for demand paging algorithms with respect to a formal stochastic model of program behavior. This cost is shown to exist under rather general assumptions, and a computational procedure is given which makes it possible to determine the optimal cost and optimal policy for moderate size programs, when the formal model is known and not time dependent. In this latter case it is shown that these computational procedures may be extended to larger programs to obtain arbitrarily close approximations to their optimal policies. In previous models either unwarranted information is assumed beyond the formal model, or the complete stochastic nature of the model is not taken into account.

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	BELADY, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 2 (1966), 78-101.
	2	MATTSON, R. L., GECSEZ, J., SLUTZ, D. R., AND TRAIGER, I. L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
	3	Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
	4	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]
	5	Azaria Paz, Introduction to probabilistic automata (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1971
	6	FELLER, W. An Introduction to Probability Theory and Its Applications, Vol I. Wiley, New York, 1968.
	7	HOWARD, R.A. Dynamic Programming and Markov Processes. The M.I.T. Press, Cambridge, Mass., 1960.

CITED BY 3

	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
	Alan Jay Smith, Bibliography on paging and related topics, ACM SIGOPS Operating Systems Review, v.12 n.4, p.39-56, October 1978
	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