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

オペレーティングシステム
(仮想記憶管理)
2006年11月2日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2006/
記憶階層(45ページ)
(0次記憶、短期記憶)
CPU内部のレジスタ
一次記憶(長期記憶)
主記憶(通常はRAM)のこと
電力の供給を絶てば、記録内容は失われる
二次記憶(外部記憶)
HDDやフロッピーなど
電力の供給がなくても、記録し続けるしくみがある
大容量とか可搬であるとか利点をもつが、一般に低速
一次記憶
一般にRAMとしてDRAMが使われる
DRAMは大容量だがアクセス速度が遅い
RAMの中ではコストパフォーマンスがよい
通常、お金は有限なのです…
ただし、リフレッシュが必要
小容量だがアクセス速度の速いSRAMもある
記憶の参照は局所性がみられることが多い
DRAMに高速SRAMを組み合わせるのが一般的
このときの高速SRAMはキャッシュと呼ばれている
CPUはせっかちさんだからね…
二次記憶
2つ以上の状態間で遷移でき、状態維持にエネル
ギーを消費しないものを利用して記録する
磁化を利用する
HDDやフロッピーやDAT(磁界を変調して書く、磁界を読む)
光磁気ディスクやMD(磁界を変調して書く、カー効果で読む)
電荷を利用する
フラッシュROM(電荷を注入して書く、閾値の変化で読む)
結晶構造を利用する
CD-RW(加熱による相変化で書く、相変化を読む)
入出力命令で装置上のデータを読み書きする
CPUがメモリを参照するのとは少し違う
記憶管理技法(46ページ)
 フェッチ技法
 要求時
 プリフェッチ
 割付け技法
 連続割付け
 単一連続割付け
 分割割付け
 固定区画割付け
 可変区画割付け
 非連続割付け
 ページング
 セグメンテーション
 置き換え技法
 スワッピング
 FIFO
 OPT
 LRU
記憶領域の保護
• TEXT
– 命令を置くための領域
– 書き込むことはあり得ない
– 命令はロードモジュールに含まれる
• DATA
– 初期値つき静的変数を置く領域
– 初期値はロードモジュールに含まれる
• BSS
– 初期値なし静的変数を置く領域
• STACK
– 動的変数や一時変数を置く領域
[Intel, ``Software Developer Manual’’]
[Intel, ``Software Developer Manual’’]
[大久保英嗣, オペレーティングシステムの基礎]
プロセスの中では記憶領域を自由に配置・獲得・使用したい!
記憶領域に関しても現実と切り離して、仮想的な存在とする
仮想記憶(55ページ)
仮想記憶に必要なこととは?
• 有限の資源である主記憶のプロセスへの割付け
– ページング
– (現在ではセグメンテーションは単体では使われない)
• アドレス変換
– ページング
– セグメンテーション
• プロセス固有の領域を保護
– セグメンテーション
アドレス変換
• ページングによるもの
– ページという固定の単位ごとにアドレスを変換
– 変換はアドレス変換表を使用
– 自由自在な変換ができる
– 高速化のために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’’]
ページングとセグメンテーションは組み合わされることが多い
ページングアルゴリズム(58ページ)
目的はページフォルト率を最小化
• FIFO
– 主記憶上の最も古いページを選択しページアウト
• ページインした順にページアウトする
– 特別なハードウェアはいらない
• OPT
– 将来のページ使用を見てページアウト
– 現実には実装できない。性能評価の際の指標
• LRU
– 参照の時間的局所性を利用したものである
– 主記憶上で最も使われなかったページをページアウト
– ハードウェア機構が必要である
• カウンタ
LRUアルゴリズム
– 時間を計時するため、カウンタを設ける
– 各ページは最終参照時刻を保持する
– 最も古くに参照されたページを線形検索しページアウト
• スタック
– 参照されたページ番号をスタックトップに移動する
– スタックボトムがページアウト対象を示す
• 参照ビット
– 定期的にページ参照があったかをソフトウェアで調査
– 荒い時間刻みでLRUを実装したことに相当
– 擬似LRUとも呼ばれる
割付け技法
• 大域割付け
– システム内に、ページ枠の集合はひとつ
– ページのプロセスの所属とは無関係に割付ける
• 局所割付け
– プロセスでは、各々のページ枠集合から割付け
– ページ枠の集合をプロセスごとに持たせる
均等割付け(ページ枠数÷プロセス数)
比例配分割付け(ページ枠数×仮想記憶量÷全仮想記憶量)
ワーキングセット
プロセスが活発に参照した領域(ワーキングセット)を維持
ワーキングセットの決定には発見的手法が必要
記憶割付けに関して
• 要求時ロードとページ置き換え
– 実記憶を超えた容量の仮想記憶が割付け可能
– プログラムやデータは参照される瞬間だけ実記憶に存
在していればよい(そのように維持されればよい)。
• 1次記憶(主記憶、RAM)と2次記憶(HDD)の関係
– 1次記憶は2次記憶のキャッシュ
• 記憶の実態は2次記憶装置上にある
– 2次記憶は1次記憶が不足したときの退避領域
• スラッシング
– ページインとページアウトが激しく起きている状態
– 実記憶容量より仮想記憶容量が大きく、参照の局所性
が期待できないときに起こることが多い。
サスペンドとハイバネーション
• サスペンド
– CPUは動作停止。内部情報の保持のため電力供給。
– メモリ(通常はDRAM)はリフレッシュ動作のみ継続。
– 周辺デバイスは内部状態をメモリ等に退避して電力供
給を停止。
• ハイバネーション
– すべてのデバイスは動作停止。電力供給も停止。
– 二次記憶装置などに内部状態を退避。
• レジューム
– CPU/メモリ/周辺デバイスの状態を復帰して、実行再
開
入出力機器
• バイト単位で入力と出力できる装置
– 読み書きする位置が設定(シーク)できるもの
• シーク可能デバイス
– DAT
– HDD
» シークが比較的速いので二次記憶装置として使われる
• ランダムにアクセスできるが、アクセス位置を示すポインタ
は装置側に存在する(メモリと異なる点)
– 読み書きする位置が設定できないもの
• シーク不可能デバイス
– キーボード
– プリンタ
– スキャナ
• 狭い意味での入出力装置
制御方法
• 入出力制御専用の命令:I/O命令
– メモリのようにキャッシュしない
これは、メモリのようにキャッシュ制御できないから
• I/O空間(メモリ空間に置かれている場合もある)
– メモリのように空間内にすべて展開しない
– I/Oポートという、ポートを通じて制御する
– ポート(Port: 本来の意味は港)に対して入出力する
直接同期制御
• プロセッサがハードウェアを直接操作
• ハードウェアの状態変化と操作が同期
• 状態変化を検出する方法→ポーリング
– ポーリングは時間精度がよい
– プロセッサは検出にかかりっきり
直接非同期制御
• プロセッサがハードウェアを直接操作
• ハードウェアの状態変化とプロセッサの動作
が非同期
– つまり、状態変化を別の手段で知る
– たとえば、割り込み
• プロセッサはその間別のことができる
間接制御
• バスマスタ転送
– DMA
• 主記憶を対象にデータを転送
– バス使用権を持っているもの→バスマスタ
• それ以外はバスマスタによってデータが転送される
• バスマスタになりえるもの→プロセッサ、ディスクI/Fなど
• I/Oプロセッサ
– 例: ネットワーク通信ボード, RAIDボード
– プロセッサの高速化により、減りつつある
入出力管理
• キャラクタデバイス
– 入出力動作で1バイトのデータが入出力できる
– キーボード、マウス、HDD
– 基本的にシーケンシャルアクセス
• ブロックデバイス
– ファイルシステムが構築できる
– HDD、フロッピー、CDROM
– 基本的にランダムアクセス
論理デバイス
• 直接ハードウェアを操作させると問題がある
– プロセスはOSの上に複数存在する、一方で、
デバイスは限られた数しかない。
– デバイスドライバが間に入る。
– ハードウェア構成は同一であるとは限らないが、
同一のインターフェースで使用できるようにしたい
– OSが使用するデバイスは、一般のプロセスから
アクセスされては困る。