平成19年 春期 ソフトウェア開発技術者 午前 問23

仮想記憶のページの置換えアルゴリズムの一つであるFIFOの特徴のうち、適切なものはどれか。

　ア 　LRUアルゴリズムより置き換えるページを決定する処理に時間がかかる。
　イ 　LRUアルゴリズムよりもページフォールトの回数が少なくなる。
　ウ 　ある種のページ参照列に対して、割当て主記憶量を増やすと、かえってページフォールトの回数が増加する。
　エ 　ページサイズを小さくすると、ページフォールトの回数が減る。

答え　ウ

【解説】

　ア 　LRUでは使った時間などを調べて、最もアクセスのないページを探す処理が必要だが、FIFOではページを割当てた順なので処理時間は短くてすむ。
　イ 　ページフォールトの回数は扱うデータの性質により異なり、LRU・FIFOだから多い・少ないとは一概にいえない。(大量のデータを順にサーチする処理ではFIFO・LRUに関係なくページフォールトの回数は一緒である。)
　ウ 　実例を示します。(過去に出題された問題です。)
ページ枠が3と4のとき、参照するページ番号が、
　1→2→3→4→1→2→5→1→2→3→4→5
のときを考えます。
ページ枠:3のとき
参照するページ ページ枠の内容 ページフォールト回数
1 1 1
2 1　2 2
3 1　2　3 3
4 2　3　4 4
1 3　4　1 5
2 4　1　2 6
5 1　2　5 7
1 1　2　5 7
2 1　2　5 7
3 2　5　3 8
4 5　3　4 9
5 5　3　4 9

ページ枠:4のとき
参照するページ ページ枠の内容 ページフォールト回数
1 1 1
2 1　2 2
3 1　2　3 3
4 1　2　3　4 4
1 1　2　3　4 4
2 1　2　3　4 4
5 2　3　4　5 5
1 3　4　5　1 6
2 4　5　1　2 7
3 5　1　2　3 8
4 1　2　3　4 9
5 2　3　4　5 10
このように、ページ割当て容量を増やした結果、ページフォールトの回数が増加しました。
　エ 　一般的に、ページサイズを小さくすると、ページフォールトの回数は増えます。
8の大きさのデータを扱うとき、ページサイズが10であれば、ページフォールトは1回ですが、ページサイズが5では、ページフォールトは2回発生します。

【キーワード】
・仮想記憶のページの置換え

【キーワードの解説】
  • 仮想記憶のページの置換え
    仮想記憶は実際にコンピュータに実装されているメモリよりも大きなメモリ領域を提供する仕組みであり、実メモリには仮想メモリ空間のデータを固定長のページで必要なときに格納しする。(可変長の場合はセグメントになる。)
    実メモリ上にないデータを扱うときに、仮想記憶から実メモリのデータを移すことをページフォールトといいます。
    このとき、実メモリに空き容量がないときには、いずれかのページを実メモリから外して仮想記憶に移す処理が必要になります。このとき、どのページを外すかを決定するアルゴリズムには幾つかありますが、LRU(Least Recently Used)では最近最も使われていないページが外され、FIFO(First-In First-Out)ではページを割当てた順(古い順)にページを外す。

もっと、「仮想記憶」について調べてみよう。

戻る 一覧へ 次へ