第１種情報処理平成１２年問２３

問　題

　仮想記憶管理におけるページ置換えアルゴリズムとして、LRU方式を
採用する。参照かつ更新されるページ番号の順番が、
２→３→５→８→２→３→６→２→３→５→１→６で、実記憶のページ
枠が４のとき、ページフォールトに伴って発生するページアウトは何回
か。ここで、初期状態では、実記憶にはいずれのページも読み込まれて
いないものとする。

　ア　３

　イ　４

　ウ　５

　エ　６

解　説

難易度　★
解答

　イ　４


長　池「この問題は仮想記憶のページ置換に関する問題だね。」

ユウト「仮想記憶って何ですか？」

長　池「仮想記憶っていうのは、主記憶が不足していても
　　　　プログラムが動作するようにする技術のことだよ。

　　　　ハードディスクをメモリの一部とみなして、
　　　　プログラム実行に十分なメモリ空間を実現できるんだ。

　　　　仮想記憶では、プログラムをページ単位で分割したものを
　　　　メモリとハードディスクの間で入れ替えを行うスワッピング
　　　　が発生するよ。」

ユウト「メモリ上に必要なページがない時に、その不要なページを
　　　　排除して、ハードディスクから必要なページを読み込むという
　　　　ことでしょうか？」

長　池「そうだよ。すごいね。
　　　　ページの置き換えにはいくつかの方式があるんだ。」

ユウト「この問題では、LRU方式ってなっていますね。」

長　池「そうだね。その他の方式は後で説明するとして、
　　　　ここではそのLRU方式について見ていこう。

　　　　また英語の略称が出てきたね。
　　　　これは何の略か分かるかな？」

ユウト「はい。これは調べてきました。
　　　　Least Reacently Usedです。」

長　池「そうだね。『もっとも最近使われていない』というのが直訳だね。
　　　　つまり、もっとも長い時間使用されなかったページを選択するんだ。」

ユウト「なるほど。これで分かったような気がします。」

長　池「それじゃ解いてごらん。」

ユウト「実記憶のページ枠が４だから、箱を４つ用意します。

　　　　『初期状態では、実記憶にはいずれのページも読み込まれて
　　　　いないものとする』という条件があるので、まず

　　　　古　　　　　新
　　　　２　３　５　８

　　　　が入ります。


　　　　次の数は、２ですから、ページフォルトは発生せず、

　　　　３　５　８　２

　　　　となりますね。


　　　　次の数は、３ですから、これもページフォルトは発生しません。

　　　　５　８　２　３

　　　　となります。


　　　　次の数は、６です。これは４つの数にありませんので、
　　　　ページフォルトが発生します。ページフォルト１回目。

　　　　８　２　３　６


　　　　次の数は、２です。これはページフォルトは発生しません。

　　　　８　３　６　２

　　　　となります。


　　　　次の数は、３です。これもページフォルトは発生しません。

　　　　８　６　２　３


　　　　次の数は、５です。これはページフォルトが発生します。
　　　　ページフォルト２回目です。

　　　　６　２　３　５


　　　　次の数は、１です。これもページフォルトが発生します。
　　　　ページフォルト３回目です。

　　　　２　３　５　１


　　　　最後の数ですね。６は、ページフォルトが発生します。
　　　　ページフォルト４回目です。

　　　　３　５　１　６


　　　　以上ですね。結果はページフォルト４回でした。
　　　　正解はイでよろしいでしょうか。」


長　池「よし。正解だよ。

　　　　それでは、最後にページの置き換えアルゴリズムについてみておこう。


　　　　◇LRU方式　とは。。。

　　　　　主記憶上にあるページのうち、最後に参照されてからその時点
　　　　　までの経過時間がもっとも長いものを追い出す方式です。


　　　　◇LFU方式　とは。。。

　　　　　主記憶上にあるページのうち、最も参照回数が少ないものを
　　　　　追い出す方式です。


　　　　◇FIFO方式　とは。。。

　　　　　主記憶上にあるページのうち、最も長くメモリ上に存在する
　　　　　ものを追い出す方式です。」

ユウト「ありがとうございました。」