Dynamic space-sharing in computer systems

ABSTRACT

A formalization of relationships between space-sharing, program behavior, and processor efficiency in computer systems is presented. Concepts of value and cost of space allocation per task are defined and then value and cost are combined to develop a single parameter termed value per unit cost. The intent is to illustrate a possible analytic approach to the investigation of the problems of space-sharing and to demonstrate the method on sample problems.

REFERENCES

• 1: B. Randell , C. J. Kuehner, Dynamic storage allocation systems, Communications of the ACM, v.11 n.5, p.297-306, May 1968 [doi>10.1145/363095.363138]
• 2: E. F. Codd, Multiprogram scheduling: parts 1 and 2. introduction and theory, Communications of the ACM, v.3 n.6, p.347-350, June 1960 [doi>10.1145/367297.367317]
• 3: 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]
• 4: BELADY, L.A. A study of replacement algorithms for a virtual storage computer. IBM Syst. J. 5, 2 (1966), 78-101.
• 5: O'NEILL, R. W. Experience using a time-sharing multiprogramming system with dynamic address relocation hardware. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, Thompson Book Co., Washington D. C., pp. 611-621.
• 6: Gerald H. Fine , Calvin W. Jackson , Paul V. Mc Isaac, Dynamic program behavior under paging, Proceedings of the 1966 21st national conference, p.223-228, January 1966 [doi>10.1145/800256.810701]
• 7: L. C. Varian , E. G. Coffman, An empirical study of the behavior of programs in a paging environment, Proceedings of the first ACM symposium on Operating System Principles, p.16.1-16.13, January 1967 [doi>10.1145/800001.811682]
• 8: BELADY, L. A. Biased replacement algorithms for multiprogramming. Rep. NC 697, IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., Mar. 1967.
• 9: DENNING, P. Resource allocation in multiprocess computer systems. Doctoral Diss., MIT, June 1968.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

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

General Terms:
Design, Theory

Keywords:
allocation strategies, computer system design, demand-paging, memory allocation, memory management, multiprogramming, program behavior, replacement strategies, space-sharing, storage allocation, storage management, time-sharing