« 【情報処理】「ページアウト問題」攻略法(FIFO編) | トップページ | 【情報処理】「ページアウト問題」攻略法(おさらい) »

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

前回に引き続き、今回はLRU編になります。

最初に、LRU方式の書き方を以下にまとめます。違いは横線で消す数字だけです

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

次に、具体的な書き方を追ってみます。

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


4、3
4、3、2

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

(4)、(3)、2、1、4
四番目の番号「1」、五番目の「4」が入ると、左端からページアウトしていきますので○で囲みます。

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

(4)、(3)、、(1)、4、2、3
次の番号「3」が入ると、左端の「1」がページアウトするので○で囲みます。

(4)、(3)、、(1)(4)、2、3、1
次の番号「1」が入ったときも同様に、左端の「4」を○で囲みます。これで全ページの参照が完了。
FIFOと同じように、○で囲った番号の数がページアウト回数になります。この場合は「4」が答えです。

(解説)
前回解説した通り、LRU(Last Recently Used)方式でも基本的にはページインした順番にアウトします。

しかしLRUの場合、ページ枠内にあるとき参照されたページはページアウトを一番最後に回すというルールがあります。例えばページ枠内に4、3、1というページがある状態で「3」を参照すると、ページアウトする順序は4、1、3に変わってしまいます。

つまり4、3、1という行列の中で参照された「3」が最後尾(一番右)に並び直すので、4、3、1、3のうち左側の3を消すことになります。

次回は、おさらいの意味で両者の比較問題を解いてみます。

|

« 【情報処理】「ページアウト問題」攻略法(FIFO編) | トップページ | 【情報処理】「ページアウト問題」攻略法(おさらい) »

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

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

コメント

コメントを書く



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




トラックバック

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

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

« 【情報処理】「ページアウト問題」攻略法(FIFO編) | トップページ | 【情報処理】「ページアウト問題」攻略法(おさらい) »