基本情報技術者 2019年 春期 午後 問02
仮想記憶方式に関する次の記述を読んで、設問1〜3に答えよ。
仮想記憶方式は、OSが提供する論理的な記憶領域（以下、仮想記憶という）上のアドレスと物理的な主記憶上のアドレスを対応付けて管理する方式である。仮想記憶方式では、補助記憶装置を仮想記憶の実装媒体として用いることによって、プログラムが主記憶の容量を超える大きさであっても、これを仮想記憶上のデータとして格納し、実行することができる。仮想記憶上のアドレス空間を仮想アドレス空間、主記憶上のアドレス空間を物理アドレス空間と呼び、それぞれの空間における記憶場所は仮想アドレス、物理アドレスで指定する。
仮想記憶方式の実現方法の一つにページング方式がある。この方式では、仮想アドレス空間と物理アドレス空間をそれぞれ仮想ページ、物理ページと呼ぶ固定長の領域に分割し、管理する。ページング方式では、プログラムの実行過程で、実行に必要な仮想ページのデータが物理アドレス空間に存在していないときは、そのデータが格納されている仮想ページからデータを物理ページに読み込んで利用する。
ページング方式のページ管理方法の例を次の(1)〜(3)に示す。
(1) 仮想アドレス空間及び物理アドレス空間の各ページには、1から順に番号を付け、それぞれを仮想ページ番号、物理ページ番号と呼ぶ。
(2) 仮想ページと物理ページの対応は、ページテーブルで管理する。ページテーブルの各要素は仮想ページと1対1に対応付けられており、要素の個数は仮想ページの個数と同じである。
(3) ページテーブルには、仮想ページのデータが物理アドレス空間に存在しているかどうかを示すビット（以下、存在ビットという）と、存在している場合に対応する物理ページ番号を登録する領域がある。存在ビットは、当該仮想ページのデータが物理アドレス空間に存在している場合は1、存在していない場合は0である。
仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例を、図1に示す。ここで、図1中のA〜Hは、仮想ページ及び物理ページに格納されているデータを示す。
設問1：
問題文を見る 図1中のに入れる正しい答えを、解答群の中から選べ。ここで、a1〜a4に入れる答えは、aに関する解答群の中から組合せとして正しいものを選ぶものとする。
aに関する解答群
模範解答
a：ウ
解説
解答の導き方
この設問では、仮想ページのデータが物理アドレス空間のどの物理ページにあるかを、図1から読み取ります。
仮想ページは、仮想アドレス空間を分割した領域です。物理ページは、主記憶を分割した領域です。ページテーブルは、仮想ページと物理ページの対応を記録する表です。問題文には「ページテーブルの各要素は仮想ページと1対1に対応付けられて」とあります。そのため、ページテーブルのは仮想ページ番号1、は仮想ページ番号2に対応します。
図1では、仮想ページと物理ページの内容が、次のように対応しています。
例えば、仮想ページ番号1の内容はAです。物理アドレス空間でAがあるのは物理ページ番号2なので、には2が入ります。同じように、仮想ページ番号2の内容Bは物理ページ番号5にあるため、には5が入ります。
この手順で確認すると、からには順に2、5、7、3が入ります。この組合せに当たるのはウです。
誤りやすいポイント
- 仮想ページ番号と物理ページ番号を同じ順番だと思わないようにしましょう。仮想ページ番号1のデータが、物理ページ番号1にあるとは限りません。
- ページ番号ではなく、図1に書かれたデータの内容を手掛かりに対応を探します。例えば、Aがある仮想ページとAがある物理ページを対応付けます。
- 存在ビットは、データが物理アドレス空間にあるかどうかを示します。問題文では、存在ビットが1ならデータが存在するとされています。物理ページ番号そのものを示す値ではありません。
FAQ
Q: 仮想ページ番号と物理ページ番号が異なるのはなぜですか？
A: 仮想ページのデータを、物理アドレス空間のどこに置くかは別々に決められるからです。そのため、データの内容を手掛かりに対応を確認します。
A: 仮想ページのデータを、物理アドレス空間のどこに置くかは別々に決められるからです。そのため、データの内容を手掛かりに対応を確認します。
Q: ページテーブルの存在ビットが1なら、何が分かりますか？
A: その仮想ページのデータが物理アドレス空間に存在することが分かります。物理ページ番号は、ページテーブルの別の領域で確認します。
A: その仮想ページのデータが物理アドレス空間に存在することが分かります。物理ページ番号は、ページテーブルの別の領域で確認します。
Q: 図1で仮想ページ番号5以降の対応を求めなくてよいのはなぜですか？
A: この設問で答えるのはからです。それぞれ仮想ページ番号1から4に対応するため、その4ページのデータを確認すれば解けます。
A: この設問で答えるのはからです。それぞれ仮想ページ番号1から4に対応するため、その4ページのデータを確認すれば解けます。
関連キーワード: 仮想記憶、ページング方式、仮想ページ、物理ページ、ページテーブル、存在ビット
設問2：
問題文を見る 次の記述中のに入れる適切な答えを、解答群の中から選べ。ここで、b1とb2、c1とc2に入れる答えは、それぞれb、cに関する解答群の中から組合せとして適切なものを選ぶものとする。
ページング方式では、プログラムの実行過程で、実行に必要なデータが物理アドレス空間に存在していないときには、ページフォールトという割込みが発生する。ページフォールトが発生すると、仮想ページに格納されているデータを物理ページに読み込む処理（以下、ページフォールト割込み処理という）を行う。
〔ページフォールト割込み処理〕
(1) 物理ページのうち、仮想ページと対応付けられていない物理ページ（以下、空きページという）を一つ探す。
(2) 空きページがなかった場合、空きページにするb1ページを一つ選び、その選んだページに格納されているデータをb2。その後、対応するページテーブルの要素の存在ビットを0にする。これによって空きページを確保する。
(3) 空きページがあった場合、又はなかった場合では(2)の処理後に、その空きページにプログラムの実行に必要なc1ページに格納されているデータをc2。その後、対応するページテーブルの要素に物理ページ番号を登録して、その存在ビットを1にする。
bに関する解答群
cに関する解答群
cに関する解答群
模範解答
b：エ、c：ア
解説
解答の導き方
この問題では、ページフォールトが起きたときに、空きページがない場合の処理と、必要なデータを空きページに読み込む処理を考えます。
-
仮想ページと物理ページの役割を確認します。
仮想ページは、プログラムのデータを仮想記憶上で分けた区画です。物理ページは、実際の主記憶を分けた区画です。OS（Operating System：コンピュータ全体を管理する基本ソフトウェア）は、ページテーブル（仮想ページと物理ページの対応を記録する表）を使って、両者の対応を管理します。 -
ページフォールトが起きる理由を確認します。
ページフォールトとは、プログラムが使おうとした仮想ページのデータが、物理アドレス空間にないときに発生する割込みです。必要なデータは補助記憶装置（主記憶より大容量で、データを保存しておく装置）に置かれているため、物理ページに読み込む必要があります。 -
空きページがない場合に何をするか考えます。
空きページがないときは、現在使われている物理ページの一つを選び、その中身を補助記憶装置に書き出します。こうすれば、その物理ページを空きページとして使えるようになります。
選ぶのは、仮想ページではなく、空きページにするための物理ページです。また、物理ページの中身を補助記憶装置に残すので、書き出す処理になります。したがって、b1は「物理」、b2は「補助記憶装置に書き出す」で、選択肢は「エ」です。 -
空きページに必要なデータを読み込む方法を考えます。
空きページに入れるのは、実行に必要なデータが格納されている仮想ページです。そのデータは補助記憶装置から物理ページへ読み込みます。読み込み後は、ページテーブルに物理ページ番号を登録し、存在ビットを1にします。
したがって、c1は「仮想」、c2は「補助記憶装置から読み込む」で、選択肢は「ア」です。
誤りやすいポイント
-
仮想ページと物理ページを取り違える
物理ページは主記憶上の区画です。空きページを作るために選ぶのは物理ページです。一方、実行に必要なデータが格納されているのは仮想ページです。 -
書き出しと読み込みを逆にする
使っていた物理ページを空けるときは、その中身を補助記憶装置に書き出します。必要な仮想ページを物理ページに入れるときは、補助記憶装置から読み込みます。 -
ページフォールトを、仮想ページ自体が存在しない状態と考える
ページフォールトは、必要な仮想ページのデータが物理アドレス空間にない状態です。そのデータを物理ページに読み込むため、ページフォールト割込み処理を行います。
FAQ
Q: 空きページにする物理ページの存在ビットを0にするのはなぜですか？
A: その物理ページに対応していた仮想ページのデータは、物理アドレス空間からなくなるためです。ページテーブルに「物理アドレス空間に存在しない」と記録します。
A: その物理ページに対応していた仮想ページのデータは、物理アドレス空間からなくなるためです。ページテーブルに「物理アドレス空間に存在しない」と記録します。
Q: 空きページが初めからある場合も、補助記憶装置への書き出しが必要ですか？
A: 必要ありません。書き出しは、空きページがないときに、使用中の物理ページを空けるための処理です。
A: 必要ありません。書き出しは、空きページがないときに、使用中の物理ページを空けるための処理です。
Q: 補助記憶装置から読み込んだ後、ページテーブルを更新するのはなぜですか？
A: 読み込んだデータがどの物理ページに入ったかを記録し、以後その仮想ページのデータを使うときに、対応する物理ページを見つけられるようにするためです。
A: 読み込んだデータがどの物理ページに入ったかを記録し、以後その仮想ページのデータを使うときに、対応する物理ページを見つけられるようにするためです。
関連キーワード: 仮想記憶、ページング方式、仮想ページ、物理ページ、ページテーブル、ページフォールト
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
ページング方式において、ページフォールトの発生回数を少なくするためには、どの物理ページを空きページにするかが重要になる。一般的に知られているアルゴリズムである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。
d, eに関する解答群
ア：1回増える
イ：1回減る
ウ：2回増える
エ：2回減る
オ：3回増える
カ：3回減る
キ：4回増える
ク：4回減る
ケ：変わらない
模範解答
d：ア、e：エ
解説
解答の導き方
この設問では、割り当てる物理ページを3個から4個に増やしたとき、ページフォールトの回数がどう変わるかを調べます。ページフォールトとは、参照した仮想ページが主記憶にないため、読み込む必要が生じることです。
問題文には「実行開始時点では、このプログラムの実行のために割り当てられた物理ページは全て空きページ」とあります。つまり、最初に参照するページから順に、空いている場所へ読み込みます。場所が埋まった後に、主記憶にないページを参照した場合は、FIFOまたはLRUの決まりに従って、今あるページのどれかを入れ替えます。
- FIFO（First In, First Out：先に入ったものを先に出す）は、最も早く読み込んだページを入れ替えます。参照されても、読み込んだ順番は変わりません。
- LRU（Least Recently Used：最も長く使われていないものを入れ替える）は、最後に参照されてから最も時間がたっているページを入れ替えます。参照されるたびに、使われた順番が更新されます。
表の「保持ページ」は、現在主記憶にある仮想ページを並べたものです。FIFOでは「読み込んだ順（古いものから）」、LRUでは「参照されていない時間が長い順（古いものから）」に示します。
FIFOの場合
4個の場所が埋まった後、参照順の後半では、入れ替えのたびに次に必要なページが追い出されてしまいます。このため、ページフォールトは合計10回です。問題文にある「物理ページの個数が3のとき」の9回と比べると、 なので、1回増えます。
LRUの場合
こちらも保持ページを古い順に並べます。ページを参照したときは、そのページを最も新しく参照したものとして並べ直します。
LRUのページフォールトは合計8回です。3個のときの10回と比べると、 なので、2回減ります。
誤りやすいポイント
-
ヒットとページフォールトを区別すること
参照したページがすでに主記憶にあればヒットです。ページフォールトは、主記憶にないページを参照したときだけ数えます。 -
FIFOでは、ヒットしても読み込んだ順番は変わらないこと
例えば4を再び参照しても、4が読み込まれた順番はそのままです。最も早く読み込んだページが入れ替え対象です。 -
LRUでは、ヒットすると参照順が変わること
参照されたページは「最近使われた」ページになります。そのため、次に入れ替えるページを決めるときは、ヒット後の順番も反映します。 -
物理ページを増やしても、FIFOのページフォールトが必ず減るとは限らないこと
FIFOではページの入れ替わり方が変化し、今回のようにページフォールトが増える場合があります。
FAQ
Q: 表の「保持ページ」の順番は、実際の物理ページ番号ですか？
A: いいえ。表では、主記憶の場所に現在入っている仮想ページを、入れ替え対象を判断しやすい順に並べています。物理ページ番号そのものではありません。
A: いいえ。表では、主記憶の場所に現在入っている仮想ページを、入れ替え対象を判断しやすい順に並べています。物理ページ番号そのものではありません。
Q: ページを参照するたびに、FIFOの順番も更新しますか？
A: いいえ。FIFOは読み込まれた順番で入れ替えます。参照だけでは順番は変わりません。LRUは参照のたびに使われた順番を更新します。
A: いいえ。FIFOは読み込まれた順番で入れ替えます。参照だけでは順番は変わりません。LRUは参照のたびに使われた順番を更新します。
Q: 主記憶の場所を増やしたのに、FIFOのページフォールトが増えるのはなぜですか？
A: FIFOは「古く読み込んだページ」を機械的に入れ替えるため、場所を増やすことで入れ替えの順番も変わります。その結果、必要なページが先に追い出されることがあり、今回のようにページフォールトが増える場合があります。
A: FIFOは「古く読み込んだページ」を機械的に入れ替えるため、場所を増やすことで入れ替えの順番も変わります。その結果、必要なページが先に追い出されることがあり、今回のようにページフォールトが増える場合があります。
関連キーワード: 仮想記憶、ページング方式、ページフォールト、FIFO、LRU
