メモリ管理 4.3, 4.4 章 さだ

4.3 仮想メモリ プログラムが大きすぎてメモリに入りきらない問題 オーバレイ：初期の解決策 仮想メモリ：現代の解決策 プログラムを分割してメモリに格納する プログラムのスワップイン・アウトはOSがやってくれる プログラムの分割はプログラマの仕事 →大変！ 仮想メモリ：現代の解決策 プログラムコード，データ，スタックからなるプログラム全体が物理メモリサイズを越えてもOK

4.3.1 ページング 仮想アドレス ページ ページフレーム 例： MOVE REG, 1000 この1000というのが仮想アドレス 仮想アドレスは仮想アドレス空間を持つ 仮想アドレスはMMU (Memory Management Unit) で物理メモリアドレスへ変換される 現代のMMUはたいていCPUに内蔵されています ページ 仮想アドレス空間を区切る単位 ページフレーム 物理メモリ内の対応する部分

マッピング 1ビットの存在/不在ビット MMUの動作例 図4-10を参照 例：仮想アドレス8192→ページフレーム6 例：仮想アドレス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 のソフトウェアによるシミュレーション ソフトウェアで実現する方法として NFU (Not Frequently Used) アルゴリズム クロック割り込みごとに，ページごとに参照ビットの内容をカウントする ページフォールト時はそのカウンタが最小のものを消す 欠点は初期化しないこと 実はNFUでLRUをシミュレートできる（エージング） 修正点は2つ カウンタに加算する前にカウンタを1ビット右へシフト 参照ビットをカウンタ内の最左端に加算する 厳密な違いも2つ 最後にアクセスされたのが分からない（例：図4-19 (e) の3,5） カウンタのビット数は有限であること

4.4.8 ワーキングセットページ置き換えアルゴリズム プロセスが現在使用中のページのセット ワーキングセットモデル 各プロセスのワーキングセットを記録し，プロセス実行前にメモリに持ってくるモデル 多くのプログラムは一部分のページにしかアクセスしない →単調非減少関数になる Kの値を予め決めておくと，ワーキングセットが一意に決まる k：メモリ参照 w(k, t)

アルゴリズムの近似 k回のメモリ参照の代わりに実行時間を用いる カレント仮想時間 年齢 プロセスが開始後に実際に使用したCPU時間 カレント仮想時間ー最後に使用された時間

4.4.9 WSClockページ置き換えアルゴリズム ワーキングセットアルゴリズムを改善したもの Working Set Clock アルゴリズム クロックページ置き換えアルゴリズムとワーキングセットアルゴリズムを足したようなもの 図4-22を参照

4.4.10 ページ置き換えアルゴリズムのまとめ 図4-23を参照 いい感じなのは エージング WSClock