2019年7月26日 2019年7月26日 18分51秒 Show
スポンサードリンク こんにちは、ももやまです! ★注意★
がまだあまり理解していない人は、この記事を読む前に下の復習記事「仮想記憶とページング」を読むことをおすすめします。 www.momoyama-usagi.com 目次
スポンサードリンク 1.ページフォルトについてページフォルトとは、プログラムを実行するのに必要なページが主記憶(メインメモリ)上に存在しないときに発生する割り込みとなります。 (1) ページフォルトを検知してから置き換えるまでページフォルトの検知は、MMU(Memory Management Unit)がページテーブルにある存在ビットで行います。もし、この存在ビットがリセットされていればページフォルトが発生します(ハードウェア側で)。 ここからはOS内の処理となります。 まずは、空きページがあるかないかを探します。 空きページがあれば、そのまま空きページに必要なページを(ハードディスクなどの)補助記憶装置からページを読み込みます。 空きページがなければ、ページを置きかえます。ページの置き換えには(LRUアルゴリズムなどの)様々ななアルゴリズムが使われます(下のほうで紹介します)。 (置き換えアルゴリズムで選んだ)主記憶のページを補助記憶へ退避させ(ページアウト)、退避させたページに必要なページを補助記憶から読み込みます(ページイン)。 最後に存在ビットをセットし、物理ページ番号を記録します。 (2) 修正ビットの役割ページフォルトの際に変更されていないページにも関わらず補助記憶へ書き出すのは大変無駄ですね。この無駄を防ぐために用意されているのが修正ビットです。 修正ビットは、名前の通りページが変更されたかを示すビットです(ページテーブル内にあります)。 具体的にどのように修正ビットを使うのかについてですが、まずページを書き込む際に修正ビットをセットします。 実際にページを置き換える際に、修正ビットがセットされているかを確認します。修正ビットがセットされていたときは補助記憶装置に書きだしますが、修正ビットがセットされていない場合は補助記憶装置へ書き出さないようにすることで、無駄な補助記憶装置の書き出しを防ぎます。 (3) 参照ビットの役割参照ビットは名前の通りページが参照されるとセットされるビットです。 後程説明するLRUアルゴリズムでは、長い間ページが参照されていないページを置き換えるアルゴリズムですが、長い間ページが参照されていないかを判定するために参照ビットをチェックします。 スポンサードリンク 2.ページ置き換えアルゴリズムページフォルトの際に空きページがなければ、ページを置きかえます。言い換えると、ページが犠牲になってしまいます。 その犠牲になるページをどうやって選ぶか主に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を置き換え 先程と同じく、赤色の部分がページフォルトの際に書き換えたページとなっております。 (3) LRUアルゴリズム(Least Recently Used)実際にページ置き換えの際によく使われるのがLRUアルゴリズムです。 このアルゴリズムは、「過去最も参照されなかったページを置き換えるアルゴリズム」です。 (1)と同じ例で実際にページフォルトの発生箇所と発生回数を見ていきましょう。 4つ目のページフォルト:3,2,1の中で最も参照されたのが古いのは3なので3を置き換え となります。 スポンサードリンク 3.なぜLRUアルゴリズムがよく使われるかLRUはアルゴリズムは実際のページ置き換えでよく使われると書きましたね。 では、なぜLRUアルゴリズムは使われるのでしょうか。 最適解(理論値)なのは将来のページ参照を予測して、将来最も長い間参照されないページを置き換えることですね。 しかし、将来のページを置き換えることは大変困難ですね。 そこで使うのが時間的局所性です。ページの参照には時間的局所性があります。 時間的局所性とは、最近参照されたページは近い将来に参照される可能性が高い性質のことを表します。言い換えると、長い参照されないページは将来的にも参照される可能性は低いといいかえることができますね。 LRUアルゴリズムは、過去最も参照されなかったページを置き換えるアルゴリズムですね。ページの参照には時間的局所性があるので、上で説明した理論値アルゴリズム(将来長い間参照されたかったページを書き換えるアルゴリズム)の近似となっていますね。 なので、他のアルゴリズムに比べてより高い確率で参照するページがメインメモリ内に登録されることを実現でき、ページフォルト回数を減らし、メモリアクセスの遅れを減少させることができます。 なので、LRUアルゴリズムは他のページ置き換えアルゴリズムに比べて優れているため、よく用いられるのです。 4.TLB (Translation Lookaside Buffer)ページ参照速度をさらにあげるため、プログラムを実行する際にはページテーブルにアクセスする前にTLBにアクセスを行います。 TLBとは、「仮想ページが物理メモリ上のどの位置に対応しているか」を高速にアクセスできるレジスタ上に保存しておくことで、仮想ページ番号がTLBに存在するときは高速にアクセスすることができます。 簡単に言うと、ページテーブルのキャッシュです。 アクセス順番としては、 1st:仮想ページ番号がTLBにあるかチェック(あればTLBにアクセス) となります。 5.練習問題では、実際に練習していきましょう。 練習1ページ置換えアルゴリズムにおけるLRU方式の説明として、適切なものはどれか。 ア:最後に参照されたページを置き換える方式 [基本情報技術者試験 平成24年春期 午前問22] 練習2ページング方式の仮想記憶において、ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき、ページ1,2,3,4,5,2,1,3,2,6の順にアクセスすると、ページ6をアクセスする時点で置き換えられるページはどれか。ここで、初期状態では主記憶にどのページも存在しないものとする。 [基本情報技術者平成24年秋期 午前問19] ア:1 練習3プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて、大きさ6ページのプログラムが実行されたとき、ページフォールトは何回発生するか。ここで、プログラム実行時のページ読込み順序は,0,1,2,3,4,0,2,4,3,1,4,5とする。ページング方式は、LRU(Least Recently Used)とし、初期状態では実メモリにはいずれのページも読み込まれていないものとする。 [応用情報技術者平成28年秋期 午前問18] ア:9 練習4仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、追い出すページを選ぶアルゴリズムは、FIFOとLRUの2つを考える。あるタスクのページアクセス順序が「1, 3, 2, 1, 4, 5, 2, 3, 4, 5」のとき、ページを置き換える回数の組合せとして適切なものはどれか。 [基本情報技術者平成29年春期 午前問19] ア:FIFO: 3 LRU: 2 練習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桁で答えなさい。 6.練習問題の解答練習1解答:イ LRUアルゴリズム → 過去最も参照されなかったページを置き換えるアルゴリズム → 参照されてからの時間が最も長いページを置き換える方式 と言い換えるだけでした。 練習2解答:エ ページ枠が4つになっているので注意してください。 1~4回目のページフォルト→空ページを埋めるだけ 最後に置き換えられているのは5なので、答えは「エ」の5となります。 練習3解答:イ ページフォルトの回数が多くなると間違えやすくなります。 1~3回目 → 空ページ の合計10回ページフォルトをする。 よって答えは「イ」の10回。 練習4解答:イ FIFOは最も古くロードされたデータを犠牲にする方式でしたね。 FIFOとLRUの両方のページテーブルを下に示します。 FIFOの場合 1回目の置き換え:1,3,2のうち一番古いのは1 の計3回。 LRUの場合 の合計6回ページフォルトをする。 よって答えは「イ」の「FIFO:3 LRU:6」となる。 練習5解答:ウ まずは、ページフォルトを検知しない限り処理は始まりません。 なので、最初は「ページフォルト」を行います。 つぎに、置き換える対象のページをアルゴリズムを使って決め、その次に主記憶上のデータを補助記憶などに退避させ(ページアウト)、必要なページを補助記憶から主記憶上に読み込みます(ページイン)。 なので答えは「ウ」の「ページフォールト→置換え対象ページの決定→ページアウト→ページイン」となります。 練習6TLBのアクセス速度は高速なので無視。 なので、残りの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) \] と計算できる。 練習7TLBのアクセス速度は高速なので無視。 なので、残りの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} 7.さらなる演習をしたい人向けにもう少しページングの練習をしたい人向けに自作の練習問題を持ってきました。 4択(基本情報や応用情報の午前と同じ)にしているので自動採点されます。 挑戦お待ちしております! forms.gle 8.さいごに今回は、オペレーティングシステム分野におけるページフォルト、LRUアルゴリズムについてまとめました。 LRUアルゴリズムなどを用いたページングは基本情報、応用情報などにもよくでるので必ず理解しておきましょう! 仮想記憶管理のページ入替え方式のうち最後に使われてからの経過時間が最も長いページを入れ替えるものはどれか?LIFO(Last-in First-out)では、最後に追加されたデータを置き換えます。 LRU(Least Recently Used)では、最後に使われてからの経過時間が最も長いページを置き換えます。
プログラムを実行するために主記憶に読み込んだとき,ロード位置に対応してプログラム内のアドレス情報を補正することを示す用語はどれか。?再配置は、プログラムが配置された主記憶上の位置に対応して、プログラム内のアドレス情報を設定することです。
ページング方式の仮想記憶において、ページアクセス時に発生する事象をその回数の多い順に並べたものはどれか。?演習問題 ページング方式の仮想記憶において,ページアクセス時に発生する事象をその回数の多い順に並べたものはどれか。 ここで,A ≥ Bは,A の回数が B の回数以上,A = B は,A と B の回数が常に同じであることを表す。 正解は,ページフォールト = ページイン ≥ ページアウトである。
ページング方式の仮想記憶を用いることによる効果はどれか。 (平成26年度春期基本情報問16)?基本情報技術者平成26年春期 午前問16
頻繁に使用されるページを仮想記憶に置くことによって,アクセス速度を主記憶へのアクセスよりも速めることができる。 プログラムの大きさに応じて大小のページを使い分けることによって,主記憶を無駄なく使用できる。
|