仮想記憶管理におけるページ置換えアルゴリズムとして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の参照で、4000＝1、5000＝2、6000＝3、7000＝4となります。
2を参照すると、古い順は1、3、4、2になります。
5を参照すると、最も古い1（4000）を追い出し、4000＝5となります。
古い順は3、4、2、5です。
3を参照すると、古い順は4、2、5、3になります。
1を参照すると、最も古い4（7000）を追い出し、7000＝1となります。
古い順は2、5、3、1です。
6を参照すると、最も古い2（5000）を追い出し、5000＝6となります。
古い順は5、3、1、6です。
5を参照すると、古い順は3、1、6、5になります。
4を参照すると、最も古い3（6000）を追い出し、6000＝4となります。
【選択肢別解説】
1：× 4000番地には、途中でページ5が入り、その後も5が参照されているので追い出されません。
2：× 5000番地にはページ6が入っており、最後の時点で最も古いページではありません。
3：○ 最後に4を参照する時点で最も長く参照されていないのは6000番地のページ3なので、4は6000番地に入ります。
4：× 7000番地にはページ1が入っています。
1は比較的最近参照されたので追い出されません。
【ポイント】
LRUでは、ヒットしたページも「最新」に並べ直すことを忘れないようにしましょう。
到着順だけで追い出すFIFO方式との違いがよく問われます。