ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。
主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。
ここで，初期状態では主記憶にどのページも存在しないものとする。
正答4
解説
正解は4です。
LRU（Least Recently Used）方式のページ置換えをたどる問題です。
LRUでは、最後に参照されてから最も時間がたったページを追い出します。
以下、主記憶にあるページを、参照が古い順に並べて示します。
【計算】
1、2、3、4のアクセスで枠が埋まり、古い順に1、2、3、4です。
5のアクセスでは最も古い1を追い出し、古い順に2、3、4、5となります。
2はヒットして最新になり、古い順に3、4、5、2となります。
1のアクセスでは最も古い3を追い出し、古い順に4、5、2、1となります。
3のアクセスでは最も古い4を追い出し、古い順に5、2、1、3となります。
2はヒットして最新になり、古い順に5、1、3、2となります。
6のアクセスでは最も古い5が追い出されます。
【選択肢別解説】
1：× ページ1は直前に参照されているので、最も古くはありません。
2：× ページ2は6の直前に参照された最新のページです。
3：× ページ4は、3をアクセスした時点ですでに追い出されています。
4：○ 6をアクセスする時点で最も長く参照されていないのはページ5なので、5が置き換えられます。
【ポイント】
LRUは「最後に使われた時刻」で判断し、FIFOは「読み込まれた時刻」で判断します。
ヒットしたときに順番を入れ替えるかどうかが両者の違いです。