仮想記憶（2） 実際に存在する主記憶（物理メモリ）の容量に制限 されない「仮想的な記憶空間」をユーザに提供する 仮想記憶の基本アイディア 主記憶に入りきらない大きなプログラムでも，ある時点で 実行されているのはプログラムの一部のみ，必要となる データも一時には一部のデータのみ（参照の局所性） プログラム全体はディスク装置に入れておき， 実行時に必要な部分を主記憶にもってくればよい。 「主記憶容量」と「仮想記憶空間」 一般に， 実際に存在する主記憶容量 ＜ 仮想記憶空間 実際に存在する主記憶（物理メモリ） （512MB とか，1GBとか…） 000000000000 仮想記憶空間/論理アドレス空間 （Pentium4などでは64TB） 3FFFFFFFFFFF 1 仮想記憶 ディスクを介在して，実際の主記憶よりも大きな記憶空間を プログラム（ユーザ）に提供する 仮想記憶空間（論理アドレス） ディスク 領域 0 領域 1 領域 2 領域 3 領域 4 領域 6 領域 4 領域 9 領域 2 領域 5 領域 6 領域 7 領域 8 領域 9 ディスクの一部領域を 仮想記憶空間のため に使う （スワップ領域， ページファイル領域） プログラム（ユーザ）から アクセス可能な仮想的な 記憶装置（仮想記憶） 動的アドレス変換 主記憶空間 （物理アドレス） プロセッサから アクセス可能な 主記憶 （物理記憶） プロセッサ ページテーブル を参照 ページング方式 ページ番号 仮想アドレス ページテーブル 0000 P0 1000 P1 ‥‥ 0 1 1 0 2000 1 1000 2 3 4 5 6 主記憶 0000 P15 1000 0 P0 P1 P2 P2 0 1 P3 P4 P5 P6 2000 0 P0 3000 ‥‥ E000 P14 物理アドレス E 0 F 1 ディスク 3000 P6 0000 4kbyte F000 P15 物理アドレス （16kbyte，1ページ4kbyteとした場合） 存在ビット ページベース （各ページの主記憶上での開始アドレス） 仮想アドレス （64kbyte，1ページ4kbyteとした場合） 2 ページング方式における主記憶アクセス z プロセッサの生成する仮想アドレスは物理アドレスに変換され， プロセッサは物理アドレスで主記憶にアクセスする z 主記憶に存在する場合（ヒット：hit） → そのままアクセス アクセス対象が z 主記憶に存在しない場合（ページフォルト：page fault） → アクセス対象を含むページをディスクから主記憶にもってくる 主記憶上に空き領域がある場合 → 空き領域にもってくる 主記憶上に空き領域がない場合 → ① 当面使いそうにない物理ページを選択 （ページ置換えアルゴリズム） ② 選択したページ内容を主記憶から追い出す （ページアウト） ③ アクセス対象を含むページをディスク から主記憶上にコピー （ページイン） ④ 主記憶上の物理ページをアクセス 用語 ページフォルト（page fault） ： 参照ページが主記憶に存在しないこと （＝ページテーブルの存在ビットが0） ⇔ ヒット（hit）：参照ページが主記憶に存在すること ページイン（page in） ： 新しいページを主記憶（物理ページ）にもってくること ページアウト（page out） ： ページ内容を主記憶から追い出すこと 3 ページフォルトの処理手順 ページフォルト発生（割込み） 空きページの検索 空きページは？ ページをディスクから 取り出す あり 空きページフレームに読み込む なし ページ置換えに よりページを追い出す ページテーブルの存在ビットを 0 から１に書き換える 割込み処理から復帰 空きページを確保 処理の再開 追い出すページに書込みがあった場合 → ディスクに書き戻す 追い出すページに変更がない場合 → 書き戻す必要はない 汚れビット 汚れビット（dirty bit） 存在ビット ページベース 0 1 1 0 2 1 3 0 4 0 5 0 6 1 E 0 F 1 1 2000 0 1000 ページフォルト時に汚れビットが 1 のとき → ディスクに書き戻してから， ページを読み出す 0 のとき → ページを読み出すだけ （ディスクには書き戻さない） 1 3000 ‥‥ 0 0000 ページテーブル（表） （主記憶内） 4 問題 仮想アドレスを32bit，物理アドレスを30bitとし，ページ内アドレス（オフセット） の指定に12bitのアドレスを 使う仮想記憶において，1~5 の問いに答えよ。 仮想ｱﾄﾞﾚｽ（32ビット） 仮想ﾍﾟｰｼﾞ番号（20ﾋﾞｯﾄ） ﾍﾟｰｼﾞ内アドレス（12ﾋﾞｯﾄ） 20ﾋﾞｯﾄ ｱﾄﾞﾚｽ変換機構 12ﾋﾞｯﾄ 18ﾋﾞｯﾄ 物理ﾍﾟｰｼﾞ番号（18ﾋﾞｯﾄ） ﾍﾟｰｼﾞ内アドレス（12ﾋﾞｯﾄ） 物理ｱﾄﾞﾚｽ(30ビット） 1. 仮想空間の大きさと主記憶の大きさはそれぞれ何byteか？ 2. 1ページの大きさは何byteか？ 3. 仮想アドレス空間内のページ数は何個か？ 4. 物理アドレス空間内に格納することのできるページ数は何個か？ 5. ページテーブルには，存在ビット，汚れビット，ページベースを格納するために1ページ につき 4byte 使用する場合，ページテーブル全体の大きさは何byteになるか？ 解答 1. 仮想空間の容量＝232byte＝4×230byte＝4Gbyte 物理空間の容量＝230byte＝1Gbyte 2. ページ内は12ビットのアドレスで指定されるから，212＝4kbyte 3. 仮想ｱﾄﾞﾚｽ空間内のﾍﾟｰｼﾞ数＝232÷212＝220個 4. 物理ｱﾄﾞﾚｽ空間内のﾍﾟｰｼﾞ数＝230÷212＝218個 5. ﾍﾟｰｼﾞﾃｰﾌﾞﾙの大きさ＝220個，一つのﾍﾟｰｼﾞﾃｰﾌﾞﾙのﾃﾞｰﾀ＝4byte， したがって ﾍﾟｰｼﾞﾃｰﾌﾞﾙの大きさ（容量）＝220×4byte＝4Mbyte 5 ページフォルトとスラッシング 参照ページがメモリにない → ページフォルトの発生 → 空き領域を確保し，ディスクからページをロードする cf. 主記憶（メモリ）のアクセス時間 ： 100 ns ディスクからのデータ転送時間 ： 10 ms アクセス時間比 ： 1000～数万倍 頻繁なページフォルトの発生は実行速度の低下を招く （スラッシング：thrashing） ページフォルトの発生をできるだけ小さくすることが重要 ページフォルトのメモリアクセスへの影響 メモリのアクセス時間 ： Tm ページフォルトの発生確率 ： p （ヒット率：1-p） ページフォルトの処理にかかる時間 ： Tf （ディスクからデータ転送を含む） ページフォルトを考慮した主記憶の平均アクセス時間 ： Te Te = p×Tf + (1-p)×Tm 6 例 -9 Tm =100ns （ =100×10 s ） 1 200000 p = 0.000005（20万回に1回の発生） ←0.000005 = -3 Tf =10ms （ =10×10 s ） とすると， -3 -9 Te = 0.000005×10×10 +(1-0.000005)×100× 10 -9 -9 ≒1 = 50×10 +100×10 -9 = 150×10 = 150ns メモリ本来のアクセス時間 Tm ： 100ns 仮想記憶を導入することによる実効アクセス時間 Te ： 150ns 1.5倍の性能低下 性能低下係数 α= Te / Tm = 1.5 αの適正値 ： 1.1～1.2 程度 ページフォルト回数の見積り p=0.000005（20万回に1回の発生） 0.000005 = 1 200000 20万回アクセスするのに要する時間 100ns×200000+10ms=30ms → 30msに1回の割合で ページフォルトが発生 20万回のアクセス メモリ本来のアクセス時間 ページフォルトの処理時間 （Tm ） （ Tf ） したがって，1秒当り 約33回（←1/30ms）のページフォルトが 発生していることになる。 （通常，1秒当たり20～30回程度発生している） 7 ページ置換えアルゴリズム （page replacement algorithm） 主記憶中に空き領域（空きページ）がなくなったときに，いずれかのページを 追い出さなければならない（ページアウト）。どのページを追い出すか ？ 今後使われないであろうページを推測し，追い出す（ページアウト）する 主記憶 プログラム アルゴリズム (1) FIFO（First In First Out） (2) LRU（Least Recently Used） (3) LFU（Least Frequently Used） ページ0 a ページ1 b ページ2 c ページ3 ページ4 (1) FIFO（First In First Out） z 最も古くから存在するページを置換え対象にする 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 ページの参照順序 参照ページ 0 1 2 3 0 1 4 0 1 2 3 4 a 主記憶の ページ b c ページフォルト 発生の有無 ページフォルト回数 9回 8 (2) LRU（Least Recently Used） z 最も長い間使われなかったページを置換え対象にする 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 ページの参照順序 参照ページ 0 1 2 3 0 1 4 0 1 2 3 4 a 主記憶の ページ b c ページフォルト 発生の有無 ページフォルト回数 10回 (3) LFU（Least Frequently Used） z 最も使用頻度の少なかったページを置換え対象にする （使用頻度が同じ場合はLRU又はランダムに選択） ページの参照順序 参照ページ 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 0 1 2 3 0 1 4 0 1 2 3 4 a 01 01 01 3‡ 31 31 4‡ 41 41 21 31 41 主記憶の ページ b - 11 11 11 0‡ 01 01 02 02 02 02 02 c - - 21 21 21 1‡ 11 11 12 12 12 12 ページフォルト 発生の有無 ‡ はLRUによる選択 ○ ○ ○○ ○○ ○ ページフォルト回数 10回 9 ○ ○○ 演習問題 7 1. 仮想アドレスを 30bit，物理アドレスを 28bit とし，ページ内アドレスの指定に 13bit のアドレスを使う仮想 記憶において，次の設問に答えよ。 (1) 仮想空間の大きさと主記憶の大きさはそれぞれ何 byte か？ (2) 1 ページの大きさは何 byte か？ (3) 仮想アドレス空間内のページ数は何個か？ (4) 物理アドレス空間内に格納することのできるページ数は何個か？ (5) ページテーブルには，物理ページ番号及び存在ビット，汚れビットを格納するために 1 ペー ジにつき 4byte 使用する場合，ページテーブル全体の大きさは何 byte になるか？ 2. 主記憶のアクセス時間を 120ns，ページフォルトの発生確率を 0.000004，ページフォルトの処理時間を 15ms としたとき， (1) 主記憶の平均アクセス時間は何 ns か。 (2) 仮想記憶を採用したことによる性能低下係数はいくらか。 (3) 1 秒当り何回のページフォルトが発生していると考えられるか。 3. ペ ー ジ ン グ 方 式 の 仮 想 記 憶 に お い て ， 参 照 か つ 更 新 さ れ る ペ ー ジ 番 号 の 順 番 が ， 2→3→5→1→2→3→4→2→3→4→1→2 で，主記憶のページ枠が 3 ページのとき，各ページ置換えアル ゴリズムについて，主記憶内に存在するページの移り変わりを示せ。なお，LFU アルゴリズムにおいて，過 去の使用回数が同じ場合は LRU アルゴリズムを採用して，ページアウトするページを選択するものとする。 また，ページフォルトが発生する場合は「ページフォルト発生の有無」欄に○を付けよ。 (1) FIFO アルゴリズム 2 3 5 1 2 3 4 2 3 4 1 2 参照ページ 主記憶のページ a b c ページフォルト発生 の有無 (2) LRU アルゴリズム 2 3 5 1 2 3 4 2 3 4 1 2 参照ページ 主記憶のページ a b c ページフォルト発生 の有無 (1) LFU アルゴリズム 2 3 5 1 2 3 4 2 3 4 1 2 参照ページ 主記憶のページ a b c ページフォルト発生 の有無 10
© Copyright 2024 ExpyDoc
