ある計算機上のページングによる仮想記憶システムを考える。この計算機の主記憶は4ページからなり、10ページ (P0～P9) からなるプログラムを実行しようとしているとする。次に示す順番でプログラムがページ参照を行うとき、ページの追い出しにLRUアルゴリズムを用いた場合の主記憶の最終状態と、ページの追い出しにFIFOアルゴリズムを用いた場合の主記憶の最終状態の組合せとして、最も適切なものはどれか。ただし、プログラム実行直前の初期状態では、主記憶がすべて空き状態であり、また、各ページの割当ては、図中上から順に行われていくものとする。
ページ参照順
P0, P1, P2, P3, P1, P4, P5, P4, P6, P7, P6, P4, P8, P7, P9
① LRU FIFO ② LRU FIFO ③ LRU FIFO
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│P4│ │P4│ │P4│ │P8│ │P4│ │P8│
├─┤ ├─┤ ├─┤ ├─┤ ├─┤ ├─┤
│P7│ │P7│ │P7│ │P9│ │P8│ │P9│
├─┤ ├─┤ ├─┤ ├─┤ ├─┤ ├─┤
│P8│ │P8│ │P8│ │P6│ │P7│ │P6│
├─┤ ├─┤ ├─┤ ├─┤ ├─┤ ├─┤
│P9│ │P9│ │P9│ │P7│ │P9│ │P7│
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘
④ LRU FIFO ⑤ LRU FIFO
┌─┐ ┌─┐ ┌─┐ ┌─┐
│P8│ │P4│ │P8│ │P8│
├─┤ ├─┤ ├─┤ ├─┤
│P9│ │P7│ │P9│ │P9│
├─┤ ├─┤ ├─┤ ├─┤
│P6│ │P8│ │P6│ │P6│
├─┤ ├─┤ ├─┤ ├─┤
│P7│ │P9│ │P7│ │P7│
└─┘ └─┘ └─┘ └─┘
②
LRU (Least Recently Used) は、参照されていない時間が最も長いページを置換対象とするアルゴリズムである。
FIFO (First In, First Out) は、先入れ先出しにより置換するアルゴリズムである。
【LRUの場合】
P0 ・・・P0, --, --, --
P1 ・・・P0, P1, --, --
P2 ・・・P0, P1, P2, --
P3 ・・・P0, P1, P2, P3
P1 ・・・P0, P1, P2, P3
P4 ・・・P4, P1, P2, P3
P5 ・・・P4, P1, P5, P3
P4 ・・・P4, P1, P5, P3
P6 ・・・P4, P1, P5, P6
P7 ・・・P4, P7, P5, P6
P6 ・・・P4, P7, P5, P6
P4 ・・・P4, P7, P5, P6
P8 ・・・P4, P7, P8, P6
P7 ・・・P4, P7, P8, P6
P9 ・・・P4, P7, P8, P9
【FIFOの場合】
P0 ・・・P0, --, --, --
P1 ・・・P0, P1, --, --
P2 ・・・P0, P1, P2, --
P3 ・・・P0, P1, P2, P3
P1 ・・・P0, P1, P2, P3
P4 ・・・P4, P1, P2, P3
P5 ・・・P4, P5, P2, P3
P4 ・・・P4, P5, P2, P3
P6 ・・・P4, P5, P6, P3
P7 ・・・P4, P5, P6, P7
P6 ・・・P4, P5, P6, P7
P4 ・・・P4, P5, P6, P7
P8 ・・・P8, P5, P6, P7
P7 ・・・P8, P5, P6, P7
P9 ・・・P8, P9, P6, P7
| Ⅲ－１２ | 目次 | Ⅲ－１４ |