平成16年春期試験問題 午前問25

仮想記憶管理におけるページ置換えアルゴリズムとして,LRU方式を採用する。参照かつ更新されるページ番号の順番が,2→3→5→8→2→3→6→2→3→5→1→6で,実記憶のページ枠が4のとき,ページフォールトに伴って発生するページアウトは何回か。ここで,初期状態では,実記憶にはいずれのページも読み込まれていないものとする。

  • 3
  • 4
  • 5
  • 6
正解 問題へ
分野:テクノロジ系
中分類:ソフトウェア
小分類:オペレーティングシステム
解説
置換えアルゴリズムとして使用されるLRU(Least Recently Used)は、置き換え対象の中で最後に参照されてからの時間が最も長いページを置き換え対象とするアルゴリズムです。

ページ枠がどのように置換えられていくかを考えていきます。
  1. 最初の2,3,5,8までは空き領域にページインします。
     2358
  2. 2は主記憶に存在するのでページアウトは発生しません。
     2358
  3. 3は主記憶に存在するのでページアウトは発生しません。
     2358
  4. 6は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは5なので、5をページアウトしその位置に6をページインします。(置換え1回目)
     2368
  5. 2は主記憶に存在するのでページアウトは発生しません。
     2368
  6. 3は主記憶に存在するのでページアウトは発生しません。
     2368
  7. 5は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは8なので、8をページアウトしその位置に5をページインします。(置換え2回目)
     2365
  8. 1は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは6なので、6をページアウトしその位置に1をページインします。(置換え3回目)
     2315
  9. 6は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは2なので、2をページアウトしその位置に6をページインします。(置換え4回目)
     2615
したがってページアウトの回数は「4回」になります。

Pagetop