メモリ管理 4.3, 4.4 章さだ 4.3 仮想メモリ • プログラムが大きすぎてメモリに入りきらない問題 • オーバレイ：初期の解決策 – – – – プログラムを分割してメモリに格納するプログラムのスワップイン・アウトはOSがやってくれるプログラムの分割はプログラマの仕事 →大変！ • 仮想メモリ：現代の解決策 – プログラムコード，データ，スタックからなるプログラム全体が物理メモリサイズを越えてもOK 4.3.1 ページング • 仮想アドレス – – – – 例： MOVE REG, 1000 この1000というのが仮想アドレス仮想アドレスは仮想アドレス空間を持つ仮想アドレスはMMU (Memory Management Unit) で物理メモリアドレスへ変換される • 現代のMMUはたいていCPUに内蔵されています • ページ – 仮想アドレス空間を区切る単位 • ページフレーム – 物理メモリ内の対応する部分 • マッピング – 図4-10を参照 – 例：仮想アドレス8192→ページフレーム6 • 1ビットの存在/不在ビット – 例：仮想アドレス32780→ない！ – CPUはOSへトラップ（ページフォールト） • MMUの動作例 – 仮想アドレス8196 :0010,0000,000,0100 ページテーブル – ページテーブル2を参照オフセット 4.3.2 ページテーブル • 実現のための問題点 – ページテーブルサイズが巨大になってしまう – マッピングは高速でなければならない • 例 – 仮想アドレス32bit，ページサイズ4KBだと • 仮想ページ数＝ページテーブルエントリ数は100万 • しかもページテーブルはプロセスごとに必要 • マルチレベルページテーブル – 例えば，10,10,12 と区切る – この場合，最大ページテーブル数は1025になるが，実際はもっと少なくて済む • 図4-12の例だと4つ • ページテーブルエントリの構造 – キャッシング不可：主にデバイスレジスタ用 – 参照ビット：ページ置き換えアルゴリズムに使われる – 修正ビット：ページに書き込みがあるとセットされる，古いページフレームを読まない用 – 保護ビット：許可するアクセスの種類 – 存在・不在ビット – ページフレーム番号 4.3.3 TLB • ページングによる性能低下という問題 • 実は，多くのアクセスはある一部分のページ群へのアクセスである • TLB (Translation Lookaside Buffer) – ページテーブルの一部分を変換するハードウェア – TLBになかったらMMUにアクセス – MMUはTLBにないことを前提に処理できる 4.3.4 逆引きページテーブル • エントリ数が巨大 – 例：アドレス空間 4GB で，ページサイズが4096倍とだとエントリ数は100万→ページテーブル当たり4MB必要 • 逆引きページテーブル – ページフレーム1つにつき1つのエントリを持つ • 例：物理メモリ256MBでページサイズが4KBであればエントリ数は65536で良い – 問題 • 仮想アドレスから物理アドレスへの変換が大変 – 解決策 • TLBを用いる • ハッシュテーブルを用いて検索を高速化する 4.4 ページ置き換えアルゴリズム • ページフォールトが発生した場合に，どのページを追い出すか – 頻繁にアクセスするページを追い出すと性能が落ちる – あまり使わないページを追い出せば性能が上がる 4.4.1 最適ページ置き換えアルゴリズム • 最も理想的なアルゴリズム – 最大のラベルを持ったページを追い出す – 将来生じるページフォールトをなるべく遠い将来においやる • しかし，実現不可能 – OSは次に参照されるページを予測できないから 4.4.2 NRUアルゴリズム • ページテーブルの参照・修正ビットを用いる • 4つのカテゴリに分類 – – – – クラス０：参照も修正もされていないクラス１：参照されていないが，修正されているクラス２：参照されたが，修正されていないクラス３：参照も修正もされた • NRU (Not Recently Used) algorithm は空ではない最下位のクラスからランダムにページを消す • 最適ではないが，容易な実装と十分な性能という特徴を持つ 4.4.3 先入れ先出しページ置き換えアルゴリズム • いわゆる FIFO (First Input First Output) • 古いページを優先的に消す • しかし，古いページ＝使われないページではない！ • というわけで，このまま使われることはない 4.4.4 セカンドチャンス置き換えアルゴリズム • FIFOの改良版 • ページを時系列に並べる • ページフォールトが起きたら古いページから参照 – もし参照ビットがセットされていれば，参照ビットをクリアして一番新しいページとして扱う – もし参照ビットがなければ消す 4.4.5 クロックページ置き換えアルゴリズム • セカンドチャンス置き換えアルゴリズムの改良 – ページをリスト上でせわしなく移動させているため効率的でない – 環状リストにする – 実現方法が違うだけで本質的には同じ 4.4.6 LRUページ置き換えアルゴリズム • LRU (Least Recently Use page) – 最近使われたページはまたすぐに使われるだろう，という戦略 – 実現可能であるがコストは小さくない – 実現手法はいくつかある – 例：図4-18 • ページテーブル数 n とすると， n×nの行列を用意 • ページフレームkが参照されると – 行kを全て1に設定 – 列kを全て0に設定 • ページフォールトの場合 – 行を2進法事とみなして値が最小のもの＝最も過去に参照された 4.4.7 LRU のソフトウェアによるシミュレーション • LRUをソフトウェアで実現するのは無理 • ソフトウェアで実現する方法として NFU (Not Frequently Used) アルゴリズム – クロック割り込みごとに，ページごとに参照ビットの内容をカウントする – ページフォールト時はそのカウンタが最小のものを消す – 欠点は初期化しないこと • 実はNFUでLRUをシミュレートできる（エージング） – 修正点は2つ • カウンタに加算する前にカウンタを1ビット右へシフト • 参照ビットをカウンタ内の最左端に加算する – 厳密な違いも2つ • 最後にアクセスされたのが分からない（例：図4-19 (e) の3,5） • カウンタのビット数は有限であること 4.4.8 ワーキングセットページ置き換えアルゴリズム • ワーキングセット – プロセスが現在使用中のページのセット • ワーキングセットモデル – 各プロセスのワーキングセットを記録し，プロセス実行前にメモリに持ってくるモデル – 多くのプログラムは一部分のページにしかアクセスしない →単調非減少関数になる w(k, t) – Kの値を予め決めておくと，ワーキングセットが一意に決まる k：メモリ参照 • アルゴリズムの近似 – k回のメモリ参照の代わりに実行時間を用いる – カレント仮想時間 • プロセスが開始後に実際に使用したCPU時間 – 年齢 • カレント仮想時間ー最後に使用された時間 4.4.9 WSClockページ置き換えアルゴリズム • ワーキングセットアルゴリズムを改善したもの – Working Set Clock アルゴリズム – クロックページ置き換えアルゴリズムとワーキングセットアルゴリズムを足したようなもの – 図4-22を参照 4.4.10 ページ置き換えアルゴリズムのまとめ • 図4-23を参照 • いい感じなのは – エージング – WSClock