キーワードのまとめです。
6. 仮想記憶
フェッチの方式
- どのページをいつ主記憶へ移すかを決めるための方式
配置の方式
- ページを主記憶のどこへ置くかを決めるための方式
置き換えの方式
- 空きのページフレームを作るために、主記憶からどのページを退避させるかを決めるための方式
デマンドページング
- 実際にページが参照された時にそのページを主記憶に取り入れる方式
- 仮想記憶実現の最も一般的な方法
プリページング
- ページを前もって主記憶に入れる方式
デマンドプリフェッチング
- デマンドページング方式とプリフェッチング方式の組合わせ
- ページフォールト時に要求されたページ以外に将来使用が予測されるページも主記憶に入れる
参照間隔
- ページが次に参照されるまでの時間間隔
- 退避すべきページを決めるために使う
LRU
- Least Recently Used
- 最も長く参照されていないページを退避ページとして選ぶ
- 時間局所性を有しているプログラムに適している
FIFO
- First-In-First-Out
- 主記憶内に最も長くいるページを退避ページとして選ぶ
- 空間局所性を有しているプログラムに適している
LFU
- Least Frequently Used
- 参照頻度が最小のページを退避ページとして選ぶ
OPT
- 将来もっとも遅くにしか参照されないページを退避ページとして選ぶ
ワーキングセット
- 過去T秒間（T単位時間）に参照されたページの集合
- ワーキングセットの概念は、もともとはプログラムを効率よく実行するために主記憶内に存在すべきページの集合の意味
ウィンドウタイム
- ワーキングセットのページ数を調整するために現在時刻から遡る時間T
スラッシング
- プログラムに割当てるページフレームの数を動的に変更するシステムにおいて生じ、主記憶にプログラムを入れ過ぎたためにシステムの性能が突如低下する現象
- 極端にページの出し入れが行われる状態で、プロセスはページの出し入れ以外何もしない状態になる
局所性
時間的局所性
- 時間が推移した時に、ある少数のページにアクセスが集中するというプログラムの特性
空間的局所性
- 主記憶上の隣接した場所にアクセスが集中するプログラムの特性
局所集合
- 集中して参照されるページの集合
フェーズ化現象
- アクセスが集中するページは必ずしも一定ではなく、ある時間特定の少数のページを参照した後は、急激に別のページの組みへと切り替わることが多い
ローカル方式
- ページフォールトを生じさせたプログラムのページのみを退避ページの対象とする
グローバル方式
- 主記憶のすべてのページを退避ページの対象とする
ページスティーリング
- 他のプロセスからページフレームを取り上げて割当てる
スタックアルゴリズム
-
すべてのページ参照列$w$に対し、次を満たすアルゴリズム$A$
$S(A, m, w) ⊆ S(A, m+1, w)$
- $w$はページに対する参照要求が出された時刻順に順序づけられたページ番号列
- $S(A, m, w)$は容量mのページの主記憶において、$w$に対してデマンドページングによりページ置き換えアルゴリズム$A$が適用された後の、主記憶に存在するページ集合
-
どのようなプログラムに対しても、主記憶の容量が増加したときページフォルトの数は増加しないと保証されている
-
LRU、LFU、OPT、LIFOはスタックアルゴリズム
-
FIFO、RANDOMはスタックアルゴリズムでない
プログラム再編成
- 互いに密に参照されるブロック（プロシージャ、関数、データ構造、配列など）を同一のページにまとめ、プログラムをロードし直す
- プログラムの論理的なブロックの大きさに比べてページがかなり大きい場合に効果を発揮する
- 時間的局所性より空間的局所性を強く有するプログラムではほとんど効果がない
ライフタイム
- ページフォールトの間の時間間隔（平均値）
ニーポイント
- 原点からの半直線でライフタイム曲線と交わるもののうち、最大の傾きを持つ半直線と曲線の交点
ニー基準
- ページングのコスト＝単位時間あたりのページフォールト数（$1/f$）×主記憶に割り当てられているページ数（$s$）を最小にする点（コスト性能比を最大にする点）