ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。
主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。
ここで，初期状態では主記憶にどのページも存在しないものとする。
正答4
解説
正解は4です。
LRU（Least Recently Used）方式は、最後に参照されてから最も長い時間が経過したページを置き換える方式です。
アクセスのたびに、参照の古い順にページを並べて追跡します。
【処理の流れ】
ページを参照の古い順に並べて記します。
ページ1、2、3、4のアクセスで、枠は「1、2、3、4」となります。
ページ5のアクセスでは、最も古い1を置き換え、「2、3、4、5」となります。
ページ2はヒットし、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は直前にアクセスされた最新のページです。
3：× ページ4は、ページ3のアクセス時にすでに置き換えられており、主記憶にありません。
4：○ ページ6のアクセス時点で、最後の参照が最も古いのはページ5です。
【ポイント】
FIFO方式なら「最も先に読み込まれたページ」を置き換える点がLRUと異なります。
LRUでは、ヒットしたページの順番を最新に入れ替えることを忘れないようにしましょう。