The Working Set Model for Program Behavior

Peter J. Denning, 1968, Communications of the ACM

About this paperTiếng Việt中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

日本語
English

プログラムの振舞いに関するワーキングセットモデル

Peter J. Denning

マサチューセッツ工科大学、マサチューセッツ州ケンブリッジ

現代のコンピューターシステムにおいてリソース割当てに関する一般的な取り扱いが存在しない最も基本的な理由は、おそらくプログラムの振舞いに関する適切なモデルがないことである。本論文では、新しいモデルである「ワーキングセットモデル」を展開する。プロセスに関連付けられたページのワーキングセットは、最近使用されたページの集合として定義され、ページングメモリの動的管理に不可欠な知識を提供する。「プロセス」と「ワーキングセット」は、同一の継続的な計算活動の現れであることを示す。次に「プロセッサ要求」と「メモリ要求」を定義し、リソース割当てを、利用可能な装置に対して要求を均衡させる問題として定式化する。

キーワードおよび句：一般的なオペレーティングシステム概念、マルチプロセッシング、マルチプログラミング、オペレーティングシステム、プログラムの振舞い、プログラムモデル、リソース割当て、スケジューリング、記憶域割当て

CR分類：4.30、4.32

  1. はじめに

リソース割当ては難しい問題である。近年、プロセススケジューリングと主メモリ管理について多くの議論がなされているが、技術の開発はこれら二つの方向に沿って独立に進められてきた。統一的なアプローチが必要であることは誰も否定しないであろう。ここでは、統一的なアプローチを開発することが可能であることを示す。すべての実行中のプログラムが、特にプロセッサとメモリを含むすべてのシステムリソースに対して同時に要求を生じさせるという観察から出発し、最終的に「システム要求」を定義する。割当て問題は、利用可能なリソースに対して要求を均衡させることから成る。

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, the "working set model," is developed. The working set of pages associated with a process, defined to be the collection of its most recently used pages, provides knowledge vital to the dynamic management of paged memories. "Process" and "working set" are shown to be manifestations of the same ongoing computational activity; then "processor demand" and "memory demand" are defined; and resource allocation is formulated as the problem of balancing demands against available equipment.

KEY WORDS AND PHRASES: general operating system concepts, multiprocessing, multiprogramming, operating systems, program behavior, program models, resource allocation, scheduling, storage allocation CR CATEGORIES: 4.30, 4.32

This section is missing here.

1 Introduction

This section is missing here.

2 Background

This section is missing here.

3 Working Set Model

This section is missing here.

4 Scheduling

This section is missing here.

5 Sharing

This section is missing here.

6 Resource Allocation: A Balancing Problem

This section is missing here.

7 Conclusions

References

  1. Dennis, J. B., and Van Horn, E. C. Programming semantics for multiprogrammed computations. Comm. ACM 9 (Mar. 1966), 143–155.
  2. Ramamoorthy, C. V. The analytic design of a dynamic look ahead and program segmenting system for multiprogrammed computers. Proc. ACM 21st Nat. Conf. 1966. Thompson Book Co., Washington, D.C., pp. 229–239.
  3. Fano, R. M., and David, E. E. On the social implications of accessible computing. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Part 2. Thompson Book Co., Washington, D.C., pp. 243–247.
  4. Selwyn, L. L. The information utility. Indust. Man. Rev. 7, 2 (spring, 1966).
  5. Parkhill, D. The Challenge of the Computer Utility. Addison-Wesley, Reading, Mass., 1966.
  6. Dennis, J. B. Segmentation and the design of multiprogrammed computer systems. J. ACM 12, 4 (Oct. 1965), 589–602.
  7. Arden, B. W., et al. Program and address structure in a time-sharing environment. J. ACM 13, 1 (Jan. 1966), 1–16.
  8. Saltzer, J. H. Traffic control in a multiplexed computer system. M.I.T. Project MAC Tech. Rep. MAC-TR-30, M.I.T., Cambridge, Mass., July 1966.
  9. Dennis, J. B. Program structure in a multi-access computer. Project MAC Tech. Rep. MAC-TR-11, M.I.T., Cambridge, Mass.
  10. Fine, G. H., McIsaac, P. V., and Jackson, C. W. Dynamic program behavior under paging. Proc. ACM 21st Nat. Conf. 1966. Thompson Book Co., Washington, D.C., pp. 223–228.
  11. Varian, L., and Coffman, E. An empirical study of the behavior of programs in a paging environment. Proc. ACM Symp. on Operating Principles, Gatlinburg, Tenn., Oct. 1967.
  12. Kilburn, T., et al. One-level storage system. IRE Trans. EC-11, 2 (Apr. 1962).
  13. Belady, L. A. A study of replacement algorithms for a virtual storage computer. IBM Systems J. 5, 2 (1966), 78–101.
  14. Progress Report III, M.I.T. Project MAC, 1965–66, pp. 63–66.
  15. Denning, P. J. Memory allocation in multiprogrammed computers. Project MAC Computation Structures Group Memo 24, M.I.T., Cambridge, Mass., Mar. 1966.
  16. Fife, D. W. An optimization model for time-sharing. Proc. AFIPS 1966 Spring Joint Comput. Conf., Vol. 28. Spartan Books, New York, pp. 97–104.
  17. Oppenheimer, G., and Weizer, N. Resource management for a medium scale time-sharing operating system. Comm. ACM 11, 5 (May 1968), 313–322.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.