An L=S criterion for optimal multiprogramming

ABSTRACT

Balancing interpagefault lifetime (L) against page swap time (S) has always been a performance criterion of great intuitive appeal. This paper shows that, under normal conditions, controlling the memory policy parameter to enforce the constraint L ≥ S, and allowing the multiprogramming load to rise as high as demand warrants without violating this constraint, will produce a load slightly higher than optimum. Equivalently, using the criterion L &equil; uS for some u slightly larger than 1 will approximate an optimal load. Using simulations, this criterion is compared with two others reported in the literature, namely the “knee criterion” (operate with L at the knee of the lifetime curve) and the 50% criterion (operate with the paging device at 50% utilization).The knee criterion produced optimal loads more often than the L&equil;S criterion, which in turn produced optimal loads more often than the 50% criterion. Since no practical implementation of the knee criterion is known, the L&equil;S criterion is the most attractive of the three.

REFERENCES

• 1: A. Brandwain , J. Buzen , E. Gelenbe , D. Potier, A model of performance for virtual memory systems, Proceedings of the 1974 ACM SIGMETRICS conference on Measurement and evaluation, p.9, January 1974
• 2: Belady, L. A. "Biased replacement algorithms for multiprogramming." IBM T. J. Watson Research Center Note NC697 (March 1967).
• 3: L. A. Belady , C. J. Kuehner, Dynamic space-sharing in computer systems, Communications of the ACM, v.12 n.5, p.282-288, May 1969 [doi>10.1145/362946.363002]
• 4: Brandwajn, A., Gelenbe, E., Lenfant, J., and Potier, D., "A model of program and system behavior in virtual memory." Technical Report, IRIA-Laboria, Rocquencourt, 78150 Le Chesnay, France (October 1973).
• 5: Badel, M., Gelenbe, E., Leroudier, J., and Potier, D., "Adaptive optimization of a time sharing system's performance," Proc. IEEE: Special Issue on Interactive Computer Systems (June 1975), 958-965.
• 6: Brandwajn, A., "A model of a time sharing virtual memory system solved using equivalence and decomposition methods," Acta Informatica 4 (1974), 11-47.
• 7: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 8: 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]
• 9: Corbato, F. J., Bagget, M. M., and Daley, R. C., "An experimental time sharing system," AFIPS Conf. Proc. 21 (1962 SJCC), 279-294. {In Programming Systems and Languages, S. Rosen, Ed., McGraw (1967).}
• 10: Chu, W. W., and Opderbeck, H., "The page fault frequency replacement algorithm," AFIPS Conf. Proc. 41 (1972 FJCC), 597-609.
• 11: Courtois, P. J., "On the near-complete-decomposability of networks of queues and of stochastic models of multiprogrammed computer systems," Sci. Rpt. CMU-CS-72-11, Carnegie-Mellon University, (Nov 1971).
• 12: P. J. Courtois, Decomposability, instabilities, and saturation in multiprogramming systems, Communications of the ACM, v.18 n.7, p.371-377, July 1975 [doi>10.1145/360881.360887]
• 13: 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]
• 14: Denning, P. J., "Thrashing: Its causes and prevention," AFIPS Conf. Proc. 33 (1968 FJCC), 915-922.
• 15: Denning, P. J., and Graham, G. S., "Multiprogrammed memory management," Proc. IEEE: Special Issue on Interactive Computer Systems (June 1975), 924-939.
• 16: 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
• 17: Leroudier, J., and Potier D., "New results on a model of virtual memory systems for performance evaluation," Technical Report, IRIA-Laboria, Rocquencourt, 78150 Le Chesnay, France (June 1975).
• 18: James B. Morris, Demand paging through utilization of working sets onr the MANIAC II, Communications of the ACM, v.15 n.10, p.867-872, Oct. 1972 [doi>10.1145/355604.361592]
• 19: Muntz, R. R., "Analytic modeling of interactive systems," Proc. IEEE 63, 6 (June 1975), 946-953.
• 20: Muntz, R. R. and Wong, J., "Asymptotic properties of closed queueing network models," Proc. 8th Princeton Conf. on Information Science and Systems, Dept. Elec. Engrg, Princeton U. (March 1974).
• 21: Barton G. Prieve, Using page residency to select the working set parameter, Communications of the ACM, v.16 n.10, p.619-620, Oct. 1973 [doi>10.1145/362375.362395]
• 22: Rodriguez-Rosell, J., and Dupuy, J. P., "The evaluation of a time sharing page demand system." AFIPS Conf. Proc. 40 (1972-SJCC), 759-765.
• 23: Juan Rodriguez-Rosell , Jean-Pierre Dupuy, The design, implementation, and evaluation of a working set dispatcher, Communications of the ACM, v.16 n.4, p.247-253, April 1973 [doi>10.1145/362003.362032]
• 24: Jerome H. Saltzer, A simple linear model of demand paging performance, Communications of the ACM, v.17 n.4, p.181-186, April 1974 [doi>10.1145/360924.360926]
• 25: Weizer, N., and Oppenheimer, G., "Virtual memory management in a paging environment," AFIPS Conf. Proc. 34 (1969 SJCC), 234ff.

INDEX TERMS

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

General Terms:
Performance