オペレーティングシステム (仮想記憶管理)

Presentation on theme: "オペレーティングシステム (仮想記憶管理)"— Presentation transcript:

1 オペレーティングシステム (仮想記憶管理)
2008年11月6日

2 記憶階層（４５ページ） （０次記憶、短期記憶） 一次記憶（長期記憶） 二次記憶（外部記憶） CPU内部のレジスタ
主記憶（通常はRAM)のこと 電力の供給を絶てば、記録内容は失われる 二次記憶（外部記憶） HDDやフロッピーやフラッシュドライブなど 電力の供給がなくても、記録し続けるしくみがある 大容量とか可搬であるとか利点をもつが、一般に低速 プロセッサの動作速度に対して、速いか遅いかを考える プロセッサ 数百ps, 高速SRAM 数ns, DRAM数十ns, HDD 数ms

3 小容量だがアクセス速度の速いSRAMもある 記憶の参照は局所性がみられることが多い
一次記憶 一般にRAMとしてDRAMが使われる DRAMは大容量だがアクセス速度が遅い RAMの中ではコストパフォーマンスがよい 通常、お金は有限なのです… ただし、リフレッシュが必要 小容量だがアクセス速度の速いSRAMもある 　記憶の参照は局所性がみられることが多い DRAMに高速SRAMを組み合わせるのが一般的 このときの高速SRAMはキャッシュと呼ばれている CPUはせっかちさんだからね…

4

5 ２つ以上の状態間で遷移でき、状態維持にエネルギーを消費しないものを利用して記録する
二次記憶 ２つ以上の状態間で遷移でき、状態維持にエネルギーを消費しないものを利用して記録する 磁化を利用する HDDやフロッピーやDAT（磁界を変調して書く、磁界を読む） 光磁気ディスクやMD（磁界を変調して書く、カー効果で読む） 電荷を利用する フラッシュROM（電荷を注入して書く、閾値の変化で読む） 結晶構造を利用する CD-RW（加熱による相変化で書く、相変化を読む） 入出力命令で装置上のデータを読み書きする CPUがメモリを参照するのとは少し違う

6 記憶管理技法（46ページ） フェッチ技法 割付け技法 置き換え技法 要求時 プリフェッチ 連続割付け 非連続割付け スワッピング FIFO
単一連続割付け 分割割付け 固定区画割付け 可変区画割付け 非連続割付け ページング セグメンテーション 置き換え技法 スワッピング FIFO OPT LRU

7 記憶領域の保護 TEXT DATA BSS STACK 命令を置くための領域 書き込むことはあり得ない 命令はロードモジュールに含まれる
初期値つき静的変数を置く領域 初期値はロードモジュールに含まれる BSS 初期値なし静的変数を置く領域 STACK 動的変数や一時変数を置く領域

8 [Intel, ``Software Developer Manual’’]

9 [Intel, ``Software Developer Manual’’]

10 プロセスの中では記憶領域を自由に配置・獲得・使用したい！
[大久保英嗣, オペレーティングシステムの基礎] プロセスの中では記憶領域を自由に配置・獲得・使用したい！ 　　記憶領域に関しても現実と切り離して、仮想的な存在とする 　　　　　　　　　　　　　　　　　仮想記憶（55ページ）

11 有限の資源である主記憶のプロセスへの割付け
仮想記憶に必要なこととは？ 有限の資源である主記憶のプロセスへの割付け ページング （現在ではセグメンテーションは単体では使われない) アドレス変換 セグメンテーション プロセス固有の領域を保護

12 アドレス変換 ページングによるもの セグメンテーションによるもの ページという固定の単位ごとにアドレスを変換 変換はアドレス変換表を使用
自由自在な変換ができる 高速化のためにTLBを使う 連想記憶機構を使った変換表のキャッシュ 領域は物理的に分割したもの（構造が無い） セグメンテーションによるもの 任意の大きさの領域を変換 領域は一般に論理セグメントに対応（構造がある）

13 ページングによるアドレス変換 [Intel, ``Software Developer Manual’’]

14 ページングによるアドレス変換 [Intel, ``Software Developer Manual’’]

15 [Intel, ``Software Developer Manual’’]

16 セグメンテーションによるアドレス変換 [Intel, ``Software Developer Manual’’]

17 [Intel, ``Software Developer Manual’’]

18 ページングとセグメンテーションは組み合わされることが多い
[Intel, ``Software Developer Manual’’] ページングとセグメンテーションは組み合わされることが多い

19 ページングアルゴリズム（58ページ） 目的はページフォルト率を最小化
FIFO 主記憶上の最も古いページを選択しページアウト ページインした順にページアウトする 特別なハードウェアはいらない OPT 将来のページ使用を見てページアウト 現実には実装できない。性能評価の際の指標 LRU 参照の時間的局所性を利用したものである 主記憶上で最も使われなかったページをページアウト ハードウェア機構が必要である

20 LRUアルゴリズム カウンタ スタック 参照ビット 時間を計時するため、カウンタを設ける 各ページは最終参照時刻を保持する
最も古くに参照されたページを線形検索しページアウト スタック 参照されたページ番号をスタックトップに移動する スタックボトムがページアウト対象を示す 参照ビット 定期的にページ参照があったかをソフトウェアで調査 荒い時間刻みでLRUを実装したことに相当 擬似LRUとも呼ばれる

21 割付け技法 大域割付け 局所割付け システム内に、ページ枠の集合はひとつ ページのプロセスの所属とは無関係に割付ける
プロセスでは、各々のページ枠集合から割付け ページ枠の集合をプロセスごとに持たせる 均等割付け（ページ枠数÷プロセス数） 比例配分割付け（ページ枠数×仮想記憶量÷全仮想記憶量） ワーキングセット プロセスが活発に参照した領域(ワーキングセット）を維持 ワーキングセットの決定には発見的手法が必要

22 1次記憶（主記憶、RAM）と2次記憶（HDD)の関係
記憶割付けに関して 要求時ロードとページ置き換え 実記憶を超えた容量の仮想記憶が割付け可能 プログラムやデータは参照される瞬間だけ実記憶に存在していればよい（そのように維持されればよい）。 1次記憶（主記憶、RAM）と2次記憶（HDD)の関係 １次記憶は２次記憶のキャッシュ 記憶の実態は２次記憶装置上にある ２次記憶は１次記憶が不足したときの退避領域 スラッシング ページインとページアウトが激しく起きている状態 実記憶容量より仮想記憶容量が大きく、参照の局所性が期待できないときに起こることが多い。

23 サスペンドとハイバネーション サスペンド ハイバネーション レジューム CPUは動作停止。内部情報の保持のため電力供給。
メモリ（通常はDRAM）はリフレッシュ動作のみ継続。 周辺デバイスは内部状態をメモリ等に退避して電力供給を停止。 ハイバネーション すべてのデバイスは動作停止。電力供給も停止。 二次記憶装置などに内部状態を退避。 レジューム CPU/メモリ/周辺デバイスの状態を復帰して、実行再開

24 入出力機器 バイト単位で入力と出力できる装置 読み書きする位置が設定（シーク）できるもの 読み書きする位置が設定できないもの
シーク可能デバイス DAT HDD シークが比較的速いので二次記憶装置として使われる ランダムにアクセスできるが、アクセス位置を示すポインタは装置側に存在する（メモリと異なる点） 読み書きする位置が設定できないもの シーク不可能デバイス キーボード プリンタ スキャナ 狭い意味での入出力装置

25 I/O空間（メモリ空間に置かれている場合もある）
制御方法 入出力制御専用の命令：I/O命令 メモリのようにキャッシュしない 　これは、メモリのようにキャッシュ制御できないから I/O空間（メモリ空間に置かれている場合もある） メモリのように空間内にすべて展開しない I/Oポートという、ポートを通じて制御する ポート(Port: 本来の意味は港)に対して入出力する

26 直接同期制御 プロセッサがハードウェアを直接操作 ハードウェアの状態変化と操作が同期 状態変化を検出する方法→ポーリング
ポーリングは時間精度がよい プロセッサは検出にかかりっきり

27 直接非同期制御 プロセッサがハードウェアを直接操作 ハードウェアの状態変化とプロセッサの動作が非同期 つまり、状態変化を別の手段で知る
たとえば、割り込み プロセッサはその間別のことができる

28 間接制御 バスマスタ転送 I/Oプロセッサ DMA バス使用権を持っているもの→バスマスタ 例: ネットワーク通信ボード, RAIDボード
主記憶を対象にデータを転送 バス使用権を持っているもの→バスマスタ それ以外はバスマスタによってデータが転送される バスマスタになりえるもの→プロセッサ、ディスクI/Fなど I/Oプロセッサ 例: ネットワーク通信ボード, RAIDボード プロセッサの高速化により、減りつつある

29 入出力管理 キャラクタデバイス ブロックデバイス 入出力動作で１バイトのデータが入出力できる キーボード、マウス、HDD
基本的にシーケンシャルアクセス ブロックデバイス ファイルシステムが構築できる HDD、フロッピー、CDROM 基本的にランダムアクセス

30 論理デバイス 直接ハードウェアを操作させると問題がある プロセスはOSの上に複数存在する、一方で、 デバイスは限られた数しかない。
デバイスドライバが間に入る。 ハードウェア構成は同一であるとは限らないが、 同一のインターフェースで使用できるようにしたい OSが使用するデバイスは、一般のプロセスから アクセスされては困る。