平成25年春期試験午後問題 問2

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問2 ソフトウェア

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

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

設問1

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

 プログラムの実行過程で存在ビットを調べ,プログラムの実行に必要なページがaに存在していないときには,ページフォールトという割込みが発生する。ページフォールトが発生すると,ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには,ページインしてから最も時間が経過しているページを置換え対象とする FIFO アルゴリズムや,参照されていない時間が最も長いページを置換え対象とするbアルゴリズムなどがある。
a,b に関する解答群
  • LFU
  • LIFO
  • LRU
  • 仮想アドレス空間
  • 物理アドレス空間
解答選択欄
  • a:
  • b:
  • a=
  • b=

解説

aについて〕
解答群のうち「LFU」「LIFO」「LRU」はページの置換に使用されるアルゴリズムなので、aの前後の文章から入る字句としては不適当とわかります。この時点で答えは残る2つに絞られます。

必要なページがaに存在しないときに発生するページフォールトとは、「主記憶上に読み込まれていないページにアクセスが試みられたときに発生する割込み」なので、aは「物理アドレス空間」が適切となります。

a=オ:物理アドレス空間

bについて〕
3つのページ置換アルゴリズムはそれぞれ以下のような仕組みで置換対象ページを決定します。
LFU(Least Frequently Used)
置換対象の中で最も参照回数の少ないページを置換対象とする。
LIFO(Last-in First-out)
最後に読み込まれたページを置換対象とする。(後入れ先出し)
LRU(Least Recently Used)
読み込まれてから最も長い時間参照されていないページを置換対象とする。
したがって「参照されていない時間が最も長いページを置換え対象とするアルゴリズム」はLRUです。

b=ウ:LRU

設問2

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

【処理の単位】
  1. 退避させるページをページアウトする。
  2. ページ置換えアルゴリズムによって,物理アドレス空間からページアウトするページを決定する。
  3. 実行に必要なページをページインする。
  4. ページアウトしたページに対応するページテーブルの要素の存在ビットを 0 にする。
  5. ページインしたページに対応するぺージテーブルの要素の存在ビットを 1 にする。
  6. ページアウトしたページに対応するページテーブルの要素の物理ページ番号を設定する。
  7. ページインしたページに対応するページテーブルの要素の物理ページ番号を設定する。
解答群
  • ①→②→③→④→⑤→⑥
  • ①→③→②→④→⑦→⑤
  • ②→①→④→③→⑤→⑥
  • ②→①→④→③→⑦→⑤
  • ②→③→①→④→⑤→⑥
  • ②→③→⑤→⑥→①→④
解答選択欄
  •  
  •  

解説

ページフォールトが発生すると、主記憶上の不必要なページが仮想記憶上に退避(ページアウト)され、プログラムの実行に必要なページが仮想記憶から主記憶に読み込まれます(ページイン)。またページアウトを行う前に、その対象となる主記憶上のページが置換アルゴリズムによって決定されます。

この流れをまとめると、
  1. 置換え対象の決定
  2. ページアウト
  3. ページイン
となり、設問中の番号でいうと「②→①→③」が処理の大まかな流れとなります。

解答群のうち、3つの処理が適切な順序となっているのは「ウ」と「エ」のみなので、答えはこの2つに絞られます。さらに「ウ」「エ」の差異は、⑥と⑦の有無なのでこの2つの処理のどちらが必要なのかを考えます。

⑥の処理が行われない場合には、物理ページ番号がページアウト前の値に設定されたままになってしまいますが、④の処理で存在ビットが 0 に設定されているのでページインしたページとの競合は生じず、再びページインする際には新しい値に再設定されるので問題は生じません。しかし⑦の処理が行われない場合には、ページインしたページと物理ページ番号の対応がとれないため、そのページにアクセスできなくなってしまう問題が発生します。

したがって⑦の処理が含まれている「エ」の順序が適切です。

エ:②→①→④→③→⑦→⑤

設問3

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

 ページ置換えアルゴリズムとして 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
解答選択欄
  • c:
  • d:
  • c=
  • d=

解説

cについて〕
参照されるページ番号と物理ページの内容の変化を表形式にすると以下のようになります。
pm02_2.png
したがってページフォールトの回数は10回です。

c=ウ:10

dについて〕
こちらも同様に物理ページ番号が4つの時の流れを表にすると以下のようになります。
pm02_3.png
したがってページフォールトの回数は11回です。

d=エ:11

Pagetop