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

　OSの主記憶管理において，仮想記憶方式は，OSが提供する論理的な記憶領域(以下，仮想記憶という)上のアドレスと主記憶上の物理的なアドレスを対応付けて管理する方式である。仮想記憶方式では，補助記憶装置を仮想記憶として用いるので，仮想記憶上に主記憶の容量を超えるプログラムを格納することができる。仮想記憶上のアドレス空間を仮想アドレス空間，主記憶上のアドレス空間を物理アドレス空間と呼び，それぞれの空間の記憶場所を仮想アドレスと物理アドレスで指定する。
　仮想記憶方式の一つに，ページング方式がある。ページング方式は，仮想アドレス空間と物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき，ページ単位でアドレス空間を管理する。ページング方式による仮想アドレス空間のページと物理アドレス空間のページの対応例を，図1に示す。図1では，補助記憶装置に格納されているプログラム A は a1，a2，a3，a4，a5 に分割されて，仮想ページ番号1～5のページに格納されている。　仮想アドレス空間及び物理アドレス空間の各ページには，先頭から順に番号を付け，それぞれを仮想ページ番号，物理ページ番号と呼ぶ。仮想ページと物理ページの対応は，ページテーブルで管理する。ページテーブルの要素の個数は仮想ページの個数と同じであり，各要素が仮想ページの1ページに対応している。ページテーブルでは，仮想ページの内容が物理アドレス空間にも存在しているかどうかを示すビット(以下，存在ビットという)と 物理ページ番号が管理されている。存在ビットは，ページが存在しているとき1，存在していないとき0とする。

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

　プログラムの実行過程で存在ビットを調べ，プログラムの実行に必要なページがaに存在していないときには，ページフォールトという割込みが発生する。ページフォールトが発生すると，ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには，ページインしてから最も時間が経過しているページを置換え対象とする FIFO アルゴリズムや，参照されていない時間が最も長いページを置換え対象とするbアルゴリズムなどがある。

a，b に関する解答群

• LFU
• LIFO
• LRU
• 仮想アドレス空間
• 物理アドレス空間

プログラム A を実行するために割り当てられた物理アドレス空間の物理ページの個数が3の場合を考える。プログラム A の実行過程において，物理アドレス空間に a1，a2，a3 が存在している状態で a4 を参照するとページフォールトが発生する。このページフォールトが発生した後の処理の流れとして適切な答えを，解答群の中から選べ。ここで，解答群中の処理は左から右に向かって行うものとする。

【処理の単位】

1. 退避させるページをページアウトする。
2. ページ置換えアルゴリズムによって，物理アドレス空間からページアウトするページを決定する。
3. 実行に必要なページをページインする。
4. ページアウトしたページに対応するページテーブルの要素の存在ビットを 0 にする。
5. ページインしたページに対応するぺージテーブルの要素の存在ビットを 1 にする。
6. ページアウトしたページに対応するページテーブルの要素の物理ページ番号を設定する。
7. ページインしたページに対応するページテーブルの要素の物理ページ番号を設定する。

解答群

• ①→②→③→④→⑤→⑥
• ①→③→②→④→⑦→⑤
• ②→①→④→③→⑤→⑥
• ②→①→④→③→⑦→⑤
• ②→③→①→④→⑤→⑥
• ②→③→⑤→⑥→①→④

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

　ページ置換えアルゴリズムとして FIFO アルゴリズムを採用する。プログラムの実行過程で仮想ページが次の順で参照されるとき，物理ページの個数が 3 の場合のページフォールトの回数はc回である。そして，物理ページの個数を 4 に増やした場合のページフォールトの回数はd回である。ここで，プログラムの実行開始時点では，物理アドレス空間にはどのページも存在していないものとする。

【仮想ページの参照順を示す仮想ページ番号の並び】
　　1→4→3→2→1→4→5→1→4→3→2→5→1

c，d に関する解答群

• 8
• 9
• 10
• 11
• 12