Generalized working sets for segment reference strings

ABSTRACT

The working-set concept is extended for programs that reference segments of different sizes. The generalized working-set policy (GWS) keeps as its resident set those segments whose retention costs do not exceed their retrieval costs. The GWS is a model for the entire class of demand-fetching memory policies that satisfy a resident-set inclusion property. A generalized optimal policy (GOPT) is also defined; at its operating points it minimizes aggregated retention and swapping costs. Special cases of the cost structure allow GWS and GOPT to simulate any known stack algorithm, the working set, and VMIN. Efficient procedures for computing demand curves showing swapping load as a function of memory usage are developed for GWS and GOPT policies. Empirical data from an actual system are included.

REFERENCES

• 1: Bard, Y. Characterization of program paging in a time sharing environment. IBM J. Res. and Develop. 17, 5 (Sept. 1973), 387-393.
• 2: Bard, Y. Application of the page survival index (PSI) to virtual memory system performance. IBM J. Res. and Develop. 19, 3 (May 1975), 212-220.
• 3: Belady, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 2 (1966), 78-101.
• 4: Belady, L.A., and Palermo, F.P. On-line measurement of paging behavior by the multilevel MIN algorithm. IBM J. Res. and Develop. 18, I (Jan. 1974), 2-19.
• 5: Chu, W.W., and Opderbeck, H. "The page fault frequency paging algorithm. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. 1, AFIPS Press, Montvale, N.J., pp. 597-609.
• 6: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 7: 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]
• 8: Courtois, P.J. Decomposability. Academic Press, New York, 1977.
• 9: 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]
• 10: Denning, P.J. Optimal multiprogrammed memory management. In Current Trends in Programming Methodology II1, K.M. Chandy and R. Yeh, Eds., Prentice-Hall, Englewood Cliffs, N.J., (1978), 298-322.
• 11: Denning, P.J. The computation and use of optimal paging curves. Tech. Rep. CSD-TR-154, Comptr. Sci. Dept., Purdue University, W. Lafayette, Ind., June 1975.
• 12: Denning, P.J., and Graham, G.S. Multiprogrammed memory management. Proc. IEEE 63, 6 (June 1975), 924-939.
• 13: Denning, P.J., Kahn, K.C., Leroudier, J., Potier, D., and Suri, R. Optimal multiprogramming. A cta Informatica 7, 2 (1976), 197-216.
• 14: 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 [doi>10.1145/361268.361281]
• 15: Peter J. Denning , Kevin C. Kahn, A study of program locality and lifetime functions, Proceedings of the fifth ACM symposium on Operating systems principles, p.207-216, November 19-21, 1975, Austin, Texas, United States
• 16: M. C. Easton , B. T. Bennett, Transient-free working-set statistics, Communications of the ACM, v.20 n.2, p.93-99, Feb. 1977 [doi>10.1145/359423.359431]
• 17: 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 [doi>10.1145/359361.359451]
• 18: Graham, G.S., and Denning, P.J. On the relative controllability of memory policies. Proc. Int. Symp. Comptr. Performance Modeling, Measurement, and Evaluation, Aug. 1977, North-Holland, Amsterdam, 1977, pp. 411-428.
• 19: A. Wayne Madison , Alan P. Batson, Characteristics of program localities, Communications of the ACM, v.19 n.5, p.285-294, May 1976 [doi>10.1145/360051.360227]
• 20: Mattson, R.L., Gecsei, J., Slutz, D.R., and Traiger, I.L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-101.
• 21: Barton G. Prieve , R. S. Fabry, MIN—an optimal variable-space page replacement algorithm, Communications of the ACM, v.19 n.5, p.295-297, May 1976 [doi>10.1145/360051.360231]
• 22: Ragaz, N., and Rodriguez-Rosell, J. Empirical studies of storage management in a data base system. IBM Res. Rep. RJ 1834, IBM Res. Lab., San Jose, Calif., May 1976.
• 23: Rodriqucz-Rosell, J. "Empirical data reference behavior in data base systems. IEEE Computer 9, 11 (Nov. 1976), 9-13.
• 24: Slutz, D.R. A relation between working set and optimal algorithms for segment reference strings. IBM Res. Rep. RJ 1623, IBM Res. Lab., San Jose, Calif., July 1975.
• 25: 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 [doi>10.1145/355620.361167]
• 26: Smith, A.J. A modified working set paging algorithm. IEEE Trans. Comptrs. C-25, 9 (Sept. 1976), 907-914.
• 27: K. Sreenivasan , A. J. Kleinman, On the construction of a representative synthetic workload, Communications of the ACM, v.17 n.3, p.127-133, March 1974 [doi>10.1145/360860.360863]
• 28: Tran-Quoc-Te. An open formulation of working set policies. Rep. 10, Proj. MIMOSA, Facultes Universitaires N.-D. de la Paix, Belgium, Dec. 1975.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Languages, Management, Measurement, Performance, Theory

Keywords:
database referencing, memory management, optimal memory policies, paging, program behavior, program measurement, segmentation, working sets