仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は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 - ページ3にアクセスする。
1 → 3 1 - ページ2にアクセスする。
3 1 → 2 3 1 - ページ1にアクセスする。
ページ1はすでに実記憶に割り当てられているのでページの状態は変わらない。2 3 1 - ページ4にアクセスする。
最初に割り当てられたパージ1が追い出されページ4が割り当てられる。2 3 1 → 4 2 3 - ページ5にアクセスする。
最初に割り当てられたパージ3が追い出されページ5が割り当てられる。4 2 3 → 5 4 2 - ページ2にアクセスする。
ページ2はすでに実記憶に割り当てられているのでページの状態は変わらない。5 4 2 - ページ3にアクセスする。
最初に割り当てられたパージ2が追い出されページ3が割り当てられる。5 4 2 → 3 5 4 - ページ4にアクセスする。
ページ4はすでに実記憶に割り当てられているのでページの状態は変わらない。3 5 4 - ページ5にアクセスする。
ページ5はすでに実記憶に割り当てられているのでページの状態は変わらない。3 5 4
- ページ1にアクセスする。
- LRU
最初のページの状態は何も入っていないのでページの状態は空である。
※ここで、右から左に最近アクセスした順とする。(一番左が最後にアクセスしたページ)- ページ1にアクセスする。
→ 1 - ページ3にアクセスする。
1 → 3 1 - ページ2にアクセスする。
3 1 → 2 3 1 - ページ1にアクセスする。
ページ1はすでに実記憶に割り当てられているので、ページの置き換えは発生しないが、順序が変わる。2 3 1 → 1 2 3 - ページ4にアクセスする。
もっともアクセスのないページ3が追い出されページ4が割り当てられる。1 2 3 → 4 1 2 - ページ5にアクセスする。
もっともアクセスのないページ2が追い出されページ4が割り当てられる。4 1 2 → 5 4 1 - ページ2にアクセスする。
もっともアクセスのないページ1が追い出されページ2が割り当てられる。5 4 1 → 2 5 4 - ページ3にアクセスする。
もっともアクセスのないページ4が追い出されページ3が割り当てられる。2 5 4 → 3 2 5 - ページ4にアクセスする。
もっともアクセスのないページ5が追い出されページ4が割り当てられる。3 2 5 → 4 3 2 - ページ5にアクセスする。
もっともアクセスのないページ2が追い出されページ5が割り当てられる。4 3 2 → 5 3 3
- ページ1にアクセスする。
【キーワード】
・ページ置換えアルゴリズム
- ページ置換えアルゴリズム
ページングによる仮想記憶方式でページフォールトに伴うページアウト(主記憶からデータを磁気ディスクなどに退避する操作)するページを決める方法には幾つかあり、代表的なものとしては、- LRU(Least Recently Used)
最も長い時間アクセスがないページをページアウトする。 - FIFO(First-In First-Out)
最も長い時間ページイン状態にあるページをページアウトする。 - NFU(Not Frequently Used)
アクセス回数の少ないページをページアウトする。 - NRU(Not Recently Used)
一定時間アクセスのないページをページアウトする。
- LRU(Least Recently Used)
もっと、「ページ置換えアルゴリズム」について調べてみよう。
戻る
一覧へ
次へ