ページ置換アルゴリズムとは
ページ置換アルゴリズムとは、物理メモリのフレームがすべて埋まったとき、どのページを追い出して新しいページを入れるかを決める決まりです。選び方がよいと、遅いディスクの読み込みが減って、プログラムが速く動きます。
図書館で、机に本を3冊しか置けない場面を考えてください。新しい本を置くには、1冊を書棚に戻します。どれを戻すかで、書棚への往復の回数が変わります。
このレッスンのゴール
メモ
FIFOとLRUのページ置換を、手順どおりにシミュレーションすることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| ページフォールト | 使うページが、今メモリにないこと | |
| ヒット | 使うページが、すでにメモリにあること | |
| 参照列 | プログラムがページを使った順の記録 | 1, 2, 3, 1 |
| FIFO | 最も古く入ったページを追い出す方法 | |
| LRU | 最も長く使われていないページを追い出す方法 | |
| スワップ領域 | 追い出したページを置くディスクの場所 |
学生が入力するセルは、このプレビューでは空白です。
参照列で何回フォールトするか数える
プログラムがページを使った順番を、参照列といいます。使うたびに、そのページがフレームにあるかを調べます。あればヒットで、なければページフォールトです。
フォールトのたびに、遅いディスクを読みます。だから、置換の方法はフォールトの回数で比べます。ここでは、フレームは3つです。
FIFOは古く入ったものから追い出す
FIFOは、First In, First Out の略で、先に入ったものを先に出す方法です。いちばん長くメモリにいるページを追い出します。使われたかどうかは見ません。
参照列 1, 2, 3, 1, 4, 1 を見ます。フレームの中身は、古い順に左から並べます。
例: FIFOで1、2、3、1、4、1
| 参照 | 結果 | フレームの中身（古い順） | 追い出したページ |
|---|---|---|---|
| 1 | フォールト | 1 | - |
| 2 | フォールト | 1, 2 | - |
| 3 | フォールト | 1, 2, 3 | - |
| 1 | ヒット | 1, 2, 3 | - |
| 4 | フォールト | 2, 3, 4 | 1 |
| 1 | フォールト | 3, 4, 1 | 2 |
学生が入力するセルは、このプレビューでは空白です。
LRUは最近使っていないものから追い出す
LRUは、Least Recently Used の略です。最も長く使われていないページを追い出します。最近使ったページは、またすぐ使われやすい、という考えです。
同じ参照列で動かします。使うたびに、そのページを「最近」の側へ移します。中身は、使ったのが古い順です。
例: LRUで1、2、3、1、4、1
| 参照 | 結果 | フレームの中身（使った古い順） | 追い出したページ |
|---|---|---|---|
| 1 | フォールト | 1 | - |
| 2 | フォールト | 1, 2 | - |
| 3 | フォールト | 1, 2, 3 | - |
| 1 | ヒット | 2, 3, 1 | - |
| 4 | フォールト | 3, 1, 4 | 2 |
| 1 | ヒット | 3, 4, 1 | - |
学生が入力するセルは、このプレビューでは空白です。
フレームを増やしても減らないことがある
長めの参照列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 で、フレームを3つから4つに増やします。
FIFOでは、フォールトが9回から10回に増えます。メモリを増やしたのに悪くなる、この現象をベレイディの異常と呼びます。LRUでは、10回から8回に減りました。
例: フォールトの回数
| 方法 | フレーム3つ | フレーム4つ |
|---|---|---|
| FIFO | 9回 | 10回 |
| LRU | 10回 | 8回 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「メモリを増やせば、ページフォールトは必ず減る」と考える人が多くいます。多くの場合は減ります。ただし、FIFOでは増えることがあります。方法とデータしだいなので、数えて確かめます。
Linuxで追い出し先を見る
追い出したページを置くディスクの場所がスワップ領域です。Linux は、今の一覧を /proc/swaps に出します。1行目は見出しで、領域がなければ、見出しだけが出ます。
ページフォールトの回数は、/proc/vmstat にあります。pgfault は全部の数、pgmajfault はディスクを読んだ数です。数は変わるので、項目名だけを取り出します。
スワップ一覧の見出しを出す
head -n 1 /proc/swapsここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
フォールトの項目名を出す
grep -E '^(pgfault|pgmajfault)' /proc/vmstat | cut -d' ' -f1ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。