# ワーキングセットモデル ## 定義 ワーキングセットモデルは、あるプロセスのメモリ需要を、プロセス時間で直近 τ 秒間(ワーキングセットパラメータ)に参照されたページの集合 W(t, τ) として定式化する、プログラム挙動のモデルである。W(t, τ) に含まれるページ数をワーキングセットサイズ ω(t, τ) と呼び、これが主記憶管理におけるメモリ需要の指標として機能する。「プロセス」がプロセッサに対する需要の現れであるのに対し、「ワーキングセット」は同一の計算活動がメモリに対して持つ需要の現れであり、両者は表裏一体の関係にあるとされる。ワーキングセットは、大小関係として単調性・上に凸な飽和的増加(P1: サイズ)、直近過去が近い将来の良い予測子になるという性質(P2: 予測性)、τ を縮めるほど再参入率が増すという性質(P3: 再参入率)、および τ の変化に対する再参入率の感度(P4: τ感度)という4つの一般的性質を持つ。実装上は、各ページテーブルエントリに K 個の使用ビットを持たせ σ = τ/K 秒ごとにシフトするソフトウェアサンプリング方式によって W(t, Kσ) を近似検出できる。(Source: [[@1968__CACM__The Working Set Model for Program Behavior]]) ## 横断的知見 (このセクションは複数ソースの突き合わせで得られる知見を蓄積する。現時点では本概念に触れたソースが1件のため、蓄積を今後の ingest に委ねる。) ## 未解決の問い - ワーキングセットが重なり合う(ページ共有)プロセス群を、どのようなスケジューリング規則で時間的に近接させれば再ロードコストを最小化できるか。原論文は「調査中」としたまま具体案を示していない。 - 現代のLRU近似アルゴリズム(Linuxのactive/inactiveリストによるクロック的手法など、[[仮想メモリとページング]] や [[Linuxメモリ回収]] が扱う仕組み)は、ワーキングセットモデルのどの性質(P1〜P4)を暗黙に前提しているか、あるいは明示的に破っているか。 - マルチコア・NUMA環境([[NUMAメモリ配置]] 参照)において、ワーキングセットパラメータ τ の選定基準(traverse time T との比)は、メモリ階層が多段化した現代のシステムでどう再定式化されるべきか。 - コンテナ・cgroup環境でのメモリオーバーコミット判定([[仮想メモリとページング]] の未解決の問いと関連)は、個々のワーキングセットの合計とホスト全体の空き容量をどう突き合わせて判断しているか。 ## 関連 - [[@1968__CACM__The Working Set Model for Program Behavior]] — 本概念の原典(Denning, 1968)。 - [[仮想メモリとページング]] — デマンドページング・オーバーコミットなど、本概念が前提とする2階層メモリシステムの一般論。 - [[スラッシング]] — ワーキングセットモデルが対処しようとする、メモリ過剰コミットメント下の性能劣化現象。 - [[Peter J. Denning]] — 本概念の提案者。 ## 出典 - [[@1968__CACM__The Working Set Model for Program Behavior]]