オペレーティングシステムJ/K (仮想記憶管理) 2005年10月20日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2005/
プロセスの中では記憶領域を自由に配置・獲得・使用したい！ [大久保英嗣, オペレーティングシステムの基礎] プロセスの中では記憶領域を自由に配置・獲得・使用したい！ 記憶領域に関しても現実と切り離して、仮想的な存在とする 仮想記憶
有限の資源である主記憶のプロセスへの割付け 仮想記憶に必要なこととは？ 有限の資源である主記憶のプロセスへの割付け ページング （現在ではセグメンテーションは単体では使われない) アドレス変換 セグメンテーション プロセス固有の領域を保護
アドレス変換 ページングによるもの セグメンテーションによるもの ページという固定の単位ごとにアドレスを変換 変換はアドレス変換表を使用 自由自在な変換ができる 高速化のためにTLBを使う 連想記憶機構を使った変換表のキャッシュ 領域は物理的に分割したもの（構造が無い） セグメンテーションによるもの 任意の大きさの領域を変換 領域は一般に論理セグメントに対応（構造がある）
ページングによるアドレス変換 [Intel, ``Software Developer Manual’’]
ページングによるアドレス変換 [Intel, ``Software Developer Manual’’]
[Intel, ``Software Developer Manual’’]
セグメンテーションによるアドレス変換 [Intel, ``Software Developer Manual’’]
[Intel, ``Software Developer Manual’’]
ページングとセグメンテーションは組み合わされることが多い [Intel, ``Software Developer Manual’’] ページングとセグメンテーションは組み合わされることが多い
記憶管理技法 フェッチ技法 割付け技法 置き換え技法 要求時 プリフェッチ 連続割付け 非連続割付け スワッピング FIFO OPT LRU 単一連続割付け 分割割付け 固定区画割付け 可変区画割付け 非連続割付け ページング セグメンテーション 置き換え技法 スワッピング FIFO OPT LRU
プロセスに関する記憶領域管理 フェッチ技法 割付け技法 置き換え技法 要求時 非連続割付け （スワッピング） FIFO OPT LRU ページ不在例外により外部記憶装置からロード （セグメント不在例外により外部記憶装置からロード） 割付け技法 非連続割付け ページング 固定区画（ページ）により実記憶は管理される。 ハードウェアにより複数のページを連続してアクセスできるように配置する セグメンテーション 置き換え技法 （スワッピング） FIFO OPT LRU
ページングアルゴリズム 目的はページフォルト率を最小化 FIFO 主記憶上の最も古いページを選択しページアウト ページインした順にページアウトする 特別なハードウェアはいらない OPT 将来のページ使用を見てページアウト 現実には実装できない。性能評価の際の指標 LRU 参照の時間的局所性を利用したものである 主記憶上で最も使われなかったページをページアウト ハードウェア機構が必要である
LRUアルゴリズム カウンタ スタック 参照ビット 時間を計時するため、カウンタを設ける 各ページは最終参照時刻を保持する 最も古くに参照されたページを線形検索しページアウト スタック 参照されたページ番号をスタックトップに移動する スタックボトムがページアウト対象を示す 参照ビット 定期的にページ参照があったかをソフトウェアで調査 荒い時間刻みでLRUを実装したことに相当 擬似LRUとも呼ばれる
割付け技法 大域割付け 局所割付け システム内に、ページ枠の集合はひとつ ページのプロセスの所属とは無関係に割付ける プロセスでは、各々のページ枠集合から割付け ページ枠の集合をプロセスごとに持たせる 均等割付け（ページ枠数÷プロセス数） 比例配分割付け（ページ枠数×仮想記憶量÷全仮想記憶量） ワーキングセット プロセスが活発に参照した領域(ワーキングセット）を維持 ワーキングセットの決定には発見的手法が必要
記憶領域の保護 TEXT DATA BSS STACK 命令を置くための領域 書き込むことはあり得ない 命令はロードモジュールに含まれる 初期値つき静的変数を置く領域 初期値はロードモジュールに含まれる BSS 初期値なし静的変数を置く領域 STACK 動的変数や一時変数を置く領域
[Intel, ``Software Developer Manual’’]
[Intel, ``Software Developer Manual’’]