スポンサードリンク
こんにちは、ももやまです！
今回は基本情報、応用情報でよく出るページフォルト、LRUアルゴリズムについて解説をします。
★注意★
- 仮想メモリと物理メモリの違い
- ページングの流れ
- ページフォルトとは何か
がまだあまり理解していない人は、この記事を読む前に下の復習記事「仮想記憶とページング」を読むことをおすすめします。
目次
スポンサードリンク
１．ページフォルトについて
ページフォルトとは、プログラムを実行するのに必要なページが主記憶（メインメモリ）上に存在しないときに発生する割り込みとなります。
(1) ページフォルトを検知してから置き換えるまで
ページフォルトの検知は、MMU（Memory Management Unit）がページテーブルにある存在ビットで行います。もし、この存在ビットがリセットされていればページフォルトが発生します（ハードウェア側で）。
ここからはOS内の処理となります。
まずは、空きページがあるかないかを探します。
空きページがあれば、そのまま空きページに必要なページを（ハードディスクなどの）補助記憶装置からページを読み込みます。
空きページがなければ、ページを置きかえます。ページの置き換えには（LRUアルゴリズムなどの）様々ななアルゴリズムが使われます（下のほうで紹介します）。
（置き換えアルゴリズムで選んだ）主記憶のページを補助記憶へ退避させ（ページアウト）、退避させたページに必要なページを補助記憶から読み込みます（ページイン）。
最後に存在ビットをセットし、物理ページ番号を記録します。
(2) 修正ビットの役割
ページフォルトの際に変更されていないページにも関わらず補助記憶へ書き出すのは大変無駄ですね。この無駄を防ぐために用意されているのが修正ビットです。
修正ビットは、名前の通りページが変更されたかを示すビットです（ページテーブル内にあります）。
具体的にどのように修正ビットを使うのかについてですが、まずページを書き込む際に修正ビットをセットします。
実際にページを置き換える際に、修正ビットがセットされているかを確認します。修正ビットがセットされていたときは補助記憶装置に書きだしますが、修正ビットがセットされていない場合は補助記憶装置へ書き出さないようにすることで、無駄な補助記憶装置の書き出しを防ぎます。
(3) 参照ビットの役割
参照ビットは名前の通りページが参照されるとセットされるビットです。
後程説明するLRUアルゴリズムでは、長い間ページが参照されていないページを置き換えるアルゴリズムですが、長い間ページが参照されていないかを判定するために参照ビットをチェックします。
スポンサードリンク
２．ページ置き換えアルゴリズム
ページフォルトの際に空きページがなければ、ページを置きかえます。言い換えると、ページが犠牲になってしまいます。
その犠牲になるページをどうやって選ぶか主に3つのアルゴリズムを紹介していきたいと思います（他にも様々なアルゴリズムがあります）。
(1) FIFO(First In First Out)アルゴリズム（キュー）
まずは単純なアルゴリズムから紹介します。
このアルゴリズムでは、最も古くロードされたページを追い出すアルゴリズムとなっております。
実際に1つ試してみましょう。
ページ枠は3つ、参照列は0～5の6つがあるとし、「3,2,1,0,1,2,5,2,5,1,4,2」の順にページを読みこんだ場合のページフォルトの発生箇所と発生回数を見ていきましょう。
最初の3つは空ページなので必ずページフォルトが発生します。
4つ目以降は、ページフォルトが発生した際に書き換えたページを赤色で示しています（色で書いておくとどのページを書き換えたかわかりやすくなっておすすめです）。
結果、8回のページフォルトが起こります。
(2) OPTアルゴリズム（理論上最速・いわゆるTAS）
つぎに紹介するのがOPTアルゴリズムです。
このアルゴリズムは、未来にわたって最も参照されないページを置き換えるアルゴリズムです。
ただし、未来のことを予言するのは非常に難しいのでこのアルゴリズムは理論値を計算する以外には使えません。
(1)と同じ例で実際にページフォルトの発生箇所と発生回数を見ていきましょう。
4つ目のページフォルト：3が参照されることはもうないので3を置き換え
5つ目のページフォルト：0が参照されることはもうないので3を置き換え
6つ目のページフォルト：2以外は参照されることがないので5か1のどちらかを置き換え（上のほう優先で4を置き換えました）
先程と同じく、赤色の部分がページフォルトの際に書き換えたページとなっております。
(3) LRUアルゴリズム（Least Recently Used）
実際にページ置き換えの際によく使われるのがLRUアルゴリズムです。
このアルゴリズムは、「過去最も参照されなかったページを置き換えるアルゴリズム」です。
(1)と同じ例で実際にページフォルトの発生箇所と発生回数を見ていきましょう。
4つ目のページフォルト：3,2,1の中で最も参照されたのが古いのは3なので3を置き換え
5つ目のページフォルト：0,2,1の中で最も参照されたのが古いのは0なので0を置き換え
6つ目のページフォルト：5,2,1の中で最も参照されたのが古いのは2なので2を置き換え
となります。
スポンサードリンク
３．なぜLRUアルゴリズムがよく使われるか
LRUはアルゴリズムは実際のページ置き換えでよく使われると書きましたね。
では、なぜLRUアルゴリズムは使われるのでしょうか。
最適解（理論値）なのは将来のページ参照を予測して、将来最も長い間参照されないページを置き換えることですね。
しかし、将来のページを置き換えることは大変困難ですね。
そこで使うのが時間的局所性です。ページの参照には時間的局所性があります。
時間的局所性とは、最近参照されたページは近い将来に参照される可能性が高い性質のことを表します。言い換えると、長い参照されないページは将来的にも参照される可能性は低いといいかえることができますね。
LRUアルゴリズムは、過去最も参照されなかったページを置き換えるアルゴリズムですね。ページの参照には時間的局所性があるので、上で説明した理論値アルゴリズム（将来長い間参照されたかったページを書き換えるアルゴリズム）の近似となっていますね。
なので、他のアルゴリズムに比べてより高い確率で参照するページがメインメモリ内に登録されることを実現でき、ページフォルト回数を減らし、メモリアクセスの遅れを減少させることができます。
なので、LRUアルゴリズムは他のページ置き換えアルゴリズムに比べて優れているため、よく用いられるのです。
４．TLB (Translation Lookaside Buffer)
ページ参照速度をさらにあげるため、プログラムを実行する際にはページテーブルにアクセスする前にTLBにアクセスを行います。
TLBとは、「仮想ページが物理メモリ上のどの位置に対応しているか」を高速にアクセスできるレジスタ上に保存しておくことで、仮想ページ番号がTLBに存在するときは高速にアクセスすることができます。
簡単に言うと、ページテーブルのキャッシュです。
アクセス順番としては、
1st：仮想ページ番号がTLBにあるかチェック（あればTLBにアクセス）
2nd：TLBになければページテーブルをチェック（あればページテーブルにアクセス）
3rd：ページテーブルにもなければページフォルト、補助記憶からアクセス
となります。
５．練習問題
では、実際に練習していきましょう。
今回は基本情報、応用情報の問題を練習問題とします。
練習1
ページ置換えアルゴリズムにおけるLRU方式の説明として、適切なものはどれか。
ア：最後に参照されたページを置き換える方式
イ：最後に参照されてからの経過時間が最も長いページを置き換える方式
ウ：最も参照回数の少ないページを置き換える方式
エ：最も古くから存在するページを置き換える方式
練習2
ページング方式の仮想記憶において、ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき、ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると、ページ6をアクセスする時点で置き換えられるページはどれか。ここで、初期状態では主記憶にどのページも存在しないものとする。
[基本情報技術者平成24年秋期 午前問19]ア：1
イ：2
ウ：4
エ：5
練習3
プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて、大きさ6ページのプログラムが実行されたとき、ページフォールトは何回発生するか。ここで、プログラム実行時のページ読込み順序は，0，1，2，3，4，0，2，4，3，1，4，5とする。ページング方式は、LRU(Least Recently Used)とし、初期状態では実メモリにはいずれのページも読み込まれていないものとする。
[応用情報技術者平成28年秋期 午前問18]ア：9
イ：10
ウ：11
エ：12
練習4
仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、追い出すページを選ぶアルゴリズムは、FIFOとLRUの２つを考える。あるタスクのページアクセス順序が「1, 3, 2, 1, 4, 5, 2, 3, 4, 5」のとき、ページを置き換える回数の組合せとして適切なものはどれか。
[基本情報技術者平成29年春期 午前問19]ア：FIFO: 3 LRU: 2
イ：FIFO: 3 LRU: 6
ウ：FIFO: 4 LRU: 3
エ：FIFO: 5 LRU: 4
練習5
ページング方式の仮想記憶において、主記憶に存在しないページをアクセスした場合の処理や状態の順番として、適切なものはどれか。ここで、主記憶には現在、空きのページ枠はないものとする。
[基本情報技術者平成20年秋期 午前問27]ア：置換え対象ページの決定→ページイン→ページフォールト→ページアウト
イ：置換え対象ページの決定→ページフォールト→ページアウト→ページイン
ウ：ページフォールト→置換え対象ページの決定→ページアウト→ページイン
エ：ページフォールト→置換え対象ページの決定→ページイン→ページアウト
練習6
あるプログラムを実行する際のメモリへのアクセスの98.5％がTLB(Translation Lookaside Buffer)から行われる。ページテーブルからのアクセスには 2.0μs、ページフォルトの際には10msのロスタイムが発生する。
ページフォルト率を \( 2.0 \times 10^{-4} \) % とすると、1回のメモリアクセスで発生するロスタイムの平均を有効数字2桁で答えなさい。
練習7
あるプログラムを実行する際のメモリへのアクセスの99％がTLB(Translation Lookaside Buffer)から行われる。ページテーブルからのアクセスには 0.60μs、ページフォルトの際には20msのロスタイムが発生する。
1回のメモリアクセスで発生する平均ロスタイムを 10ns 以下にするためには、ページフォルト率を何%以下にすればよいか有効数字2桁で答えなさい。
６．練習問題の解答
練習1
解答：イ
LRUアルゴリズム → 過去最も参照されなかったページを置き換えるアルゴリズム → 参照されてからの時間が最も長いページを置き換える方式
と言い換えるだけでした。
練習2
解答：エ
ページ枠が4つになっているので注意してください。
実際にページ枠を書いていきページ枠の動きを調べていきます。
1～4回目のページフォルト→空ページを埋めるだけ
5回目 → 1,2,3,4のうち最も長く参照されていないのは1 → 1を置き換え
6回目 → 5,2,3,4のうち最も長く参照されていないのは3 → 3を置き換え
7回目 → 5,2,1,4のうち最も長く参照されていないのは4 → 4を置き換え
8回目 → 5,2,1,3のうち最も長く参照されていないのは5 → 5を置き換え
最後に置き換えられているのは5なので、答えは「エ」の5となります。
練習3
解答：イ
ページフォルトの回数が多くなると間違えやすくなります。
1～3回目 → 空ページ
4回目 → 0,1,2の中で最も長く参照されていないのは0
5回目 → 3,1,2の中で最も長く参照されていないのは1
6回目 → 3,4,2の中で最も長く参照されていないのは2
7回目 → 3,4,0の中で最も長く参照されていないのは3
8回目 → 2,4,0の中で最も長く参照されていないのは0
9回目 → 2,4,3の中で最も長く参照されていないのは2
10回目 → 1,4,3の中で最も長く参照されていないのは3
の合計10回ページフォルトをする。
よって答えは「イ」の10回。
練習4
解答：イ
FIFOは最も古くロードされたデータを犠牲にする方式でしたね。
FIFOとLRUの両方のページテーブルを下に示します。
ページフォルトのページ読み取りのうち、空のページに読み込んだものを△、置き換えたものを×としています。
FIFOの場合
1回目の置き換え：1,3,2のうち一番古いのは1
2回目の置き換え：4,3,2のうち一番古いのは3
3回目の置き換え：4,5,2のうち一番古いのは2
の計3回。
LRUの場合
1回目の置き換え：1,3,2のうち最も長く参照されていないのは3
2回目の置き換え：1,4,2のうち最も長く参照されていないのは2
3回目の置き換え：1,4,5のうち最も長く参照されていないのは1
4回目の置き換え：2,4,5のうち最も長く参照されていないのは4
5回目の置き換え：2,3,5のうち最も長く参照されていないのは5
6回目の置き換え：2,3,4のうち最も長く参照されていないのは2
の合計6回ページフォルトをする。
よって答えは「イ」の「FIFO：3 LRU：6」となる。
練習5
解答：ウ
まずは、ページフォルトを検知しない限り処理は始まりません。
なので、最初は「ページフォルト」を行います。
つぎに、置き換える対象のページをアルゴリズムを使って決め、その次に主記憶上のデータを補助記憶などに退避させ（ページアウト）、必要なページを補助記憶から主記憶上に読み込みます（ページイン）。
なので答えは「ウ」の「ページフォールト→置換え対象ページの決定→ページアウト→ページイン」となります。
練習6
TLBのアクセス速度は高速なので無視。
なので、残りの1.5％がページテーブルからのアクセス、\( 2.0 \times 10^{-4} \) %がページフォルトによるアクセスとなる。
\( 2 \ \mathrm{[ \mu s ]} = 2.0 \times 10^{-6} \ \mathrm{[s]} \) 、\( 10 \mathrm{[ ms ]} = 1.0 \times 10^{-2} \ \mathrm{[s]} \) なので求めるもの（平均ロスタイム）を \( x \) とすると、\[ 98.5 \times 0 + 1.5 \times 2.0 \times 10^{-6} + 1.0 \times 10^{-2} \times 2.0 \times 10^{-4} = 100 \times x \]となる。解くと、\[ 3.0 \times 10^{-6} + 2.0 \times 10^{-6} = 1.0 \times 10^{2} x \] となるので、
\[x = 5.0 \times 10^{-8} \ \mathrm{[s]} \ \ \left( 50 \mathrm{[ns]} \right) \] と計算できる。
練習7
TLBのアクセス速度は高速なので無視。
なので、残りの1.0％がページテーブルからのアクセス、\( x \) %がページフォルトによるアクセスとなる（今回はこの \( x \) を求める問題）。
\( 0.6 \ \mathrm{[ \mu s ]} = 6.0 \times 10^{-7} \ \mathrm{[s]} \) 、\( 20 \mathrm{[ ms ]} = 2.0 \times 10^{-2} \ \mathrm{[s]} \) なので求める \( x \) は、\[ 99.0 \times 0 + 1.0 \times 6.0 \times 10^{-7} + 2.0 \times 10^{-2} \times x = 100 \times 1.0 \times 10^{-8}
\\ 10 \ \mathrm{[ ns ]} = 1.0 \times 10^{-8} \ \mathrm{[s]}
\]となる。解くと、\[ 6.0 \times 10^{-7} + 2.0 \times 10^{-2} x = 1.0 \times 10^{-6} \] となるので、\[ 2.0 \times 10^{-2} x = 4.0 \times 10^{-7} \] より、\[x = 2.0 \times 10^{-5} \ \mathrm{[\%]}\] と計算できる。
７．さらなる演習をしたい人向けに
もう少しページングの練習をしたい人向けに自作の練習問題を持ってきました。
4択（基本情報や応用情報の午前と同じ）にしているので自動採点されます。
挑戦お待ちしております！
８．さいごに
今回は、オペレーティングシステム分野におけるページフォルト、LRUアルゴリズムについてまとめました。
LRUアルゴリズムなどを用いたページングは基本情報、応用情報などにもよくでるので必ず理解しておきましょう！
関連広告・スポンサードリンク
