> [!abstract] 概要(原文 Abstract の日本語訳) > 現代の計算機システムにおいて資源配分の一般的な扱いが存在しない、そのおそらく最も基本的な理由は、プログラムの挙動に関する適切なモデルが欠けていることである。本論文では新しいモデルである「ワーキングセットモデル」を展開する。あるプロセスに結び付くページのワーキングセットは、そのプロセスが最も直近に使用したページの集合として定義され、ページ化されたメモリの動的管理にとって不可欠な知識を与える。「プロセス」と「ワーキングセット」は、同一の進行中の計算活動が持つ現れ方であることが示され、続いて「プロセッサ需要」と「メモリ需要」が定義され、資源配分は需要を利用可能な設備に対して均衡させる問題として定式化される。 ## 論文情報 - タイトル: The Working Set Model for Program Behavior - 著者: Peter J. Denning(Massachusetts Institute of Technology, Cambridge, Massachusetts) - 媒体: Communications of the ACM, Volume 11, Number 5(1968年5月), pp. 323–333 - 初出: ACM Symposium on Operating System Principles にて発表(Gatlinburg, Tenn., 1967年10月1日〜4日)、1967年11月に改稿 - 助成: Project MAC(M.I.T.、Advanced Research Projects Agency, Department of Defense、Office of Naval Research Contract Nonr-4102(01) による一部支援) - DOI: [10.1145/363095.363141](https://doi.org/10.1145/363095.363141) ## 概要 論文は、計算機ユーティリティ(computer utility)のようなマルチプログラミング環境で、プロセッサとメモリという2種の資源に対する需要を統一的に扱う枠組みを提示する。プログラマやコンパイラからの事前情報に頼らず、OSが観測だけからページ利用状況を判定できるようにするため、プロセスが直近 τ 秒間に参照したページ集合を「ワーキングセット」と定義し、これをメモリ管理・プロセススケジューリング・資源配分の3つに横断して用いる統一理論を構築する。 ## 問題設定 - **入力**: 各プロセスのページ参照系列(demand paging を行う2階層メモリシステム上での実行)。 - **前提とする計算機システム**: 各プロセスは専用のセグメント化された名前空間を持ち、各セグメントはページ単位(固定長)でページ化主記憶(main memory)にマップされる。主記憶に無いデータはすべて容量無限の補助記憶(auxiliary memory)にあるとみなし、両者間の転送に要する時間を traverse time T と呼ぶ(§2「Background」、Figure 1)。プロセスは running・ready・blocked の3状態を持つ。 - **課題**: プログラマにもコンパイラにも、資源要求に関する信頼できる事前情報(advice)を期待できない。3つの理由が挙げられる——(1) プログラムはモジュール構成であり他モジュールの資源要求は不明ないしデータ依存で決定不能、(2) 「助言」の形式や利用法が不明瞭でオーバーヘッドが利点を相殺しうる、(3) 個々のユーザに最適化した助言はコミュニティ全体へのサービスを損ないうる。コンパイラについても、モジュール構成のため実行時までどのモジュールが含まれるか決まらないこと、予測機構の追加がコンパイル速度を落とすことから、事前情報の取得は不適当とされる。 - **出力**: OSが現在の観測データのみから下す、ページ配置(page-turning)・プロセススケジューリング・資源配分の決定。 ## 提案手法 ### アーキテクチャ: ワーキングセットの定義 プロセスのワーキングセット W(t, τ) を、プロセス時間区間 (t − τ, t) の間に参照された情報(ページ)の集合と定義する(Figure 2)。τ を**ワーキングセットパラメータ**と呼ぶ。ワーキングセットサイズ ω(t, τ) は W(t, τ) に含まれるページ数である。 **Figure 1: 2階層メモリシステム** ![[_attachments/denning1968-working-set/fig01-two-level-memory.png]] (Fig. 1. 複数のプロセッサ P が主記憶(MAIN)に接続され、主記憶と補助記憶(AUXILIARY)の間を traverse time T をかけてページトラフィックが行き来する構成を示す。Source: 本論文 Figure 1。) **Figure 2: W(t, τ) の定義** ![[_attachments/denning1968-working-set/fig02-definition-wt-tau.png]] (Fig. 2. プロセス時間軸上で、時刻 t から遡って τ 秒の区間(斜線部)に参照されたページの集合が W(t, τ) を構成することを示す模式図。Source: 本論文 Figure 2。) ### ワーキングセットの4つの性質(P1〜P4) - **P1(サイズ)**: ω(t, 0) = 0 であり、ω(t, τ) は τ の増加関数で上に凸(concave downward)である。式 (3)〜(5) から統計的定常性の下で ω(t, 2τ) ≦ 2ω(t, τ) が成り立つ。挙動は Figure 3 の飽和曲線で示される。 - **P2(予測性)**: 直近の参照挙動は近い将来の参照挙動の良い予測子になる。時間差 α が τ より十分小さいとき W(t, τ) は W(t + α, τ) の良い予測子だが、α が τ に比べ十分大きいと予測力を失う(式 (6)〜(7))。 - **P3(再参入率)**: τ を小さくするほど ω(t, τ) は減少し、有用なページが W(t, τ) から漏れる確率が増して再参入率が上がる。ページの再参照間隔 x の分布 F_x(α) から、プロセス時間での再参入率 λ(τ)(式 (10))、実時間での再参入率 φ(τ)(式 (11))、およびメモリバランス時の総復帰トラフィック率 Φ(τ)(式 (13))を導出する。 - **P4(τ感度)**: τ の減少に対して再参入率 λ(τ) がどれだけ敏感かを表す感度関数 σ(τ) = −dλ(τ)/dτ を定義する(式 (14))。σ(τ) ≧ 0 であり、τ を小さくすると再参入率は決して減少しない。 **Figure 3: ω(t, τ) の挙動** ![[_attachments/denning1968-working-set/fig03-behavior-omega.png]] (Fig. 3. τ の増加に対してワーキングセットサイズ ω(t, τ) が単調増加かつ上に凸で飽和していく様子を示す平滑化曲線。Source: 本論文 Figure 3。) ### τ の選び方とレジデンシ τ の値は、小さすぎれば有用なページの追い出しによる復帰トラフィックの増大を招き、大きすぎればメモリの浪費を招くというトレードオフを持つ。論文は τ を traverse time T と同程度の値にすることを推奨する。そのために「レジデンシ(residency)」——ページが主記憶に存在しうる時間の割合——を定義し、ページの再参照間隔 x に応じて3つの場合分けを行う(Figure 4)。 - x ≦ τ のとき: レジデンシは100%。 - τ < x ≦ (τ + T) のとき: レジデンシは τ/(τ + 2T)。ページは τ 秒間主記憶に残った後補助記憶へ送られ、往復2traverse time後に(τ + 2T)秒後に再出現する。 - x > (τ + T) のとき: レジデンシは τ/(x + T)。 100%から τ/(τ + 2T) への落差を50%以内に抑えたい場合、τ ≈ 2T を選ぶべきだとされる。 **Figure 4: レジデンシ** ![[_attachments/denning1968-working-set/fig04-residency.png]] (Fig. 4. 再参照間隔 x に対するページのレジデンシ(主記憶に存在する時間割合)の階段状の変化を示す。x = τ で100%からτ/(τ+2T)へ急落し、x = τ+T以降はτ/(x+T)へなだらかに減衰する。Source: 本論文 Figure 4。) ### 実装上の工夫: W(t, Kσ) の検出とスケジューリング ハードウェアでτ秒のタイマーを各ページに持たせる方式(Appendixで詳述)は既存システムへの追加が非現実的なため、論文はソフトウェアによるサンプリング方式を提案する。各ページテーブルエントリに「in-core」ビット M と K個の使用ビット u₀, u₁, …, u_K を持たせ、σ = τ/K のサンプリング間隔ごとにビット列をシフトする(式 (15))。使用ビットの論理和 U = u₀ + u₁ + … + u_K が1であれば、そのページは直近K回のサンプリング区間内に参照されたことを意味し、W(t, Kσ) を構成する(式 (16))。U = 0 かつ M = 1 のページは主記憶から除去してよい。 **Figure 5: W(t, Kσ) 検出のためのページテーブルエントリ** ![[_attachments/denning1968-working-set/fig05-page-table-entries.png]] (Fig. 5. 「in-core」ビット M・使用ビット u₀…u_K・ページへのポインタを持つページテーブルエントリの構造(上)と、サンプリング区間終了時に使用ビット列をシフトする操作(下)を示す。Source: 本論文 Figure 5。) スケジューリング側では、インタラクティブでモジュール構成のプログラム(Figure 6: ユーザ→インタフェース手続きA→手続き群B₁…Bₙ→データDという構成)ではブロック(たとえばコンソールとのインタラクション)のたびにワーキングセットが急変しうることを論拠に、先読み(look-ahead)を退ける。プロセスがブロックする(ページフォールト以外の理由で)ことは、W(t, τ) の差し迫った変化の強い兆候になりうる。 **Figure 6: プログラムの構成** ![[_attachments/denning1968-working-set/fig06-program-organization.png]] (Fig. 6. ユーザがインタフェース手続き A を介して複数の手続き B₁〜Bₙ を呼び出し、共通のデータ D を操作する、インタラクティブなモジュール構成プログラムの模式図。Source: 本論文 Figure 6。) Figure 7 は、これらの要件(メモリ管理とプロセススケジューリングの一体運用、効率性、ワーキングセットサイズと使用プロセッサ時間の計測)を満たす実装を示す。ready list・running list(循環キュー)・blocked list の3リストをプロセス識別子が巡回し、running list に常駐する特別なプロセス「checker」がコア管理機能(ページテーブルのサンプリングとページ除去)を担う。プロセス i にはクォンタム qᵢ が割り当てられ、σ 秒のバーストを繰り返し受け取ってブロックまたはクォンタム超過まで実行される。プロセス i の時間使用量 tᵢ(ページフォールトを除く)はブロック解除ごとに 0 にリセットされる。 **Figure 7: スケジューリングの実装** ![[_attachments/denning1968-working-set/fig07-scheduling-implementation.png]] (Fig. 7. ready list・running list・blocked list を巡るプロセス識別子の経路(実線矢印)と、時間使用変数 tᵢ に対する操作(破線)を示すスケジューリング実装の状態遷移図。checker が running list 中の各プロセスのページテーブルをサンプリングして不要ページを除去する。Source: 本論文 Figure 7。) running list の長さが l、プロセッサ数が N のとき、ページテーブルのサンプリングは σ 秒ごとではなく約 lσ/N 秒ごとに行われる点に注意が必要だとされる。 ### 共有(Sharing)への対応 ページが共有される場合、複数プロセスのワーキングセットが重なりうる。Arden の提案するプログラム構造に従えば、あるページが少なくとも1つのワーキングセットに含まれていれば使用ビットがONのままとなり除去されないため、Figure 7 の枠組みを変更せずに共有を扱える。ただし checker が同一サンプリング内で同じページテーブルを重複して調べないようにする必要がある。ワーキングセットが重なるプロセス同士をどう時間的に近接させて再ロードを避けるか、また共有時のメモリ課金をどう配分するかは未解決の問題として提示される。 ## 新規性 先行研究であるページ置換方式は、Random選択・FIFO(先入れ先出し)選択・LRU(最近最も使われていない)選択・ATLASのループ検出方式の4種が主に比較される(§2「Previous Work」)。 - **Random選択**: 実装は単純だが有用なページを誤って除去しやすく、ページトラフィックが高い。 - **FIFO選択**: 主記憶のページを循環リストで管理し、最も古く読み込まれたページを除去する。プログラムが逐次的な命令フェッチパターンに従うという仮定に立つが、モジュール構成のプログラムでは制御の流れがページを線形につながず、この仮定が崩れる。Fine ほか [10] と Varian & Coffman [11] の実験がこれを支持する。加えて、マルチプログラム環境でコア需要が過大になると、リストの1巡が速すぎてまだ必要なページまで削除され、それが更なるページフォールトの連鎖を生む「自己増強的な危機」を招きうる。 - **LRU選択**: プロセスが1つだけの単純なケースでは合理的だが、多数のプロセスが主記憶を奪い合う場合には過負荷になりやすい。 - **ATLASループ検出方式**: ループ挙動を検出してページトラフィックを最小化しようとするが、ループ的なプログラムにしか有効でなく、ランダムな参照パターンには効果が薄く実装コストも高い。Belady [13] の数学的比較によれば、理想的なアルゴリズムはRandomやFIFOの単純さと、過去の参照履歴のわずかな蓄積とを両立すべきであり、ATLASのように過去の履歴を蓄積しすぎることには弊害があるとされる。 ワーキングセットモデルは、これら4方式の中で最も低いページトラフィックを実現する方式として位置づけられる(§7「Conclusions」)。実装コストは Random や FIFO より高いが、正確さと汎用的な資源配分戦略との整合性がその追加コストを上回るとされる。また、論文は「プロセス」と「ワーキングセット」を同一の計算活動の2つの現れ(プロセッサ需要とメモリ需要)として統一的に扱う点で、従来のメモリ管理研究とスケジューリング研究が別々に進んできた状況に橋を架けている(§1「Introduction」)。 ## 資源配分: プロセッサ需要とメモリ需要のバランス 論文終盤(§6「Resource Allocation: A Balancing Problem」)では、ワーキングセットモデルを土台に資源配分を定式化する。計算 i のメモリ需要は式 (17) mᵢ = min(wᵢ/M, 1) で定義され、M は主記憶の総ページ数、wᵢ = ωᵢ(t, τ) はスケジューラが維持するワーキングセットカウントである。 プロセッサ需要はより定義が難しい。プロセスが「インタラクト」する(名前空間外の何か、たとえばユーザや他プロセスと通信する)までに使用する処理時間 q を確率変数とし、その確率密度関数 f_q(z) を式 (18) のような超指数分布(hyper-exponential)としてモデル化する(Figure 8)。既に γ 秒(プロセス時間)使用済みという条件のもとでの条件付き期待値 Q(γ) を式 (19)〜(20) で導出し(Figure 9)、プロセッサ需要 pᵢ を式 (21) pᵢ = Q(tᵢ)/(NA) として定義する。ここで N はプロセッサ数、A は許容できる最大応答時間に相当する標準区間である。 **Figure 8: q の確率密度関数** ![[_attachments/denning1968-working-set/fig08-density-function-q.png]] (Fig. 8. インタラクション間の処理時間 q の確率密度関数 f_q(x)。小さいqに確率が集中しつつ長い指数的なテールを持つ超指数分布の形状を示す。Source: 本論文 Figure 8。) **Figure 9: q の条件付き期待値関数** ![[_attachments/denning1968-working-set/fig09-conditional-expectation.png]] (Fig. 9. 直近のインタラクションからγ秒経過した条件下での、次のインタラクションまでの期待処理時間 Q(γ)。Q(0)から単調に増加しQ(∞)に漸近する。Source: 本論文 Figure 9。) 計算 i の(システム)需要は式 (22) Dᵢ = (pᵢ, mᵢ) の対として定義され、システムは式 (23)(24) を同時に満たすとき「バランス」しているとされる——running list 中の全プロセスのプロセッサ需要の総和が定数 α、メモリ需要の総和が定数 β に等しいこと。「バランスポリシー」は式 (26) minimize(S − (α, β)) を目的関数とし、不均衡が生じたとき、均衡回復に最も寄与するジョブから ready list を離脱させる。論文は、メモリの過剰コミットメントに対する感度がプロセッサのそれより大きいため、まずメモリバランスを優先し、次にプロセッサバランスを図るべきだと述べる(§6 の考察(1))。 ## 考察 - 過剰コミットメントの下で多数のワーキングセットが主記憶を奪い合い、互いのページを追い出し合う現象を、論文は「スラッシング(thrashing)」と呼ぶ。この語は本論文で導入された用語であり、ページ待ち状態に滞留するプログラムの急増と補助記憶チャネルの輻輳を招くと説明される(§6 の考察(1))。 - バランス基準は設備利用率に関する基準であり、設備利用率とユーザへの良好な応答性は必ずしも両立しないと明言される。式 (26) のポリシーはそのままでは需要の小さいジョブを優先し需要の大きいジョブを冷遇する傾向を持つが、Figure 7 の仕組みとバランス定数 α・β の調整により、ほぼバランスを保ちつつ良好なサービスを両立できるとされる(§6 の考察(2))。 - バランスのような直観的に単純な戦略であっても、プロセスとワーキングセットの相互作用、バランスと良好なサービスの相互作用は未だ十分に理解されていないと留保している(§6 の考察(3))。 - Oppenheimer と Weizer [17] が RCA Spectra 70/46 タイムシェアリングOSのシミュレーションで、ワーキングセットおよびメモリバランスに関連する概念を用い、システム性能が顕著に改善したという証拠を報告していることに論文は言及している(§7「Conclusions」)。 ## 強み・弱点/課題 - **強み**: プロセスとワーキングセットを同一の計算活動の2つの現れとして統一的に捉えることで、それまで独立に発展してきたメモリ管理研究とプロセススケジューリング研究に橋を架け、「プロセッサ需要」「メモリ需要」「システム需要」という共通言語で資源配分を定式化した。ソフトウェアのみで実装可能なサンプリング方式(式 (15)(16))を示し、専用ハードウェアなしでもワーキングセットを近似的に検出できる道を示した。 - **弱点/課題**: 論文自身が明言する未解決点として、(1) ワーキングセットが重なる際のプロセス間の時間的な近接配置とメモリ課金のあり方は「調査中」のまま残されている(§5「Sharing」)、(2) バランスポリシー(式 (26))が需要の小さいジョブを優先し大きいジョブを冷遇する傾向をどこまで緩和できるかは Figure 7 の枠組みとバランス定数の調整に依存し、詳細な解法は示されていない(§6 の考察(2))、(3) プロセッサ需要のモデル化(式 (18)〜(21))は特定の確率分布形(超指数分布)を仮定しており、その妥当性の実証は別文献([16] Fife)に依存する。ハードウェア実装(Appendix)は「既存システムへの追加は非現実的」と論文自身が認めており、当時の実用上の主眼はソフトウェアサンプリング方式に置かれている。 ## 参考: Appendix(ハードウェア実装の概要) 論文末尾の Appendix は、各主記憶ページに π(ページテーブルエントリへのポインタ)・t(τを測るタイマー)・A(アラームビット)の3フィールドを持つ「ページレジスタ」を関連付けるハードウェア機構を提案する(Figure A)。ページ参照のたびに t を τ にリセットして計時を開始し、t が0まで下がると A を1にセットして除去候補とする。フレッシュなページが必要になったとき、追加のメモリハードウェアが A = 1 のページを走査して補助記憶へ直接ディスパッチすることで、スーパーバイザを介さず「メモリが自身を管理する」非同期な仕組みを実現するとされる。ただし前述のとおり、この方式は既存システムへの追加が実際的でないという理由から、論文の主眼はソフトウェアサンプリング方式(式 (15)(16))に置かれている。 **Figure A: メモリ管理ハードウェア** ![[_attachments/denning1968-working-set/figA-memory-management-hardware.png]] (Fig. A. 各ページに π・t・A の3フィールドを持つページレジスタを対応付け、t-registerから供給される値τでタイマーtを計時するハードウェア構成。Source: 本論文 Figure A。)