平成31年春期試験午後問題 問2
問2 ソフトウェア
仮想記憶方式に関する次の記述を読んで，設問1～3に答えよ。
仮想記憶方式は，OSが提供する論理的な記憶領域(以下，仮想記憶という)上のアドレスと物理的な主記憶上のアドレスを対応付けて管理する方式である。仮想記憶方式では，補助記憶装置を仮想記憶の実装媒体として用いることによって，プログラムが主記憶の容量を超える大きさであっても，これを仮想記憶上のデータとして格納し，実行することができる。仮想記憶上のアドレス空間を仮想アドレス空間，主記憶上のアドレス空間を物理アドレス空間と呼び，それぞれの空間における記憶場所は仮想アドレス，物理アドレスで指定する。
仮想記憶方式の実現方法の一つにページング方式がある。この方式では，仮想アドレス空間と物理アドレス空間をそれぞれ仮想ページ，物理ページと呼ぶ固定長の領域に分割し，管理する。ページング方式では，プログラムの実行過程で，実行に必要な仮想ページのデータが物理アドレス空間に存在していないときは，そのデータが格納されている仮想ページからデータを物理ページに読み込んで利用する。
ページング方式のページ管理方法の例を次の(1)～(3)に示す。
仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例を，図1に示す。ここで，図1中のA～Hは，仮想ページ及び物理ページに格納されているデータを示す。
仮想記憶方式は，OSが提供する論理的な記憶領域(以下，仮想記憶という)上のアドレスと物理的な主記憶上のアドレスを対応付けて管理する方式である。仮想記憶方式では，補助記憶装置を仮想記憶の実装媒体として用いることによって，プログラムが主記憶の容量を超える大きさであっても，これを仮想記憶上のデータとして格納し，実行することができる。仮想記憶上のアドレス空間を仮想アドレス空間，主記憶上のアドレス空間を物理アドレス空間と呼び，それぞれの空間における記憶場所は仮想アドレス，物理アドレスで指定する。
仮想記憶方式の実現方法の一つにページング方式がある。この方式では，仮想アドレス空間と物理アドレス空間をそれぞれ仮想ページ，物理ページと呼ぶ固定長の領域に分割し，管理する。ページング方式では，プログラムの実行過程で，実行に必要な仮想ページのデータが物理アドレス空間に存在していないときは，そのデータが格納されている仮想ページからデータを物理ページに読み込んで利用する。
ページング方式のページ管理方法の例を次の(1)～(3)に示す。
- 仮想アドレス空間及び物理アドレス空間の各ページには，1から順に番号を付け，それぞれを仮想ページ番号，物理ページ番号と呼ぶ。
- 仮想ページと物理ページの対応は，ページテーブルで管理する。ページテーブルの各要素は仮想ページと1対1に対応付けられており，要素の個数は仮想ページの個数と同じである。
- ページテーブルには，仮想ページのデータが物理アドレス空間に存在しているかどうかを示すビット(以下，存在ビットという)と，存在している場合に対応する物理ページ番号を登録する領域がある。存在ビットは，当該仮想ページのデータが物理アドレス空間に存在している場合は1，存在していない場合は0である。
仮想アドレス空間の仮想ページと物理アドレス空間の物理ページとの対応例を，図1に示す。ここで，図1中のA～Hは，仮想ページ及び物理ページに格納されているデータを示す。
広告
設問1
図1中の に入れる正しい答えを，解答群の中から選べ。ここで，a1～a4に入れる答えは，aに関する解答群の中から組合せとして正しいものを選ぶものとする。
a に関する解答群
解答選択欄
- a:
- a=ウ
解説
ページテーブルのa1～a4には、それぞれ物理ページ番号が入ります。物理ページ番号は、対応する仮想ページのデータが物理アドレス空間に存在する場合に、その物理ページの番号を保持します。ページテーブルの各要素は仮想ページと1対1に対応付けられているので、図1の状態だと次の情報が入ることになります。- a1 … 仮想ページ1の"A"が存在する物理ページの番号
- a2 … 仮想ページ2の"B"が存在する物理ページの番号
- a3 … 仮想ページ3の"C"が存在する物理ページの番号
- a4 … 仮想ページ4の"D"が存在する物理ページの番号
広告
設問2
次の記述中の に入れる適切な答えを，解答群の中から選べ。ここで，b1とb2，c1とc2に入れる答えは，それぞれb，cに関する解答群の中から組合せとして適切なものを選ぶものとする。
ページング方式では，プログラムの実行過程で，実行に必要なデータが物理アドレス空間に存在していないときには，ページフォールトという割込みが発生する。ページフォールトが発生すると，仮想ページに格納されているデータを物理ページに読み込む処理(以下，ページフォールト割込み処理という)を行う。
〔ページフォールト割込み処理〕
ページング方式では，プログラムの実行過程で，実行に必要なデータが物理アドレス空間に存在していないときには，ページフォールトという割込みが発生する。ページフォールトが発生すると，仮想ページに格納されているデータを物理ページに読み込む処理(以下，ページフォールト割込み処理という)を行う。
〔ページフォールト割込み処理〕
- 物理ページのうち，仮想ページと対応付けられていない物理ページ(以下，空きページという)を一つ探す。
- 空きページがなかった場合，空きページにするb1ページを一つ選び，その選んだページに格納されているデータをb2。その後，対応するページテーブルの要素の存在ビットを0にする。これによって空きページを確保する。
- 空きページがあった場合，又はなかった場合では(2)の処理後に，その空きページにプログラムの実行に必要なc1ページに格納されているデータをc2。その後，対応するページテーブルの要素に物理ページ番号を登録して，その存在ビットを1にする。
b に関する解答群
c に関する解答群
解答選択欄
- b:
- c:
- b=エ
- c=ア
解説
プログラムの実行に必要なページが物理アドレス空間上に存在しないときにはページフォールトという割込みが発生します。ページフォールトの発生時、物理アドレス空間にページの空きがなかった場合には、物理アドレス空間(主記憶)の物理ページを補助記憶装置に退避させ、その空いた部分に仮想アドレス空間(補助記憶装置)の仮想ページを読み込むことで、ページを入れ替える処理が行われます。〔bについて〕
(2)は、物理アドレス空間に空きページを確保する処理です。この処理では、入れ替え対象となった物理ページを補助記憶装置に退避させるので、b1＝物理、b2＝補助記憶装置に書き出す、が入ります。
∴b＝エ
〔cについて〕
(3)は、(2)の処理で作成した空きページに仮想ページを読み込む処理です。この処理では、仮想ページのデータを補助記憶装置から物理アドレス空間に移すので、c1＝仮想、c2＝補助記憶装置から読み込む、が入ります。
∴c＝ア
広告
設問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。
ページング方式において，ページフォールトの発生回数を少なくするためには，どの物理ページを空きページにするかが重要になる。一般的に知られているアルゴリズムである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:
- d=ア
- e=エ
解説
〔dについて〕FIFO(First In First Out)は、ページインしてから最も時間が経過しているページを置換え対象とする先入れ先出しのアルゴリズムです。
ページ枠4でFIFOを採用した場合の処理の流れは次の通りです。
- 最初の4,2,1,5については、いずれも物理アドレス空間に存在していないので4回のページフォールトが発生します。
4215 - 4は物理アドレス空間に存在するのでページフォールトは発生しません。
- 2は存在するのでページフォールトは発生しません。
- 3は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは4なので、4をページアウトしその位置に3をページインします。
3215 - 4は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは2なので、2をページアウトしその位置に4をページインします。
3415 - 2は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは1なので、1をページアウトしその位置に2をページインします。
3425 - 1は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは5なので、5をページアウトしその位置に1をページインします。
3421 - 5は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは3なので、3をページアウトしその位置に5をページインします。
5421 - 3は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔にページインしたページは4なので、4をページアウトしその位置に3をページインします。
5321 - 5は存在するのでページフォールトは発生しません。
∴d＝ア：1回増える
〔eについて〕
LRU(Least Recently Used)方式は、対象ページの中で最も長い時間参照されていないものを置換え対象とするアルゴリズムです。
ページ枠4でLRUを採用した場合の処理の流れは次の通りです。
- 最初の4,2,1,5については、いずれも物理アドレス空間に存在していないので4回のページフォールトが発生します。
4215 - 4は物理アドレス空間に存在するのでページフォールトは発生しません。
- 2は存在するのでページフォールトは発生しません。
- 3は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔に参照されたページは1なので、1をページアウトしその位置に3をページインします。
4235 - 4は存在するのでページフォールトは発生しません。
- 2は存在するのでページフォールトは発生しません。
- 1は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔に参照されたページは5なので、5をページアウトしその位置に1をページインします。
4231 - 5は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔に参照されたページは3なので、3をページアウトしその位置に5をページインします。
4251 - 3は存在しないのでページ置換えが必要になります。4つの物理ページのうち、最も昔に参照されたページは4なので、4をページアウトしその位置に3をページインします。
3251 - 5は存在するのでページフォールトは発生しません。
∴e＝エ：2回減る
広告
広告