概念・定理図鑑 · 基礎から応用へ

ワーキングセット:最近使うページを数える

確保した容量と最近参照したページを分け、時間窓と負荷の変化からメモリ不足を考える。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 容量より参照の履歴を見る
  2. 参照列から集合を作る
  3. 保持できないと再取得が増える
  4. RSSと同じ数とは限らない
  5. 窓をずらして変化を読む
  6. 配置の変更を小さく検証する
  7. この記事をロゲイアに質問する理解を確かめる

容量より参照の履歴を見る

ワーキングセットは、ある観測窓の中でプロセスが参照したページの集合です。仮想領域を大きく確保しても、その一部しか触らなければ、最近必要になったページは小さくなります。逆に、少量ずつでも全域を繰り返し読む処理では、広い範囲を保持した方が再取得を減らせます。窓を参照回数で定めるか時間で定めるかを先に決めないと、二つの値を比較できません。

例えば、写真編集で画像を開く段階と、フィルターを繰り返し適用する段階では、最近使うページの範囲が変わります。最初の数秒だけ測った値を、その後の編集作業全体の必要量と考えてはいけません。測定を始める位置と終える位置を明示すると、処理の段階による変化と、窓の定義による違いを切り分けられます。プロセスが停止していた時間を含む壁時計の窓か、実際に動いた間の参照列の窓かも区別します。

参照列から集合を作る

ページ参照列をA、B、A、C、D、Aとし、直近4参照を窓とします。最後の窓はA、C、D、Aなので、集合はA、C、Dの3ページです。Bは過去に使っていますが、この窓には入りません。ページサイズを4KiBと仮定すれば、この集合のページ容量は12KiBです。窓を6参照へ伸ばすとBも入り16KiBになります。これは実行時間の測定値ではなく、定義を確かめるための計算例です。

この例では、同じページを何度参照しても集合の要素は増えません。Aを三回読んだことと、A、B、Cを一回ずつ読んだことは、参照回数が同じでも必要なページの種類数が違います。ただし集合は順序を保存しないので、ページを追い出す方針までこの数だけで決められるわけではありません。ページ番号の列を残し、窓を一つずつずらして再計算すると、集合の増減を手で確かめられます。

保持できないと再取得が増える

複数プロセスの必要なページが物理メモリに収まらないと、追い出したページをすぐ再び必要とし、回収と再取得が増える場合があります。これがスラッシングを考える入口です。ただし、ファイルを一方向に一度だけ読む処理では、通過済みのページを保持し続ける価値は低いままです。同じ参照ページ数でも、再利用までの距離が違えば適した保持量は変わります。集合の大きさに加え、アクセスの順序も見ます。

保持量を増やす判断では、一つの処理だけでなく同時実行する処理の合計も見ます。各処理の局所的な最適化が、他の処理からページを奪う場合があるためです。共有ページは単純に足すと重複して数えるので、物理メモリ全体の必要量へ変換する際には注意が要ります。バッチ処理の同時実行数を減らして一つずつ終える方が、全体の完了が早くなる条件もあります。

RSSと同じ数とは限らない

RSSはその時点で常駐するページ量であり、直近に使われた集合そのものではありません。共有ページを複数プロセスで数える方法、ページキャッシュ、匿名ページ、巨大ページの扱いでも解釈が変わります。処理の開始直後と定常状態を分け、同じ窓と負荷で、ページフォルトや回収の変化を一緒に観察します。ワーキングセットを小さくする工夫として、処理順の変更やデータの分割がありますが、追加のI/Oや計算との釣り合いを確かめます。

Linuxの/procから得た常駐量やフォルト数は、ワーキングセットの定義どおりの直接測定値ではありません。例えばminor faultが増えても、ディスクから読み直したとは限りません。匿名領域の初回割り当てやコピーオンライトも候補です。観測値の単位と増分の期間をそろえ、まず何を測った数なのかを説明します。概念上のページ集合と、OSが公開する代理指標を分けることが、誤った容量見積もりを防ぎます。

窓をずらして変化を読む

参照列A、B、A、C、D、Aで、窓を直近4参照に固定します。4回目ではA、B、C、5回目ではB、A、C、D、6回目ではA、C、Dです。集合の大きさは3、4、3と変わります。ここで「容量が減った」と説明するのは不正確です。物理メモリを変更したのではなく、窓の中で使ったページの種類が変わっただけです。これに対し、窓を4から6へ変更する比較は、同じ時点でも定義を変更する操作です。二つの変化を混ぜないようにします。さらに、別々の仮想ページが同じ物理ページを共有する場合、仮想ページ数と実際の物理容量の対応は単純ではありません。ページの単位を固定した教材上の計算と、実機の共有・巨大ページを含む計数を区別して報告します。

配置の変更を小さく検証する

大きな表を列ごとに走査する処理を、一定の行数ごとに区切って全列を処理する構成へ変えるとします。狙いは、次の列へ進むまでに再利用したいページが窓から消えにくくすることです。ただし区切りを小さくしすぎると、ループ制御や入出力の回数が増える場合があります。同じ結果が得られることを先に確認し、入力サイズ、区切りの大きさ、同時実行数を記録して比較します。一回だけ速くなったことを一般的な最適サイズの証明にはしません。共有ページやページキャッシュも他の処理の影響を受けるため、ウォームアップ後と開始直後を分けて観察します。この方法なら、単に「メモリを増やす」という対処から、再利用の距離を変える設計へ議論を進められます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 16

サーバーの中で起きていること · STEP 6

AI基盤へ進む · STEP 6

学習コースから次を選ぶ