応用情報技術者 予想問題｜練習問題 第22問

解説

LRU（Least Recently Used）は、「最近使われたページは近い将来も使われやすい」という参照の局所性を前提に、最も長い間参照されていないページを置換対象に選ぶアルゴリズムである。最も古くロードされたページを置き換えるのはFIFOの説明で、ロード後も頻繁に参照され続けているページまで追い出してしまう欠点がある。将来最も参照されないページを置き換えるのはOPT（最適置換アルゴリズム）だが、将来の参照パターンを事前に知る必要があるため実装は不可能であり、「実装可能」とする記述は誤り。OPTは他方式の性能を評価する理論上の基準として使われる。「LRUは過去の実績を見る、OPTは未来を見るから実装できない、FIFOは入った順」と整理して覚えるとよい。