問１９
仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は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回置き換わる。
