オペレーティングシステム

オペレーティングシステムJ/K
(仮想記憶管理)
2005年10月20日
酒居敬一([email protected])
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
– 参照の時間的局所性を利用したものである
– 主記憶上で最も使われなかったページをページアウト
– ハードウェア機構が必要である
• カウンタ
LRUアルゴリズム
– 時間を計時するため、カウンタを設ける
– 各ページは最終参照時刻を保持する
– 最も古くに参照されたページを線形検索しページアウト
• スタック
– 参照されたページ番号をスタックトップに移動する
– スタックボトムがページアウト対象を示す
• 参照ビット
– 定期的にページ参照があったかをソフトウェアで調査
– 荒い時間刻みでLRUを実装したことに相当
– 擬似LRUとも呼ばれる
割付け技法
• 大域割付け
– システム内に、ページ枠の集合はひとつ
– ページのプロセスの所属とは無関係に割付ける
• 局所割付け
– プロセスでは、各々のページ枠集合から割付け
– ページ枠の集合をプロセスごとに持たせる
均等割付け(ページ枠数÷プロセス数)
比例配分割付け(ページ枠数×仮想記憶量÷全仮想記憶量)
ワーキングセット
プロセスが活発に参照した領域(ワーキングセット)を維持
ワーキングセットの決定には発見的手法が必要
記憶領域の保護
• TEXT
– 命令を置くための領域
– 書き込むことはあり得ない
– 命令はロードモジュールに含まれる
• DATA
– 初期値つき静的変数を置く領域
– 初期値はロードモジュールに含まれる
• BSS
– 初期値なし静的変数を置く領域
• STACK
– 動的変数や一時変数を置く領域
[Intel, ``Software Developer Manual’’]
[Intel, ``Software Developer Manual’’]