仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。
主記憶のページ枠が，4000，5000，6000，7000番地（いずれも16進数）の4ページ分で，プログラムが参照するページ番号の順が，1→2→3→4→2→5→3→1→6→5→4のとき，最後の参照ページ4は何番地にページインされているか。
ここで，最初の1→2→3→4の参照で，それぞれのページは4000，5000，6000，7000番地にページインされるものとする。
正答3
解説
正解は3です。
LRU（Least Recently Used）方式は、最後に参照されてから最も長い時間が経過したページを追い出して置き換える方式です。
参照列は1、2、3、4、2、5、3、1、6、5、4の順です。
各ページ枠のページと、最近参照された順を追跡します。
【計算】
最初の1、2、3、4で、4000番地に1、5000番地に2、6000番地に3、7000番地に4が入ります。
次の2は主記憶にあるので置換えは起きず、古い順は1、3、4、2になります。
次の5はページフォールトで、最も古い1（4000番地）を置き換えます。
古い順は3、4、2、5になります。
次の3は主記憶にあり、古い順は4、2、5、3になります。
次の1はページフォールトで、最も古い4（7000番地）を置き換えます。
古い順は2、5、3、1になります。
次の6はページフォールトで、最も古い2（5000番地）を置き換えます。
古い順は5、3、1、6になります。
次の5は主記憶にあり、古い順は3、1、6、5になります。
最後の4はページフォールトで、最も古い3（6000番地）を置き換えます。
よって、ページ4は6000番地にページインされます。
【選択肢別解説】
1：× 4000番地には、5の参照時に1を追い出してページ5が入っています。
5は最後の4の直前に参照されたばかりなので、追い出されません。
2：× 5000番地には、6の参照時に2を追い出してページ6が入っています。
6も最後の4の少し前に参照されており、最も古いページではありません。
3：○ 最後の4の参照時点で最も長く参照されていないのは、6000番地のページ3です。
そのため3が追い出され、4は6000番地にページインされます。
4：× 7000番地には、1の参照時に元のページ4を追い出してページ1が入っています。
最後の参照時点では1より3の方が古いので、7000番地は置換えの対象になりません。
【ポイント】
LRUでは「参照された時刻が最も古いもの」を追い出します。
FIFO（First In First Out）は「ページインされた時刻が最も古いもの」を追い出すので、参照で順序が更新されない点が違います。