基本情報技術概論 (第14回) ソフトウェア記憶の管理と仮想記憶埼玉大学理工学研究科堀山貴史 1 期末試験情報処理技術者試験の過去問 http://www.jtec.ipa.go.jp/  7/30 (木) 3, 4 限  試験範囲 : 中間試験以後、7/23 の講義分まで      工-11 教室 (要確認) アルゴリズムとデータ構造 (第２部, 第10部 01) ソフトウェア (第4部 01～09, 第10部 03 該当部分) 確率と統計 (7/23 に実施) 持ち込み不可  荷物はイスの下に。  机の上や机の棚に物がある場合は、不正行為とみなします。問題用紙や解答用紙の配布を始めたら、私語厳禁。（私語も不正行為とみなします。） 2 前回の復習：ソフトウェアの体系  ユーザ  アプリケーションソフトウェア基本ソフトウェア (OS) 制御プログラム   言語プロセッサ   コンパイラ、アセンブラ、インタプリタサービスプログラム  ハードウェアスーパバイザ制御 (管理) やユーザプログラム実行の監視ジョブ管理、タスク管理、記憶管理データ管理、運用管理、障害管理ユーザインタフェース 3 ずいぶん前の復習：コンピュータの構成 CPU 制御装置入力装置演算装置主記憶装置出力装置補助記憶装置  主記憶 (main memory, メモリ) に、プログラムとデータを置く 4 記憶の管理    主記憶に複数のプログラムを置きたい主記憶よりも大きなサイズのプログラムを扱いたい実記憶管理 _________________ プログラムから、実際の主記憶 (の大きさや番地) が見える   スワッピング方式 / オーバーレイ方式仮想記憶管理 _________________ プログラムからは、仮想記憶が見える OS が、仮想記憶と実記憶とを対応させる  セグメント方式 / ページング方式 5 実記憶管理（１） ________________ スワッピング方式  主記憶に複数のプログラムを置きたいスワップアウト 1. スワッププログラムＤアウト実行に関係のないプログラムを、主記憶から待避させるプログラムＣプログラムＢプログラムＡＯＳ主記憶装置 2. 空き領域にロードプログラムＥ補助記憶装置新しいプログラムを実行したい 6 実記憶管理（１）スワッピング方式  主記憶に複数のプログラムを置きたいスワップインプログラムＥスワップ＿＿＿インプログラムＤプログラムＡＯＳ主記憶装置実行を再開したい補助記憶装置スワップアウトされていたプログラムを主記憶に戻す主記憶に空きがなければ、他のプログラムをスワップアウト 7 実記憶管理（２） ________________ オーバーレイ方式  主記憶よりも大きなサイズのプログラムを扱いたい  実行するプログラムを、セグメント (モジュール) に分割（OS ではなく）プログラム自身がロードのタイミングを指定  ルートセグメントセグメントＡセグメントＣセグメントＢセグメントＤ ※ ＡとＢ、ＣとＤは同時に使わない必要な最大サイズルートＡＢＣＤ主記憶装置 8 フラグメンテーション ________________  (断片化) OS が記憶領域の割当てと開放を繰り返す → こま切れの未使用領域 (断片) 合計では十分な空き領域があるが、こま切れのため、使えないプログラムＥプログラムＤＯＳ主記憶装置コンパクション？プログラムＦこま切れの隙間を集めて、連続した領域にする 9 プログラム実行に関連した用語  再配置 (リロケーション)  プログラムを、主記憶上の他の位置に置き直す (→ see also 演習 14回再配置可能)  ガーベージコレクション (ゴミ集め, Garbage Collection)  動的に確保した記憶領域のうち、不要になった部分を回収し、再び利用できるようにする処理 (Java 等で、実行環境が自動的に行ってくれる)  メモリリーク  プログラムが、動的に確保した記憶領域を、不要になっても解放せず、保持し続けること  システムから見ると、使える主記憶が減っていく 10 仮想記憶 11 仮想記憶  主記憶よりも大きなサイズのプログラムを扱いたい  OS が必要な所を必要に応じてロードしてくれると便利  OS が主記憶よりも大きなサイズの記憶空間を仮想的に用意する（仮想記憶という）  プログラムは、実記憶 (のサイズや番地) を気にしなくてよい実記憶分割Ｅ分割Ｃ分割ＡＯＳ主記憶装置ＯＳが、必要に応じてロード補助記憶装置分割Ｄ分割Ｃ分割Ｂ分割Ａ仮想記憶プログラム 12 仮想記憶管理（１） ________________ セグメント方式  セグメント … 論理的に意味のある、分割単位  プログラムをセグメントに分割して、OS が管理 ________________  セグメントのサイズは、可変 ________________ … フラグメンテーションが起きる可能性あり (→ コンパクションを行う) 13 仮想記憶管理（２） ________________ ページング方式  ページ … サイズ固定の分割単位  プログラムをページに分割して、OS が管理  ページフォールト ________________   必要なページが、実記憶に配置されていないページ置き換え    ページフォルトが発生したら必要ないページを補助記憶に待避（ページアウト）必要なページを主記憶にロード（ページイン） _____________ 14 テキスト p.110, 111 も参照ページ置き換えアルゴリズム F IFO First-In First-Out  どのページを必要ないと判断するか  F I FO … 最初に入ったページが、最初に出ていく ________________  次の仮想ページの参照に対し、実記憶の状態は F I FO によりどのように変化するか示しなさい。割当てステップ 1 2 3 4 5 6 参照する実記憶の状態仮想ページ 1 1 4 1 4 2 1 4 2 1 5 1 (H18年度秋改変) 参考： Belady の例外実記憶の割当て量を増やすと、かえってページフォールトが増えることがある 15 テキスト p.110, 111 も参照ページ置き換えアルゴリズム LRU Least Recently Used  どのページを必要ないと判断するか  LRU … 最も長く使われていないページを捨てる (最後に参照されてからの時間が最も長いページ) ________________  次の仮想ページの参照に対し、実記憶の状態は LRU によりどのように変化するか示しなさい。割当てステップ 1 2 3 4 5 6 参照する実記憶の状態仮想ページ 1 1 4 1 4 2 1 4 2 1 5 1 (H18年度秋改変) 16 スラッシング ________________  主記憶が極端に小さいと … ⇒ ページング（ページイン/ページアウト）が頻繁に発生 ⇒ 処理時間のほとんどがページング、プログラム実行のスループットが極端に低下参考：参照の局所性   時間的局所性  今参照されている箇所は、近い将来にも参照される可能性が高い空間的局所性  今参照されている箇所の近くの場所が、参照される可能性が高い仮想記憶やキャッシュが有効に機能する理由 17 動的アドレス変換  仮想記憶上の仮想アドレス (論理アドレス) を ________________ 主記憶上の実アドレス (物理アドレス) に変換する例) ページング物理アドレス論理アドレス 5 F 0 1 1000 + F01 = 1F01 ページページ枠内の番号アドレスページテーブルページページ枠の番号物理アドレス ※ 参照ページがページテーブルに無い場合、ページフォールト 1 5 A 2000 1000 3000 1000 2000 3000 主記憶ページ 5 ページ 1 ページ A 18 19 20 スラッシング ________________  主記憶が極端に小さいと … ⇒ ページング（ページインとページアウト）が頻繁に発生 ⇒ 処理時間のほとんどがページング、プログラム実行のスループットが極端に低下 21 参考：  時間的局所性   参照の局所性今参照されている箇所は、近い将来にも参照される可能性が高い空間的局所性  今参照されている箇所の近くの場所が、参照される可能性が高い ※ 仮想記憶やキャッシュは、これらの局所性のおかげで有効に機能する 22 23 練習問題：  フラグメンテーション (断片化) (H19年度春改変) モジュール A ～ E を次の順で操作する。操作終了時点で、主記憶の空き領域は何か所存在するか。ここで、主記憶は 500 kB、初期状態では何もロードされていない。また、モジュールは空き領域の先頭からロードする。 [操作] A ロード → B ロード → C ロード → B 解放 → D ロード → A 解放 → E ロードモジュール大きさ (kB) A 200 B 100 C 150 D 80 E 90 24 25 26 この教材のご利用について     この文面は、TOKYO TECH OCW の利用条件を参考にしましたこの教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。非商業利用に限定  この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。著作権の帰属  この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。同一条件での頒布・再頒布  この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件27 この教材のご利用について  配布場所  http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/  この powerpoint ファイルの著作者  堀山貴史 2007-2009 [email protected]  改変等を加えられた場合は、お名前等を追加してください図の著作者  p. 3  クリップアート : Microsoft Office Online / クリップアート  その他  堀山貴史  28