基本情報技術者 2013年 春期 午後 問02
仮想記憶方式に関する次の記述を読んで、設問1〜3に答えよ。
OSの主記憶管理において、仮想記憶方式は、OSが提供する論理的な記憶領域（以下、仮想記憶という）上のアドレスと主記憶上の物理的なアドレスを対応付けて管理する方式である。仮想記憶方式では、補助記憶装置を仮想記憶として用いるので、仮想記憶上に主記憶の容量を超えるプログラムを格納することができる。仮想記憶上のアドレス空間を仮想アドレス空間、主記憶上のアドレス空間を物理アドレス空間と呼び、それぞれの空間の記憶場所を仮想アドレスと物理アドレスで指定する。
仮想記憶方式の一つに、ページング方式がある。ページング方式は、仮想アドレス空間と物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき、ページ単位でアドレス空間を管理する。ページング方式による仮想アドレス空間のページと物理アドレス空間のページの対応例を、図1に示す。図1では、補助記憶装置に格納されているプログラムAはa1、a2、a3、a4、a5に分割されて、仮想ページ番号1〜5のページに格納されている。
仮想アドレス空間及び物理アドレス空間の各ページには、先頭から順に番号を付け、それぞれを仮想ページ番号、物理ページ番号と呼ぶ。仮想ページと物理ページの対応は、ページテーブルで管理する。ページテーブルの要素の個数は仮想ページの個数と同じであり、各要素が仮想ページの1ページに対応している。ページテーブルでは、仮想ページの内容が物理アドレス空間にも存在しているかどうかを示すビット（以下、存在ビットという）と物理ページ番号が管理されている。存在ビットは、ページが存在しているとき1、存在していないとき0とする。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プログラムの実行過程で存在ビットを調べ、プログラムの実行に必要なページがaに存在していないときには、ページフォールトという割込みが発生する。ページフォールトが発生すると、ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには、ページインしてから最も時間が経過しているページを置換え対象とするFIFOアルゴリズムや、参照されていない時間が最も長いページを置換え対象とするbアルゴリズムなどがある。
解答群
ア：LFU
イ：LIFO
ウ：LRU
エ：仮想アドレス空間
オ：物理アドレス空間
模範解答
a：オ、b：ウ
解説
解答の導き方
まず、aには「必要なページが存在していない場所」が入ります。
本文では、仮想アドレス空間を「仮想記憶上のアドレス空間」、物理アドレス空間を「主記憶上のアドレス空間」と説明しています。さらに、ページテーブルの存在ビットは、仮想ページの内容が「物理アドレス空間にも存在しているかどうか」を示します。
つまり、プログラムの実行に必要なページの存在ビットが0なら、そのページは主記憶上にありません。この状態で必要なページを使おうとするとページフォールトが発生します。したがって、aは「物理アドレス空間」です。
次に、bにはページ置換えアルゴリズムの名前が入ります。本文では、FIFO（First In, First Out：先に入ったものを先に出す方式）について、ページインしてから最も時間が経過しているページを置換え対象とすると説明しています。
これに対して、bの手掛かりは「参照されていない時間が最も長いページ」です。これは、最後に参照されてから最も長い時間が経過したページを置換えるLRU（Least Recently Used：最も最近使われていないページを対象にする方式）の説明です。
LFU（Least Frequently Used：参照された回数が最も少ないページを対象にする方式）は、参照されていない時間ではなく、参照回数に注目します。LIFO（Last In, First Out：最後に入ったものを先に出す方式）は、ページを入れた順番に注目する方式です。そのため、bには当てはまりません。
誤りやすいポイント
- 仮想アドレス空間と物理アドレス空間を混同しないようにします。仮想アドレス空間はOSが提供する論理的な領域で、物理アドレス空間は主記憶上の領域です。ページフォールトは、必要なページが物理アドレス空間にないときに発生します。
- LRUとLFUを取り違えないようにします。LRUは「最後に参照されてからの時間」、LFUは「参照された回数」に注目します。
- FIFOとLRUも別の基準です。FIFOは「ページインした順番」、LRUは「最後に参照した時点」を基準に置換え対象を選びます。
FAQ
Q: ページフォールトが起きると、プログラムは必ず異常終了しますか？
A: いいえ。ページフォールトは、必要なページが主記憶にないことを知らせる割込みです。OSがページを主記憶に読み込む処理を行うため、ページフォールトが発生しただけで必ず異常終了するわけではありません。
A: いいえ。ページフォールトは、必要なページが主記憶にないことを知らせる割込みです。OSがページを主記憶に読み込む処理を行うため、ページフォールトが発生しただけで必ず異常終了するわけではありません。
Q: LRUは、参照回数が少ないページを選ぶ方式ですか？
A: いいえ。LRUは、最後に参照されてから最も長い時間が経過したページを選びます。参照回数が最も少ないページを選ぶのはLFUです。
A: いいえ。LRUは、最後に参照されてから最も長い時間が経過したページを選びます。参照回数が最も少ないページを選ぶのはLFUです。
Q: ページテーブルは何を管理していますか？
A: 仮想ページの内容が主記憶にあるかどうかと、主記憶にある場合はどの物理ページに対応するかを管理しています。
A: 仮想ページの内容が主記憶にあるかどうかと、主記憶にある場合はどの物理ページに対応するかを管理しています。
関連キーワード: 仮想記憶、ページング方式、ページテーブル、ページフォールト、FIFO、LRU
設問2：
問題文を見る プログラムAを実行するために割り当てられた物理アドレス空間の物理ページの個数が3の場合を考える。プログラムAの実行過程において、物理アドレス空間にa1、a2、a3が存在している状態でa4を参照するとページフォールトが発生する。このページフォールトが発生した後の処理の流れとして適切な答えを、解答群の中から選べ。ここで、解答群中の処理は左から右に向かって行うものとする。
【処理の単位】
① 退避させるページをページアウトする。
② ページ置換えアルゴリズムによって、物理アドレス空間からページアウトするページを決定する。
③ 実行に必要なページをページインする。
④ ページアウトしたページに対応するページテーブルの要素の存在ビットを0にする。
⑤ ページインしたページに対応するページテーブルの要素の存在ビットを1にする。
⑥ ページアウトしたページに対応するページテーブルの要素の物理ページ番号を設定する。
⑦ ページインしたページに対応するページテーブルの要素の物理ページ番号を設定する。
解答群
ア：①→②→③→④→⑤→⑥
イ：①→③→②→④→⑦→⑤
ウ：②→①→④→③→⑤→⑥
エ：②→①→④→③→⑦→⑤
オ：②→③→①→④→⑤→⑥
カ：②→③→⑤→⑥→①→④
模範解答
エ
解説
解答の導き方
まず、ページフォールトとは、プログラムが使おうとしたページが主記憶にないときに起きる処理です。主記憶は、実行中のプログラムやデータを置く記憶領域です。
問題では、主記憶にa1、a2、a3がある状態でa4を参照します。a4は主記憶にないため、ページフォールトが発生します。さらに、プログラムAに割り当てられた物理ページは3個で、すでにすべて使われています。そのため、a4を読み込む前に、主記憶のページを1個空ける必要があります。
ここから、処理を順に考えます。
-
主記憶から追い出すページを決めます。
どのページを追い出すかは、ページ置換えアルゴリズム（主記憶から追い出すページを選ぶ方法）で決めます。これは②です。 -
決めたページをページアウトします。
ページアウトとは、主記憶にあるページを補助記憶装置へ退避させることです。まず退避させることで、そのページが使っていた物理ページを再利用できるようにします。これは①です。 -
ページアウトしたページの存在ビットを0にします。
ページテーブルは、仮想ページと物理ページの対応を記録する表です。本文には「存在ビットは、ページが存在しているとき1、存在していないとき0」とあります。ページアウトしたページは主記憶にないので、対応する存在ビットを0にします。これは④です。 -
参照されたページをページインします。
ページインとは、補助記憶装置にあるページを主記憶へ読み込むことです。退避によって空いた物理ページに、a4を読み込みます。これは③です。 -
ページインしたページの物理ページ番号を設定します。
a4を読み込んだ物理ページがどれなのかを、ページテーブルに記録します。これは⑦です。 -
ページインしたページの存在ビットを1にします。
a4が主記憶にある状態になったので、対応する存在ビットを1にします。これは⑤です。
したがって、処理の順序は ②→①→④→③→⑦→⑤ となり、解答群ではエです。
なお、⑥は「ページアウトしたページ」の要素に物理ページ番号を設定する処理です。ページアウト後に主記憶へ読み込まれるページは、ページアウトしたページではなく、今回参照されたページです。そのため、物理ページ番号を設定するのは⑥ではなく⑦です。
誤りやすいポイント
-
ページインを先に行うと思い込むこと
物理ページが3個とも使われているため、先にページアウトして空きを作る必要があります。 -
ページアウトしたページと、ページインしたページを混同すること
ページアウトするのは、主記憶から追い出すページです。ページインするのは、今回読み込む必要があるページです。 -
存在ビットを設定する対象を間違えること
ページアウトしたページの存在ビットは0にし、ページインしたページの存在ビットは1にします。 -
物理ページ番号を設定する対象を間違えること
再利用する物理ページ番号を設定するのは、主記憶へ読み込んだページの要素です。したがって⑦を使います。
FAQ
Q：ページフォールトが起きるのは、プログラムに誤りがあるからですか？
A：必ずしもそうではありません。参照したページが主記憶になく、補助記憶装置にある場合にも発生します。必要なページをページインすれば、処理を続けられます。
A：必ずしもそうではありません。参照したページが主記憶になく、補助記憶装置にある場合にも発生します。必要なページをページインすれば、処理を続けられます。
Q：ページアウトしたページは、もう使えなくなるのですか？
A：いいえ。ページアウトしたページは補助記憶装置に退避されています。後で必要になれば、ページインして再び主記憶に読み込めます。
A：いいえ。ページアウトしたページは補助記憶装置に退避されています。後で必要になれば、ページインして再び主記憶に読み込めます。
Q：ページインしたページの存在ビットを、物理ページ番号より先に1にしてはいけないのですか？
A：存在ビットを1にすると、そのページが主記憶にあるものとして扱われます。先に物理ページ番号を設定してから存在ビットを1にすれば、ページテーブルの対応を整えてから利用可能な状態にできます。
A：存在ビットを1にすると、そのページが主記憶にあるものとして扱われます。先に物理ページ番号を設定してから存在ビットを1にすれば、ページテーブルの対応を整えてから利用可能な状態にできます。
関連キーワード: 仮想記憶、ページング方式、ページフォールト、ページテーブル、ページイン、ページアウト
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
ページ置換えアルゴリズムとしてFIFOアルゴリズムを採用する。プログラムの実行過程で仮想ページが次の順で参照されるとき、物理ページの個数が3の場合のページフォールトの回数はc回である。そして、物理ページの個数を4に増やした場合のページフォールトの回数はd回である。ここで、プログラムの実行開始時点では、物理アドレス空間にはどのページも存在していないものとする。
【仮想ページの参照順を示す仮想ページ番号の並び】
1 → 4 → 3 → 2 → 1 → 4 → 5 → 1 → 4 → 3 → 2 → 5 → 1
解答群
ア：8
イ：9
ウ：10
エ：11
オ：12
模範解答
c：ウ、d：エ
解説
解答の導き方
この問題では、仮想ページが参照されたとき、主記憶にそのページがあるかを順番に確認します。
ページフォールトとは、参照された仮想ページが主記憶にないため、補助記憶装置から主記憶へ読み込む必要がある状態です。物理ページは、その読み込み先となる主記憶の領域です。
FIFOアルゴリズム（First In, First Out：先に入ったものを先に出す方法）では、主記憶がいっぱいのときにページフォールトが起きると、最も早く読み込まれたページを追い出します。すでに主記憶にあるページが参照されても、読み込まれた順番は変わりません。
以下の表では、物理ページにあるページを「古い順→新しい順」で示します。「—」は空き領域です。
物理ページの個数が3の場合
ページフォールトは、参照順のうち、1、4、3、2、1、4、5、3、2、1のときに起きています。したがって、回数は10回です。
物理ページの個数が4の場合
最初の4回は、主記憶にページがないためページフォールトになります。その後は、1と4の参照だけがヒットし、残りの7回はページフォールトです。合計すると、回です。
誤りやすいポイント
-
ページフォールトとページの入替えを混同しないこと
ページフォールトは、参照したページが主記憶にないときに起きます。空き領域があればそこへ読み込み、空き領域がなければFIFOの順番に従って古いページを追い出します。 -
ヒットしたページを新しい順に移動させないこと
FIFOでは、ページが参照されても読み込まれた順番は変わりません。参照された順番を基準に入替えを行う方式とは異なります。 -
ページ数が増えればページフォールトが必ず減る、とは限らないこと
この問題では、FIFOの入替え順が変わるため、物理ページの個数が3の場合より4の場合のほうがページフォールトの回数が多くなります。
FAQ
Q: ページが主記憶にあった場合、FIFOの順番は変わりますか？
A: 変わりません。FIFOでは、ページを読み込んだ順番で古いページを決めます。参照されただけでは順番を更新しません。
A: 変わりません。FIFOでは、ページを読み込んだ順番で古いページを決めます。参照されただけでは順番を更新しません。
Q: 物理ページの個数が4の場合に、ページフォールトの回数が増えるのはなぜですか？
A: FIFOでは、主記憶に保持できるページ数が変わると、追い出されるページの順番も変わります。この参照順では、その変化によって後の参照で必要なページが主記憶から追い出され、ページフォールトが増えます。
A: FIFOでは、主記憶に保持できるページ数が変わると、追い出されるページの順番も変わります。この参照順では、その変化によって後の参照で必要なページが主記憶から追い出され、ページフォールトが増えます。
Q: 最初の参照では、なぜページフォールトが起きますか？
A: 問題文では、実行開始時点で主記憶にページがないとしています。そのため、最初に参照するページは必ず主記憶になく、読み込む必要があります。
A: 問題文では、実行開始時点で主記憶にページがないとしています。そのため、最初に参照するページは必ず主記憶になく、読み込む必要があります。
関連キーワード: 仮想記憶、ページング方式、ページフォールト、FIFOアルゴリズム、ページ置換えアルゴリズム
