平成29年 春期 基本情報技術者 午前 問19

仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、追い出すページを選ぶアルゴリズムは、FIFOとLRUの二つを考える。
あるタスクのページのアクセス順序が
 1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき、ページを置き換える回数の組み合わせとして適切なものはどれか。

FIFO LRU
3 2
3 6
4 3
5 4


答え イ


解説
FIFO、LRUの時のそれぞれのページの置き換え回数を数える。

  • FIFO
    最初のページの状態は何も入っていないのでページの状態は空である。
    ※ここで、右から左にページに割り当てられた順とする。(一番左が最後に割り当てられたページ)



    1. ページ1にアクセスする。



      1

    2. ページ3にアクセスする。
      1

      3 1
    3. ページ2にアクセスする。
      3 1
      2 3 1
    4. ページ1にアクセスする。
      ページ1はすでに実記憶に割り当てられているのでページの状態は変わらない。
      2 3 1
    5. ページ4にアクセスする。
      最初に割り当てられたパージ1が追い出されページ4が割り当てられる。
      2 3 1
      4 2 3
    6. ページ5にアクセスする。
      最初に割り当てられたパージ3が追い出されページ5が割り当てられる。
      4 2 3
      5 4 2
    7. ページ2にアクセスする。
      ページ2はすでに実記憶に割り当てられているのでページの状態は変わらない。
      5 4 2
    8. ページ3にアクセスする。
      最初に割り当てられたパージ2が追い出されページ3が割り当てられる。
      5 4 2
      3 5 4
    9. ページ4にアクセスする。
      ページ4はすでに実記憶に割り当てられているのでページの状態は変わらない。
      3 5 4
    10. ページ5にアクセスする。
      ページ5はすでに実記憶に割り当てられているのでページの状態は変わらない。
      3 5 4
    したがって、ページの置き換え回数は3回である。
  • LRU
    最初のページの状態は何も入っていないのでページの状態は空である。
    ※ここで、右から左に最近アクセスした順とする。(一番左が最後にアクセスしたページ)



    1. ページ1にアクセスする。



      1

    2. ページ3にアクセスする。
      1

      3 1
    3. ページ2にアクセスする。
      3 1
      2 3 1
    4. ページ1にアクセスする。
      ページ1はすでに実記憶に割り当てられているので、ページの置き換えは発生しないが、順序が変わる。
      2 3 1
      1 2 3
    5. ページ4にアクセスする。
      もっともアクセスのないページ3が追い出されページ4が割り当てられる。
      1 2 3
      4 1 2
    6. ページ5にアクセスする。
      もっともアクセスのないページ2が追い出されページ4が割り当てられる。
      4 1 2
      5 4 1
    7. ページ2にアクセスする。
      もっともアクセスのないページ1が追い出されページ2が割り当てられる。
      5 4 1
      2 5 4
    8. ページ3にアクセスする。
      もっともアクセスのないページ4が追い出されページ3が割り当てられる。
      2 5 4
      3 2 5
    9. ページ4にアクセスする。
      もっともアクセスのないページ5が追い出されページ4が割り当てられる。
      3 2 5
      4 3 2
    10. ページ5にアクセスする。
      もっともアクセスのないページ2が追い出されページ5が割り当てられる。
      4 3 2
      5 3 3
    したがって、ページの置き換え回数は6回である。


キーワード
・ページ置換えアルゴリズム

キーワードの解説
  • ページ置換えアルゴリズム
    ページングによる仮想記憶方式でページフォールトに伴うページアウト(主記憶からデータを磁気ディスクなどに退避する操作)するページを決める方法には幾つかあり、代表的なものとしては、
    • LRU(Least Recently Used)
      最も長い時間アクセスがないページをページアウトする。
    • FIFO(First-In First-Out)
      最も長い時間ページイン状態にあるページをページアウトする。
    • NFU(Not Frequently Used)
      アクセス回数の少ないページをページアウトする。
    • NRU(Not Recently Used)
      一定時間アクセスのないページをページアウトする。
    などがある。

もっと、「ページ置換えアルゴリズム」について調べてみよう。

戻る 一覧へ 次へ