The working set model for program behavior

ABSTRACT

Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model is developed, the “working set model”, which enables us to decide which information is in use by a running program and which is not. Such knowledge is vital for dynamic management of paged memories. The working set of pages associated with a process, defined to be the collection of its most recently used pages, is a useful allocation concept. A proposal for an easy-to-implement allocation policy is set forth; this policy is unique, inasmuch as it blends into one decision function the heretofore independent activities of process-scheduling and memory-management.

REFERENCES

• 1: C. V. Ramamoorthy, The analytic design of a dynamic look ahead and program segmenting system for multiprogrammed computers, Proceedings of the 1966 21st national conference, p.229-239, January 1966 [doi>10.1145/800256.810702]
• 2: R.M. Fano and E.E.David. "On the Social Implications of Accessible Computing." AFIPS Conf. Proc. 27 (Nov 1965), 243-247.
• 3: L.L. Selwyn. "The Information Utility." Industrial Management Review 7, 2, Spring 1966.
• 4: D. Parkhill. The Challenge of the Computer Utility. Addison-Wesley, 1966.
• 5: Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
• 6: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• 7: B. W. Arden , B. A. Galler , T. C. O'Brien , F. H. Westervelt, Program and Addressing Structure in a Time-Sharing Environment, Journal of the ACM (JACM), v.13 n.1, p.1-16, Jan. 1966 [doi>10.1145/321312.321313]
• 8: J. H. Saltzer, TRAFFIC CONTROL IN A MULTIPLEXED COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1966
• 9: 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]
• 10: T. Kilburn, et al. "One-level Storage System." IRE Trans. on Elec. Comp. EC-11, 2 (April 1962).
• 11: L.A. Belady. "A Study of Replacement Algorithms for a Virtual Storage Computer." IBM Systems Journal 5, 2 (1966), 78-101.
• 12: Progress Report III, M.I.T. Project MAC (1965-1966), 63-66.
• 13: P.J. Denning. "Memory Allocation in Multiprogrammed Computers." M.I.T. Project MAC Computation Structures Group Memo 24, March 1966.
• 14: J. B. Dennis, PROGRAM STRUCTURE IN A MULTI-ACCESS COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1964
• 15: D.W. Fife. "An Optimization Model for Time-Sharing." AFIPS Conf. Proc. 28 (April 1966), 97-104.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Software psychology

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Pricing and resource allocation

General Terms:
Management, Theory