基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

仮想記憶方式に関する次の記述を読んで，設問1～3に答えよ。

　仮想記憶方式は，OSが提供する論理的な記憶領域(以下，仮想記憶という)上のアドレスと物理的な主記憶上のアドレスを対応付けて管理する方式である。仮想記憶方式では，補助記憶装置を仮想記憶の実装媒体として用いることによって，プログラムが主記憶の容量を超える大きさであっても，これを仮想記憶上のデータとして格納し，実行することができる。仮想記憶上のアドレス空間を仮想アドレス空間，主記憶上のアドレス空間を物理アドレス空間と呼び，それぞれの空間における記憶場所は仮想アドレス，物理アドレスで指定する。

　仮想記憶方式の実現方法の一つにページング方式がある。この方式では，仮想アドレス空間と物理アドレス空間をそれぞれ仮想ページ，物理ページと呼ぶ固定長の領域に分割し，管理する。ページング方式では，プログラムの実行過程で，実行に必要な仮想ページのデータが物理アドレス空間に存在していないときは，そのデータが格納されている仮想ページからデータを物理ページに読み込んで利用する。

　ページング方式のページ管理方法の例を次の(1)～(3)に示す。

• 仮想アドレス空間及び物理アドレス空間の各ページには，1から順に番号を付け，それぞれを仮想ページ番号，物理ページ番号と呼ぶ。
• 仮想ページと物理ページの対応は，ページテーブルで管理する。ページテーブルの各要素は仮想ページと1対1に対応付けられており，要素の個数は仮想ページの個数と同じである。
• ページテーブルには，仮想ページのデータが物理アドレス空間に存在しているかどうかを示すビット(以下，存在ビットという)と，存在している場合に対応する物理ページ番号を登録する領域がある。存在ビットは，当該仮想ページのデータが物理アドレス空間に存在している場合は1，存在していない場合は0である。

　仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例を，図1に示す。ここで，図1中のA～Hは，仮想ページ及び物理ページに格納されているデータを示す。

図1中の　に入れる正しい答えを，解答群の中から選べ。ここで，a1～a4に入れる答えは，aに関する解答群の中から組合せとして正しいものを選ぶものとする。

次の記述中の　に入れる適切な答えを，解答群の中から選べ。ここで，b1とb2，c1とc2に入れる答えは，それぞれb，cに関する解答群の中から組合せとして適切なものを選ぶものとする。

　ページング方式では，プログラムの実行過程で，実行に必要なデータが物理アドレス空間に存在していないときには，ページフォールトという割込みが発生する。ページフォールトが発生すると，仮想ページに格納されているデータを物理ページに読み込む処理(以下，ページフォールト割込み処理という)を行う。

〔ページフォールト割込み処理〕

• 物理ページのうち，仮想ページと対応付けられていない物理ページ(以下，空きページという)を一つ探す。
• 空きページがなかった場合，空きページにするb1ページを一つ選び，その選んだページに格納されているデータをb2。その後，対応するページテーブルの要素の存在ビットを0にする。これによって空きページを確保する。
• 空きページがあった場合，又はなかった場合では(2)の処理後に，その空きページにプログラムの実行に必要なc1ページに格納されているデータをc2。その後，対応するページテーブルの要素に物理ページ番号を登録して，その存在ビットを1にする。

次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　ページング方式において，ページフォールトの発生回数を少なくするためには，どの物理ページを空きページにするかが重要になる。一般的に知られているアルゴリズムであるFIFOとLRUについて，あるプログラムの実行過程で仮想ページが次の順で参照される場合を考える。ここで，プログラムの実行開始時点では，このプログラムの実行のために割り当てられた物理ページは全て空きページである。

〔仮想ページの参照順〕
　4→2→1→5→4→2→3→4→2→1→5→3→5

　FIFOを用いると，割り当てられた物理ページの個数が3のときは，ページフォールトの発生回数は9回である。物理ページの個数が4ならば，物理ページの個数が3のときと比べて，ページフォールトの発生回数はd。
　一方，LRUを用いると，物理ページの個数が3のときは，ページフォールトの発生回数は10回である。物理ページの個数が4ならば，物理ページの個数が3のときと比べて，ページフォールトの発生回数はe。