基本情報技術者 一問一答｜A 第81問

解説

LRU（Least Recently Used）は、仮想記憶のページ置換アルゴリズムの一つで、主記憶上のページのうち最後に参照されてから最も長い時間が経過した（最も長く使われていない）ページを追い出しの対象とする方式である。「最近使われたページは近い将来も使われる可能性が高い」という参照の局所性に基づいており、ヒット率が高くなりやすい。最も頻繁に使われるページを置換するのは局所性に反する選択であり誤り。ランダムに置換するのは参照履歴を活用しない別方式、最も新しいページを置換するのはLRUと逆の考え方である。基本情報技術者試験では、ページ参照列とページ枠数を与えてLRUやFIFOでのページフォールト回数を数えさせる問題が頻出であり、「最後の参照時刻が最も古いページを選ぶ」動作を手で追えるようにしたい。