仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、追い出すページを選ぶアルゴリズムは、FIFOとLRUの二つを考える。あるタスクのページのアクセス順序が 1, 3, 2, 1, 4, 5, 2, 3, 4, 5 のとき、ページを置き換える回数の組み合わせとして適切なものはどれか。
┌────┬────┐
│ＦＩＦＯ│ ＬＲＵ │
┌─┼────┼────┤
│ア│ ３ │ ２ │
├─┼────┼────┤
│イ│ ３ │ ６ │
├─┼────┼────┤
│ウ│ ４ │ ３ │
├─┼────┼────┤
│エ│ ５ │ ４ │
└─┴────┴────┘
イ
FIFO (First In, First Out) は、先入れ先出しにより置換するアルゴリズムである。
LRU (Least Recently Used) は、参照されていない時間が最も長いページを置換対象とするアルゴリズムである。
ページ数が3であるため、割り当てられるページの状態は以下のようになる。
【FIFOの場合】
青字は置換発生
1: 1
3: 1, 3
2: 1, 3, 2
1: 1, 3, 2
4: 3, 2, 4
5: 2, 4, 5
2: 2, 4, 5
3: 4, 5, 3
4: 4, 5, 3
5: 4, 5, 3
よって、3回置き換わる。
【LRUの場合】
赤字は次の置換対象ページ
青字は置換発生
1: 1
3: 1, 3
2: 1, 3, 2
1: 1, 3, 2
4: 1, 4, 2
5: 1, 4, 5
2: 2, 4, 5
3: 2, 3, 5
4: 2, 3, 4
5: 5, 3, 4
よって、6回置き換わる。
| 問２０ | 目次 | 問２２ |