Properties of the working-set model

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Properties of the working-set model

Full text

Pdf (672 KB)

Source

Communications of the ACM archive
Volume 15 , Issue 3 (March 1972) table of contents

Pages: 191 - 198

Year of Publication: 1972

ISSN:0001-0782

Authors

Peter J. Denning	Princeton Univ., Princeton, NJ
Stuart C. Schwartz	Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 50, Citation Count: 54

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

ABSTRACT

A program's working set W(t, T) at time t is the set of distinct pages among the T most recently referenced pages. Relations between the average working-set size, the missing-page rate, and the interreference-interval distribution may be derived both from time-average definitions and from ensemble-average (statistical) definitions. An efficient algorithm for estimating these quantities is given. The relation to LRU (lease recently used) paging is characterized. The independent-reference model, in which page references are statistically independent, is used to assess the effects of interpage dependencies on working-set size observations. Under general assumptions, working-set size is shown to be normally distributed.

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	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]
	2	Belady, L. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 2 (1966), 78-101.
	3	Brawn, B., and Gustavson, F. Program behavior in a paging environment. Proc. AFIPS 1968 FJCC Vol. 33, Pt. 2, AFIPS Press, Montvale, N.J., pp. 1019-1032.
	4	E. G. Coffman, Jr. , R. C. Wood, Interarrival statistics for time sharing systems, Communications of the ACM, v.9 n.7, p.500-503, July 1966 [doi>10.1145/365719.365961]
	5	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 [doi>10.1145/361268.361280]
	6	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]
	7	P. J. Denning, RESOURCE ALLOCATION IN MULTIPROCESS COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1968
	8	Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
	9	Doherty, W. Scheduling TSS/360 for responsiveness. Proc. AFIPS 1970 FJCC Vol. 37, AFIPS Press, Montvale, N.J., pp. 97-112.
	10	E. Fuchs , P. E. Jackson, Estimates of distributions of random variables for certain computer communications traffic models, Communications of the ACM, v.13 n.12, p.752-757, Dec. 1970 [doi>10.1145/362814.362830]
	11	Liptay, J. The cache, lBMSyst. J. 7, 1 (1968), 15-21.
	12	Mattson, R., Gecsei, J., Slutz, D., and Traiger, I. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
	13	Rosenblatt, M. A central limit theorem and a strong mixing condition. Proc. Nat. Acad. Sci. 42 (1956), 43-47.
	14	D. Sayre, Is automatic “folding” of programs efficient enough to displace manual?, Communications of the ACM, v.12 n.12, p.656-660, Dec. 1969 [doi>10.1145/363626.363629]
	15	Yaglom, A.M. Stationary Random Functions. Prentice-Hall, Englewood Cliffs, N.J., 1962.
	16	Weizer, N., and Oppenheimer, G. Virtual memory management in a paging environment. Proc. 1969 SJCC Vol. 34, AFIPS Press, Montvale, N.J., p. 234.

CITED BY 54

	Peter J. Denning , Donald R. Slutz, Generalized working sets for segment reference strings, Communications of the ACM, v.21 n.9, p.750-759, Sept. 1978
	Huei-hsiung Chuang, Multiprogramming under separate working-set principle, Proceedings of the annual conference, p.428.4-429, August 27-29, 1973, Atlanta, Georgia, United States
	E. Sadeh, An analysis of the performance of the page fault frequency (PFF) replacement algorithm., ACM SIGOPS Operating Systems Review, v.9 n.5, p.6-13, November 1975
	Peter D. Welch, On the self contained modelling of DB/DC systems, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.14-24, March 29-31, 1976, Cambridge, Massachusetts, United States
	Jeffrey Scott Vitter, Analysis of the Search Performance of Coalesced Hashing, Journal of the ACM (JACM), v.30 n.2, p.231-258, April 1983
	Isao Miyamoto, Some considerations in database application programming, Proceedings of the 2nd international conference on Software engineering, p.545-555, October 13-15, 1976, San Francisco, California, United States
	Peter J. Denning , Kevin C. Kahn, A study of program locality and lifetime functions, ACM SIGOPS Operating Systems Review, v.9 n.5, p.207-216, November 1975
	Avi Mendelson , Freddy Gabbay, The effect of seance communication on multiprocessing systems, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.252-281, May 2001
	Shikharesh Majumdar , Richard B. Bunt, Measurement and analysis of locality phases in file referencing behaviour, ACM SIGMETRICS Performance Evaluation Review, v.14 n.1, p.180-192, May 1986
	William T. Marshall , C. Thomas Nute, Analytic modelling of “working set like” replacement algorithms, ACM SIGMETRICS Performance Evaluation Review, v.8 n.3, p.65-72, Fall 1979
	Kenneth J. Thurber , Peter C. Patton, Page size selection for a real time computer, Proceedings of the 1975 annual conference, p.198-203, January 1975
	Arvind , R. Y. Kain , E. Sadeh, On reference string generation processes, ACM SIGOPS Operating Systems Review, v.7 n.4, p.80-87, October 1973
	Richard W. Carr , John L. Hennessy, WSCLOCK—a simple and effective algorithm for virtual memory management, ACM SIGOPS Operating Systems Review, v.15 n.5, p.87-95, December 1981
	J. H. Hester , D. S. Hirschberg, Self-organizing linear search, ACM Computing Surveys (CSUR), v.17 n.3, p.295-311, Sept. 1985
	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
	D. R. Slutz , I. L. Traiger, A note on the calculation of average working set size, Communications of the ACM, v.17 n.10, p.563-565, Oct. 1974
	Daniel G. Bobrow , Jerry D. Burchfiel , Daniel L. Murphy , Raymond S. Tomlinson, TENEX, a paged time sharing system for the PDP - 10, Communications of the ACM, v.15 n.3, p.135-143, March 1972
	Juan Rodriguez-Rosell, Empirical working set behavior, Communications of the ACM, v.16 n.9, p.556-560, Sept. 1973
	M. A. Franklin , G. Scott Graham , R. K. Gupta, Anomalies with variable partition paging algorithms, Communications of the ACM, v.21 n.3, p.232-236, March 1978
	Norman M. Aaronson, AGSICP: An Automated Grading System for the Instruction of Cobol Programming, Proceedings of the annual conference, p.428.1-429, August 27-29, 1973, Atlanta, Georgia, United States
	Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, ACM SIGPLAN Notices, v.37 n.1, p.140-153, Jan. 2002
	M. C. Easton , B. T. Bennett, Transient-free working-set statistics, Communications of the ACM, v.20 n.2, p.93-99, Feb. 1977
	Patrice Burgevin , Jacques Leroudier, Characteristics and models of program behaviour, Proceedings of the annual conference, p.344-350, October 20-22, 1976, Houston, Texas, United States
	J. M. Murphy , R. B. Bunt, Characterising program behaviour with phases and transitions, ACM SIGMETRICS Performance Evaluation Review, v.16 n.1, p.226-234, May 1988
	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
	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
	K. M. Chandy , T. W. Keller , J. C. Browne, Design automation and queueing networks: An interactive system for the evaluation of computer queueing models, Proceedings of the 9th workshop on Design automation, p.357-367, June 26-28, 1972
	Pietro Manzoni , Paolo Cremonesi , Giuseppe Serazzi, Workload models of VBR video traffic and their use in resource allocation policies, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.387-397, June 1999
	A. Choi , M. Ruschitzka, Managing Locality Sets: The Model and Fixed-Size Buffers, IEEE Transactions on Computers, v.42 n.2, p.190-204, February 1993
	Amir H. Hashemi , David R. Kaeli , Brad Calder, Efficient procedure mapping using cache line coloring, ACM SIGPLAN Notices, v.32 n.5, p.171-182, May 1997
	Alan Jay Smith, Bibliography on paging and related topics, ACM SIGOPS Operating Systems Review, v.12 n.4, p.39-56, October 1978
	Wolfgang Effelsberg , Mary E. S. Loomis, Logical, internal, and physical reference behavior in CODASYL database systems, ACM Transactions on Database Systems (TODS), v.9 n.2, p.187-213, June 1984
	Hock-Beng Lim , Pen-Chung Yew, Parallel program behavioral study on a shared-memory multiprocessor, Proceedings of the 5th international conference on Supercomputing, p.386-395, June 17-21, 1991, Cologne, West Germany
	James Wittneben , Dennis Kafura, A simple reference string sampling method, Proceedings of the ACM 1980 annual conference, p.191-196, January 1980
	Emily C. Placy , Jon C. Strauss, A model hierarchy for virtual memory system investigation, Proceedings of the 7th conference on Winter simulation, p.415-420, January 14-16, 1974, Washington, DC
	Jaswinder Pal Singh , Harold S. Stone , Dominique F. Thiébaut, A Model of Workloads and its Use in Miss-Rate Prediction for Fully Associative Caches, IEEE Transactions on Computers, v.41 n.7, p.811-825, July 1992
	Joel L. Wolf , Harold S. Stone , Dominique Thiébaut, Synthetic Traces for Trace-Driven Simulation of Cache Memories, IEEE Transactions on Computers, v.41 n.4, p.388-410, April 1992
	Yuanyuan Zhou , Zhifeng Chen , Kai Li, Second-Level Buffer Cache Management, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.505-519, June 2004
	M. Kobayashi , M. H. MacDougall, The Stack Growth Function: Cache Line Reference Models, IEEE Transactions on Computers, v.38 n.6, p.798-805, June 1989
	Makoto Kobayashi, A cache multitasking model, ACM SIGMETRICS Performance Evaluation Review, v.20 n.2, p.27-37, Nov. 1992
	Ying-Hong Wang , Chih-Feng Chao , Shih-Wei Lin , Wei-Ting Chen, A distributed data caching framework for mobile ad hoc networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Antonis Panagakis , Athanasios Vaios , Ioannis Stavrakakis, Approximate analysis of LRU in the case of short term correlations, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.6, p.1142-1152, April, 2008
	Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
	Razvan Cheveresan , Matt Ramsay , Chris Feucht , Ilya Sharapov, Characteristics of workloads used in high performance and technical computing, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
	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
	Jeremy Lau , Erez Perelman , Brad Calder, Selecting Software Phase Markers with Code Structure Analysis, Proceedings of the International Symposium on Code Generation and Optimization, p.135-146, March 26-29, 2006
	David S. Burris , Udo W. Pooch, The dynamic matrix model, Proceedings of the 1977 annual conference, p.386-391, January 1977
	N. A. Oliver, Experimental data on page replacement algorithm, Proceedings of the May 6-10, 1974, national computer conference and exposition, May 06-10, 1974, Chicago, Illinois
	Isao Miyamoto, Hierarchical performance analysis models for data base systems, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts
	Subhasis Banerjee , G. Surendra , S. K. Nandy, On the effectiveness of phase based regression models to trade power and performance using dynamic processor adaptation, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.8, p.797-815, August, 2008
	A. DeCegama, A methodology for computer model building, Proceedings of the December 5-7, 1972, fall joint computer conference, part I, 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
	Peter J. Denning, On modeling program behavior, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	K. V. Sastry, Balancing processor shares of scheduling classes through controlled allocation of memory, Proceedings of the May 19-22, 1980, national computer conference, May 19-22, 1980, Anaheim, California

INDEX TERMS

Keywords:
paging, paging algorithms, program behavior, program modeling, working-set model

Collaborative Colleagues:

Peter J. Denning: colleagues

Stuart C. Schwartz: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player