Summary
Existing models of program behaviour are shown to give an incomplete account of program locality. A model based on the distinction between short- and long-run equilibrium states in nearly completely decomposable systems is proposed to overcome this deficiency. This distinction leads to the combined use of a Markovian model of the transitions between localities and of separate models for the locality short-term behaviours. This combination is shown to give better estimations of the page fault rate and of the working set size distribution. The conditions under which this distribution is approximately normal and under which the assumptions of independent page references are valid are also clarified. The approach is illustrated by a numerical example, showing in particular that other models presented in the literature may have computer time and space requirements which are beyond practical possibilities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Denning, P. J., Ullman, J. D.: Principles of optimal page replacement. J. ACM 18, 80–93 (1971)
Batson, A. P., Madison, A. W.: Measurements of major locality phases in symbolic reference strings. Proc. of the ACM-SIGMETRICS and IFIP-W.G.7.3 Internat. Symp. on Computer Performance Modeling, Measurement and Evaluation, Cambridge (Mass.), 1976, p. 75–84
Belady, L. A.: A study of replacement algorithms for virtual storage computers. IBM Systems J. 5, 78–101 (1966)
Bryant, P.: Predicting working set sizes. IBM J. R and D 19, 221–229 (1975)
Coffman Jr., E. G., Ryan Jr., T. A.: A study of storage partitioning using a mathematical model of locality. Comm. ACM 15, 185–190 (1972)
Courtois, P.-J.: On the near-complete-decomposability of networks of queues and of stochastic models of multiprogramming computing systems. Carnegie-Mellon University, Dept. of Comp. Sc., Pittsburgh (Pa.) CMU-CS-72-111, 1972
Courtois, P.-J.: Error analysis in nearly completely decomposable stochastic systems. Econometrica 43, 691–709 (1975)
Denning, P. J.: The working set model for program behavior. Comm. ACM 11, 323–333 (1968)
Denning, P. J.: Virtual memory. Computing Surveys 2, 153–189 (1970)
Denning, P. J., Kahn, K. C.: A study of program locality and lifetime functions. Proc. of the 5th ACM-SIGOPS Symposium on Operating Systems Principles, Austin (Texas), 1975, p. 207–216
Denning, P. J., Schwartz, S. C.: Properties of the working set model. Comm. ACM 15, 191–198 (1972)
Fine, G. H., Jackson, C. W., McIsaac, P. V.: Dynamic program behavior under paging. Proc. of the ACM National Conference 1966. Washington (D.C.): Thompson Book 1966, p. 223–228
Franklin, M. A., Gupta, R. K.: Computation of page fault probability from program transition diagram. Comm. ACM 17, 186–191 (1974)
Freiberger, W. F., Grenander, U., Sampson, P. D.: Patterns in program references. IBM J. R and D 19, 230–243 (1975)
Gelenbe, E.: A unified approach to the evaluation of a class of replacement algorithms. IEEE Trans. Computers C-22, 611–618 (1973)
Glowacki, C.: Quelques résultats explicites sur certains algorithmes de remplacement de page. Private communication (1975)
Hatfield, D. J., Gerald, J.: Program restructuring for virtual memory. IBM Systems J. 10, 168–192 (1971)
Hoare, C. A. R., McKeag, R. M.: A survey of storage management techniques. Part two. In: Hoare, C. A. R., Perrot, R. H. (eds.): Operating system techniques London: Academic Press 1972, p. 132–151
King III, W.: Analysis of demand paging algorithms. Proc. IFIP Congress 1971, Ljubljana. Amsterdam: North-Holland 1971, p. 155–159
Kral, J.: One way of estimating frequencies of jumps in a program. Comm. ACM 11, 475–480 (1968)
Madison, A. W., Batson, A. P.: Characteristics of program localities. Comm. ACM 19, 285–294 (1976)
Mattson, R. L., Gecsei, J., Slutz, D. R., Traiger, I. W.: Evaluation techniques for storage hierarchies. IBM Systems J. 9, 78–117 (1970)
Naur, P.: The performance of a system for automatic segmentation of programs within an Algol Compiler (GIER Algol). Comm. ACM 8, 671–676, 686 (1965)
Rodriguez-Rosell, J.: Empirical working set behavior. Comm. ACM 16, 556–560 (1973)
Shedler, G. S., Tung, C.: Locality in page reference strings. SIAM J. Computing 1, 218–241 (1972)
Simon, H. A.: The sciences of the artificial. Cambridge (Mass.): MIT Press 1969
Simon, H. A., Ando, A.: Aggregation of variables in dynamic systems. Econometrica 29, 111–138 (1961)
Spirn, J. R., Denning, P. J.: Experiments with program locality. Proc. AFIPS 1972 FJCC. Montvale (N.J.): AFIPS Press 1972, p. 611–621
Spirn, J. R., Denning, P. J., Savage, J. E.: Models for locality in program behavior, Acta Informatica, to appear
Vantilborgh, H.: On the working set size distribution and its normal approximation. BIT 14, 240–251 (1974)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Courtois, P.J., Vantilborgh, H. A decomposable model of program paging behaviour. Acta Informatica 6, 251–275 (1976). https://doi.org/10.1007/BF00288657
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00288657