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