The Working Set Model for Program Behavior

Peter J. Denning, 1968, Communications of the ACM

About this paperEnglishTiếng Việt中文beside Englishbeside Tiếng Việtbeside 中文

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.

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

Peter J. Denning

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

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

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

CR分類：4.30、4.32

  1. はじめに

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

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.