基本情報技術概論（第12回） 埼玉大学 理工学研究科 堀山 貴史

Presentation on theme: "基本情報技術概論（第12回） 埼玉大学 理工学研究科 堀山 貴史"— Presentation transcript:

1 基本情報技術概論（第12回） 埼玉大学 理工学研究科 堀山 貴史
2010/01/20 基本情報技術概論 (第12回) 基本ソフトウェア (OS) (前回の続き) 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

2 制御プログラム ユーザ 言語プロセッサ サービスプログラム 基本 ソフトウェア (OS) ハードウェア 前回の復習： ソフトウェアの体系
前回の復習： ソフトウェアの体系 制御プログラム スーパバイザ 制御 (管理) やユーザプログラム実行の監視 ジョブ管理、タスク管理、記憶管理 データ管理、運用管理、障害管理 言語プロセッサ コンパイラ、アセンブラ、インタプリタ サービスプログラム ユーザインタフェース ユーザ アプリケーション ソフトウェア 基本 ソフトウェア (OS) ハードウェア

3 記憶の管理

4 コンピュータの構成 (第１回の復習) 主記憶 (main memory, メモリ) に、 CPU 制御装置 演算装置 入力装置 主記憶装置
コンピュータの構成 (第１回の復習) CPU 主記憶 (main memory, メモリ) に、 プログラム と データを置く 制御装置 演算装置 入力装置 主記憶装置 出力装置 補助記憶装置

5 記憶の管理 主記憶に 複数のプログラム を置きたい 主記憶よりも 大きなサイズのプログラム を扱いたい 実記憶管理
プログラムから、実際の主記憶 (の大きさや番地) が見える スワッピング方式 / オーバーレイ方式 仮想記憶管理 プログラムからは、仮想記憶が見える OS が、仮想記憶と実記憶とを対応させる セグメント方式 / ページング方式 _________________ _________________

6 実行に関係のない プログラムを、 主記憶から 待避させる
実記憶管理（１）　スワッピング方式 ________________ 主記憶に複数のプログラムを置きたい スワップアウト 実行に関係のない プログラムを、 主記憶から 待避させる 1. スワップ アウト プログラム Ｄ プログラム Ｃ プログラム Ｂ 2. 空き領域 に ロード プログラム Ｅ プログラム Ａ ＯＳ 新しいプログラムを実行したい 主記憶装置 補助記憶装置

7 スワップアウト されていた プログラムを 主記憶に戻す
実記憶管理（１）　スワッピング方式 主記憶に複数のプログラムを置きたい スワップイン スワップアウト されていた プログラムを 主記憶に戻す スワップ イン プログラム Ｅ ＿＿＿ プログラム Ｄ プログラム Ａ 実行を 再開したい 主記憶に空きが なければ、 他のプログラムを スワップアウト ＯＳ 主記憶装置 補助記憶装置

8 実記憶管理（２） オーバーレイ方式 主記憶よりも大きなサイズのプログラムを扱いたい 実行するプログラムを、セグメントに分ける
実記憶管理（２）　オーバーレイ方式 ________________ 主記憶よりも大きなサイズのプログラムを扱いたい 実行するプログラムを、セグメントに分ける （OS ではなく） プログラム自身が ロードのタイミングを指定 ルート セグメント 必要な最大サイズ ルート セグメント Ａ セグメント Ｂ Ａ Ｂ Ｃ Ｄ セグメント Ｃ セグメント Ｄ 主記憶装置 ※ ＡとＢ、ＣとＤは同時に使わない

9 OS が記憶領域の割当てと開放を繰り返す → こま切れの未使用領域 (断片) 合計では十分な空き領域があるが、 こま切れのため、使えない ？
用語： フラグメンテーション (断片化) OS が記憶領域の割当てと開放を繰り返す 　　　　　　　　→ こま切れの未使用領域 (断片) 　　　　　　　　　　合計では十分な空き領域があるが、 　　　　　　　　　　こま切れのため、使えない プログラム Ｅ プログラム Ｄ ？ プログラム Ｆ ＯＳ 主記憶装置

10 練習問題： フラグメンテーション (断片化)
練習問題： フラグメンテーション (断片化) (H19年度 春 改変) モジュール A ～ E を次の順で操作する。 操作終了時点で、 主記憶の空き領域は何か所存在するか。 ここで、主記憶は 500 kB、初期状態では何もロードされていない。また、モジュールは空き領域の先頭からロードする。 [操作] A ロード → B ロード → C ロード → B 解放 → D ロード → A 解放 → E ロード モジュール 大きさ (kB) A 200 B 100 C 150 D 80 E 90

11 仮想記憶 主記憶よりも大きなサイズのプログラムを扱いたい OS が必要な所を必要に応じてロードしてくれると便利 実記憶 プログラム ＯＳ
仮想的に用意する　（仮想記憶という） プログラムは、実記憶 (のサイズや番地) を気にしなくてよい 分割 Ｅ 実記憶 分割 Ｃ プログラム 分割 Ｄ 分割 Ａ ＯＳ が、 必要に応じてロード ＯＳ 分割 Ｃ 分割 Ｂ 分割 Ａ 主記憶装置 補助記憶装置 仮想記憶

12 仮想記憶管理（１） セグメント方式 セグメント … 論理的に意味のある、分割単位 プログラムをセグメントに分割して、OS が管理
仮想記憶管理（１）　セグメント方式 ________________ セグメント … 論理的に意味のある、分割単位 プログラムをセグメントに分割して、OS が管理 セグメントのサイズは、可変 （フラグメンテーションが起きる可能性あり）

13 仮想記憶管理（２） ページング方式 ページ … サイズ固定の分割単位 プログラムをページに分割して、OS が管理 ページフォルト
仮想記憶管理（２）　ページング方式 ________________ ページ … サイズ固定の分割単位 プログラムをページに分割して、OS が管理 ページフォルト 必要なページが、実記憶に配置されていない ページ置き換え ページフォルトが発生したら 必要ないページを補助記憶に待避 （ページアウト） 必要なページを主記憶にロード （ページイン） _____________

14 ページ置き換えアルゴリズム F I FO F I FO … 最初に入ったページが、最初に出ていく どのページを必要ないと判断するか
First-In First-Out どのページを必要ないと判断するか F I FO … 最初に入ったページが、最初に出ていく 次の仮想ページの参照に対し、実記憶の状態は F I FO により どのように変化するか示しなさい。 (H18年度 秋 改変) 割当て ステップ 参照する 仮想ページ 実記憶の状態 参考： Belady の例外 実記憶の割当て量を 増やすと、かえって ページフォールトが 増えることがある 1 1 1 - - 2 4 1 4 - 3 2 1 4 2 4 1 5 5 6 1

15 ページ置き換えアルゴリズム LRU LRU … 最も長く使われていないページを捨てる (最後に参照されてからの時間が最も長いページ)
Least Recently Used どのページを必要ないと判断するか LRU … 最も長く使われていないページを捨てる (最後に参照されてからの時間が最も長いページ) 次の仮想ページの参照に対し、実記憶の状態は LRU により どのように変化するか示しなさい。 (H18年度 秋 改変) 割当て ステップ 参照する 仮想ページ 実記憶の状態 1 1 1 - - 2 4 1 4 - 3 2 1 4 2 4 1 5 5 6 1

16 ⇒ ページング （ページイン と ページアウト） が 頻繁に発生 ⇒ 処理時間のほとんどがページング、
用語： スラッシング 実記憶が極端に小さいと … ⇒ ページング （ページイン と ページアウト） が 頻繁に発生 ⇒ 処理時間のほとんどがページング、 プログラム実行のスループットが極端に低下

17 時間的局所性 今 参照されている箇所は、 近い将来 にも参照される可能性が高い 空間的局所性 今 参照されている箇所の 近くの場所 が、
用語：　参照の局所性 時間的局所性 今 参照されている箇所は、 近い将来 にも参照される可能性が高い 空間的局所性 今 参照されている箇所の 近くの場所 が、 参照される可能性が高い ※ 仮想記憶やキャッシュは、 これらの局所性のおかげで有効に機能する

18

19

20 この文面は、TOKYO TECH OCW の利用 条件を参考にしました
この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

21 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/
この powerpoint ファイルの著作者 堀山 貴史　 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4 ハードディスク : 堀山 貴史 CPU, メモリ, キーボード, USB : パソコン, ディスプレイ, プリンタ, マウス, FD, CD : Microsoft Office Online / クリップアート p. 2 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史