ページを置き換える回数の組合せ

参照列を順に追うと、置換回数はFIFOが3回、LRUが6回です。この組合せに当たる「イ」が正解です。 最初の1、3、2の読込みは空き枠への格納なので、置換回数に含めない。 FIFOでは4、5、3の読込み時に合計3回置換する。 LRUでは4、5、2、3、4、5の読込み時に合計6回置換する。 参照 FIFO：処理 FIFO：実記憶（古い順） LRU：処理 LRU：実記憶（参照が古い順） 1 空きに読込み 1 空きに読込み 1 3 空きに読込み 1 3 空きに読込み 1 3 2 空きに読込み 1 3 2 空きに読込み 1 3 2 1 ヒット 1 3 2 ヒット 3 2 1 4 1を追い出す 3 2 4 3を追い出す 2 1 4 5 3を追い出す 2 4 5 2を追い出す 1 4 5 2 ヒット 2 4 5 1を追い出す 4 5 2 3 2を追い出す 4 5 3 4を追い出す 5 2 3 4 ヒット 4 5 3 5を追い出す 2 3 4 5 ヒット 4 5 3 2を追い出す 3 4 5 置き換え（追い出し）の回数は FIFO が 3回 、LRU が 6回 です。FIFO は 読み込んだ順 、LRU は 最後に参照された時刻 が古いページを追い出す点が違います。4回目の参照（1）は、FIFO では順番を変えませんが、LRU では1が最新になります。

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

出典平成29年度 春期 基本情報技術者試験 午前 問19

FIFO

LRU

ア

3

2

イ

3

6

ウ

4

3

エ

5

4