仮想記憶 (2) 実際に存在する主記憶 ( 物理メモリ ) の容量に制限されない 仮想的な記憶空間 をユーザに提供する 仮想記憶の基本アイディア 主記憶に入りきらない大きなプログラムでも, ある時点で実行されているのはプログラムの一部のみ, 必要となるデータも一時には一部のデータのみ ( 参照の局所性 ) プログラム全体はディスク装置に入れておき, 実行時に必要な部分を主記憶にもってくればよい 主記憶容量 と 仮想記憶空間 一般に, 実際に存在する主記憶容量 < 仮想記憶空間 実際に存在する主記憶 ( 物理メモリ ) (52MB とか,GB とか ) 仮想記憶空間 / 論理アドレス空間 (Pentium4 などでは 64TB) 3FFFFFFFFFFF
仮想記憶 ディスクを介在して, 実際の主記憶よりも大きな記憶空間をプログラム ( ユーザ ) に提供する 仮想記憶空間 ( 論理アドレス ) ディスク プログラム ( ユーザ ) からアクセス可能な仮想的な記憶装置 ( 仮想記憶 ) 領域 領域 領域 2 領域 3 領域 4 領域 5 領域 6 領域 7 領域 8 領域 9 仮想記憶空間のために使う ( スワップ領域, ページファイル領域 ) 主記憶空間 ( 物理アドレス ) 動領域 6 領域 4 領域 9 領域 2 プロセッサからアクセス可能な主記憶 ( 物理記憶 ) 的アドレス変換ディスクの一部領域を プロセッサ ページテーブルを参照 ページ番号 仮想アドレス E F P P P4 P5 ページテーブル 2 3 4 5 6 E F 仮想アドレス (64kyte, ページ 4kyte とした場合 ) 存在ビット ページング方式 2 3 物理アドレス 2 3 主記憶 P5 P2 P P6 4kyte P P P2 P3 P4 P5 P6 ディスク 物理アドレス (6kyte, ページ 4kyte とした場合 ) ページベース ( 各ページの主記憶上での開始アドレス ) 2
ページング方式における主記憶アクセス プロセッサの生成する仮想アドレスは物理アドレスに変換され, プロセッサは物理アドレスで主記憶にアクセスする アクセス対象が 主記憶に存在する場合 ( ヒット :hit) そのままアクセス 主記憶に存在しない場合 ( ページフォルト :pge fult) アクセス対象を含むページをディスクから主記憶にもってくる 主記憶上に空き領域がある場合 空き領域にもってくる 主記憶上に空き領域がない場合 当面使いそうにない物理ページを選択 ( ページ置換えアルゴリズム ) 2 選択したページ内容を主記憶から追い出す ( ページアウト ) 3 アクセス対象を含むページをディスクから主記憶上にコピー ( ページイン ) 4 主記憶上の物理ページをアクセス 用語 ページフォルト (pge fult) : 参照ページが主記憶に存在しないこと (= ページテーブルの存在ビットが ) ヒット (hit): 参照ページが主記憶に存在すること ページイン (pge in) : 新しいページを主記憶 ( 物理ページ ) にもってくること ページアウト (pge out) : ページ内容を主記憶から追い出すこと 3
ページフォルトの処理手順 ページフォルト発生 ( 割込み ) 空きページの検索 空きページは? なし ページ置換えによりページを追い出す あり ページをディスクから取り出す 空きページフレームに読み込む ページテーブルの存在ビットを から に書き換える 空きページを確保 割込み処理から復帰 処理の再開 追い出すページに書込みがあった場合 ディスクに書き戻す追い出すページに変更がない場合 書き戻す必要はない 汚れビット 汚れビット (dirty it) 存在ビット ページベース 2 3 4 5 6 2 3 ページフォルト時に汚れビットが のとき ディスクに書き戻してから, ページを読み出す のとき ページを読み出すだけ ( ディスクには書き戻さない ) E F ページテーブル ( 表 ) ( 主記憶内 ) 4
問題 仮想アドレスを 32it, 物理アドレスを 3it とし, ページ内アドレス ( オフセット ) の指定に 2it のアドレスを使う仮想記憶において,~5 の問いに答えよ 仮想アト レス (32 ビット ) 仮想ヘ ーシ 番号 (2 ヒ ット ) ヘ ーシ 内アドレス (2 ヒ ット ) 2 ヒ ット アト レス変換機構 2 ヒ ット 8 ヒ ット. 仮想空間の大きさと主記憶の大きさはそれぞれ何 yte か? 2. ページの大きさは何 yte か? 物理ヘ ーシ 番号 (8 ヒ ット ) ヘ ーシ 内アドレス (2 ヒ ット ) 物理アト レス (3 ビット ) 3. 仮想アドレス空間内のページ数は何個か? 4. 物理アドレス空間内に格納することのできるページ数は何個か? 5. ページテーブルには, 存在ビット, 汚れビット, ページベースを格納するために ページにつき 4yte 使用する場合, ページテーブル全体の大きさは何 yte になるか? 解答. 仮想空間の容量 =2 32 yte=4 2 3 yte=4gyte 物理空間の容量 =2 3 yte=gyte 2. ページ内は 2 ビットのアドレスで指定されるから,2 2 =4kyte 3. 仮想アト レス空間内のヘ ーシ 数 =2 32 2 2 =2 2 個 4. 物理アト レス空間内のヘ ーシ 数 =2 3 2 2 =2 8 個 5. ヘ ーシ テーフ ルの大きさ =2 2 個, 一つのヘ ーシ テーフ ルのテ ータ =4yte, したがってヘ ーシ テーフ ルの大きさ ( 容量 )=2 2 4yte=4Myte 5
ページフォルトとスラッシング 参照ページがメモリにない ページフォルトの発生 空き領域を確保し, ディスクからページをロードする f. 主記憶 ( メモリ ) のアクセス時間 : ns ディスクからのデータ転送時間 : ms アクセス時間比 : ~ 数万倍 頻繁なページフォルトの発生は実行速度の低下を招く ( スラッシング :thrshing) ページフォルトの発生をできるだけ小さくすることが重要 ページフォルトのメモリアクセスへの影響 メモリのアクセス時間 : T m ページフォルトの発生確率 : p ( ヒット率 :-p) ページフォルトの処理にかかる時間 : T f ( ディスクからデータ転送を含む ) ページフォルトを考慮した主記憶の平均アクセス時間 : T e T e = p T f + (-p) T m 6
例 T m =ns ( = -9 s ) p =.5(2 万回に 回の発生 ) T f =ms ( = -3 s ) とすると, T e =.5-3 +(-.5) -9 = 5-9 + -9 = 5-9 = 5ns.5 = 2 メモリ本来のアクセス時間 T m : ns 仮想記憶を導入することによる実効アクセス時間 T e : 5ns.5 倍の性能低下性能低下係数 α= T e / T m =.5 αの適正値 :.~.2 程度 ページフォルト回数の見積り p=.5(2 万回に 回の発生 ) 2 万回アクセスするのに要する時間.5 = 2 ns 2+ms=3ms 3msに 回の割合でページフォルトが発生 2 万回のアクセスメモリ本来のアクセス時間ページフォルトの処理時間 (T m ) ( T f ) したがって, 秒当り約 33 回 ( /3ms) のページフォルトが発生していることになる ( 通常, 秒当たり 2~3 回程度発生している ) 7
ページ置換えアルゴリズム (pge replement lgorithm) 主記憶中に空き領域 ( 空きページ ) がなくなったときに, いずれかのページを追い出さなければならない ( ページアウト ) どのページを追い出すか? 今後使われないであろうページを推測し, 追い出す ( ページアウト ) する アルゴリズム () FIFO(First In First Out) (2) LRU(Lest Reently Used) (3) LFU(Lest Frequently Used) プログラムページ ページ ページ2 ページ3 主記憶 ページ 4 () FIFO(First In First Out) 最も古くから存在するページを置換え対象にする ページの参照順序,, 2, 3,,, 4,,, 2, 3, 4 参照ページ 2 3 4 2 3 4 ページフォルト回数 9 回 8
(2) LRU(Lest Reently Used) 最も長い間使われなかったページを置換え対象にする ページの参照順序,, 2, 3,,, 4,,, 2, 3, 4 参照ページ 2 3 4 2 3 4 ページフォルト回数 回 (3) LFU(Lest Frequently Used) 最も使用頻度の少なかったページを置換え対象にする ( 使用頻度が同じ場合は LRU 又はランダムに選択 ) ページの参照順序,, 2, 3,,, 4,,, 2, 3, 4 参照ページ 2 3 4 3 3 3 4 4 - - - 2 2 2 2 2 3 4 4 2 3 4 2 2 2 2 2 2 2 2 は LRU による選択 ページフォルト回数 回 9
演習問題 7. 仮想アドレスを 3it, 物理アドレスを 28it とし, ページ内アドレスの指定に 3it のアドレスを使う仮想記憶において, 次の設問に答えよ () 仮想空間の大きさと主記憶の大きさはそれぞれ何 yte か? (2) ページの大きさは何 yte か? (3) 仮想アドレス空間内のページ数は何個か? (4) 物理アドレス空間内に格納することのできるページ数は何個か? (5) ページテーブルには, 物理ページ番号及び存在ビット, 汚れビットを格納するために ページにつき 4yte 使用する場合, ページテーブル全体の大きさは何 yte になるか? 2. 主記憶のアクセス時間を 2ns, ページフォルトの発生確率を.4, ページフォルトの処理時間を 5ms としたとき, () 主記憶の平均アクセス時間は何 ns か (2) 仮想記憶を採用したことによる性能低下係数はいくらか (3) 秒当り何回のページフォルトが発生していると考えられるか 3. ページング方式の仮想記憶において, 参照かつ更新されるページ番号の順番が, 2 3 5 2 3 4 2 3 4 2 で, 枠が 3 ページのとき, 各ページ置換えアルゴリズムについて, 主記憶内に存在するページの移り変わりを示せ なお,LFU アルゴリズムにおいて, 過去の使用回数が同じ場合は LRU アルゴリズムを採用して, ページアウトするページを選択するものとする また, ページフォルトが発生する場合は 欄に を付けよ () FIFO アルゴリズム 参照ページ 2 3 5 2 3 4 2 3 4 2 (2) LRU アルゴリズム 参照ページ 2 3 5 2 3 4 2 3 4 2 () LFU アルゴリズム 参照ページ 2 3 5 2 3 4 2 3 4 2