仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つを考える。
あるタスクのページのアクセス順序が
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき，ページを置き換える回数の組合せとして，適切なものはどれか。
正答2
解説
正解は2です。
ページ置換えアルゴリズムのFIFOとLRUで、置換え回数を数える問題です。
FIFO（First In First Out）は最も古く読み込んだページを、LRU（Least Recently Used）は最も長い間参照されていないページを追い出します。
実記憶のページ枠は3つです。
【計算】
FIFOでは、最初の1、3、2は空き枠に入るので置換えではありません。
次の1は実記憶にあるので置換えは起きません。
4の参照で最も古い1を追い出し、実記憶は3、2、4になります（1回目）。
5の参照で3を追い出し、2、4、5になります（2回目）。
2は実記憶にあります。
3の参照で2を追い出し、4、5、3になります（3回目）。
4と5は実記憶にあるので、FIFOの置換えは3回です。
LRUでは、1、3、2を読み込み、次の1を参照すると最も古い参照は3になります。
4の参照で3を追い出します（1回目）。
5の参照で2を追い出します（2回目）。
2の参照で1を追い出します（3回目）。
3の参照で4を追い出します（4回目）。
4の参照で5を追い出します（5回目）。
5の参照で2を追い出します（6回目）。
よってLRUの置換えは6回です。
【選択肢別解説】
1：× FIFOの3回は合っていますが、LRUは2回ではなく6回です。
2：○ FIFOが3回、LRUが6回で、計算結果と一致します。
3：× FIFOは4回ではなく3回、LRUは3回ではなく6回です。
4：× FIFOは5回ではなく3回、LRUは4回ではなく6回です。
【ポイント】
LRUは一般に効率が良いとされますが、この問題のように参照順によってはFIFOより置換えが多くなることがあります。
置換え回数は、最初に空き枠へ読み込む分を含めないことに注意します。