« 【情報処理@AN】本を買ってみた | トップページ | 【情報処理】「ページアウト問題」攻略法(LRU編) »

【情報処理】「ページアウト問題」攻略法(FIFO編)

高度区分の午前問題によく出る、仮想記憶のページアウト回数の問題。

主に、FIFO方式LRU方式の違いを理解しているかが問われるわけですが、慣れていないと時間をとられたり、数え間違えてしまいがちです。また、FIFO方式とLRU方式で回数の違いを比較させるなどの応用問題もあり、意外と手強かったりします。

そこで、ワキィなりに編み出した「ページアウト問題」の攻略法を紹介してみようと思います。

二回に分けて、今回がFIFO方式の数え方、次回はLRU方式の数え方について書きます。

例として、実記憶装置のページ枠が3ページ分あり、仮想ページ番号が4、3、2、1、4、2、3、1の順に参照された場合を考えてみます。


4、3
4、3、2

左から順にページ番号を書いていきます。まだページアウトはありません。

4、3、2、1
(4)、3、2、1
四番目の番号「1」が入ると、3ページの枠に収まらないので左端の「4」がページアウトになります。これを○で囲んで表します。

(4)、(3)、2、1、4
同じように五番目の「4」が入ると、左端の「3」がページアウトになりますので○で囲みます。

(4)、(3)、2、1、4、2
(4)、(3)、2、1、4、
六番目は「2」ですが、ページ枠内にあるのでページアウトが発生しません。このとき、FIFOの場合は右側の「2」を横線で消します

(4)、(3)、(2)、1、4、、3
次の番号「3」を書いたら、2がページアウトするので○で囲みます。

(4)、(3)、(2)、1、4、、3、
次の番号「1」はページアウトしないので、右の「1」を横線で消します。これで全ページの参照が完了。
このとき、○で囲った番号の数がページアウト回数になります。この場合は「3」が答えです。

以上をまとめると…。

  • 左端から順に参照するページを書いていく
  • ○も横線もないページ番号がページ枠の数を超えたら、左端の番号を○で囲む
  • ページ内に同じ番号がある場合、FIFOでは右側(後)の番号を横線で消す
  • 全ページの参照が終わったとき、○で囲んだ数字の数がページアウト数になる

(解説)
順番に書いていったページ番号は、実はページアウトされる順番を表しています。
FIFO方式、LRU方式のどちらも、基本的にはページインした順番にページアウトすることになります…が、ページ枠内にあるページを参照したとき両者に違いが生まれます。

FIFO(First In First Out)方式の場合、ページ枠内にあるページを参照しても、先に入ったページが先に出て行くルールは変わりません。このため、例えばページ枠内に4、3、1というページがある状態で「3」を参照しても、ページアウトする順序は4、3、1のままです。

つまり後で参照した「3」は順序に影響しないので、4、3、1、3のうち後者=右側の3を消すことになります。

次回はLRU編になります。ご参考になれば幸いです。

|

« 【情報処理@AN】本を買ってみた | トップページ | 【情報処理】「ページアウト問題」攻略法(LRU編) »

学問・資格」カテゴリの記事

情報処理技術者試験」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/516130/41718025

この記事へのトラックバック一覧です: 【情報処理】「ページアウト問題」攻略法(FIFO編):

« 【情報処理@AN】本を買ってみた | トップページ | 【情報処理】「ページアウト問題」攻略法(LRU編) »