Decomposability, instabilities, and saturation in multiprogramming systems

ABSTRACT

A step-by-step approach to model the dynamic behavior and evaluate the performance of computing systems is proposed. It is based on a technique of variable aggregation and the concept of nearly decomposable systems, both borrowed from Econometrics. This approach is taken in order to identify in multiprogramming paging systems (i) unstable regimes of operations and (ii) critical computing loads which bring the system into states of saturation. This analysis leads to a more complete definition of the circumstances in which “thrashing” can set in.

REFERENCES

• 1: Betourne, C., and Krakowiack, S. Simulation de l'allocation de Ressources dans un Systme Conversationnel h m6moire virtuelle pagin6e. Proc. Congrs AFCET, Grenoble, France, Nov. 1972.
• 2: Jeffrey P. Buzen, Computational algorithms for closed queueing networks with exponential servers, Communications of the ACM, v.16 n.9, p.527-531, Sept. 1973 [doi>10.1145/362342.362345]
• 3: Courtois, P.J., and Georges, J. An evaluation of the stationary behavior of computations in multiprogramming computer systems. Proc. ACM Int. Comput. Symp., Bonn, Germany, 1970, vol. 1, pp. 98-115.
• 4: Courtois, P.J. On the near-complete-decomposability of networks of queues and of stochastic models of multiprogramming computing systems. Seientif. Rep. CMU-CS-72-11, Carnegie- Mellon U., Nov. 1971.
• 5: Courtois, P.J. Error analysis in nearly decomposable stochastic systems. MBLE Rep. R214, Mar. 1973. To be published in Econometrica (Mar. 1975).
• 6: Denning, P.J. Thrashing; its causes and prevention. Proc. AFIPS 1968 FJCC, vol. 33, AFIPS Press, Montvale, N.J., pp. 915-922.
• 7: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 8: Dijkstra, E.W. Hierarchical ordering of sequential processes. Acta Informatica 1, 2 (1971), 115-138.
• 9: Jackson, J.R. Jobshop-like queueing systems. Mall. Sci. 9, 1 (Oct. 1963), 131-142.
• 10: Kleinrock, L. Certain analytic results for time shared processors. Proc. IFIP 68, North-Holland Pub. Co., Amsterdam, 1969, vol. 2, pp. 838-845.
• 11: Little, J.D.C. A proof for the queueing formula L = XW. Oper. Res. 9 (1961), 383-387.
• 12: Richard R. Muntz , Forest Baskett, III, Open, closed, and mixed networks of queues with different classes of customers., Stanford University, Stanford, CA, 1972
• 13: Parnas, D.L., and Darringer, J.A. SODAS and a methodology for system design. Proc. AFIPS 1967 FJCC, vol. 31, AFIPS Press, Montvale, N.J., pp. 449--474.
• 14: Simon, H.A., and Ando, A. Aggregation of variables in dynamic systems. Econometrica 29, 2 (Apr. 1961), 111-138.
• 15: John L. Smith, Microprogamming under a page on demand strategy, Communications of the ACM, v.10 n.10, p.636-646, Oct. 1967 [doi>10.1145/363717.363763]
• 16: Vantilborgh, H. On random partially preloaded page replacement algorithms. MBLE Rep. R202, Sept. 1972.
• 17: Zurcher, F.W., and Randell, B. Iterative multilevel modelling. A methodology for computer system design. Proc. IFIP 68 Cong., North-Holland Pub. Co., Amsterdam, 1969, vol. 2, pp. 867-871. 377

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Stability (and instability)

General Terms:
Performance

Keywords:
aggregation, hierarchy, instabilities, multiprogramming, networks of queues, paging, performance evaluation, saturation, system levels, thrashing