LRU（Least Recently Used）

最後に使われてから最も時間が経過したページを追い出す、ページ置換えアルゴリズム。直近に使ったものはまた使われやすいという性質に沿うため、FIFOより一般に高い命中率が得られる。

最も長い間参照されていないページを置換対象とするページ置換えアルゴリズム。参照の局所性（最近使われたページは再び使われやすい）を利用する。FIFOより効率的で、キャッシュやOSのページ管理で広く採用される。

到着した順にジョブやタスクを実行するスケジューリング方式で、到着順方式ともいう。公平で仕組みも単純だが、処理時間の長いジョブが先に来ると、後続のジョブの待ち時間が大きくなる。

先に入れたものから先に取り出す方式で、先入れ先出しともいう。キューの動作原理であり、ページ置換えアルゴリズムとしては、主記憶に最も早く読み込まれたページを追い出す。仕組みは単純だが、よく使われるページも追い出してしまうことがある。

プログラムが直近の一定期間に参照したページの集合。プログラムが効率よく動くために主記憶に置いておくべきページの目安となり、ワーキングセットを主記憶に保持できないとページの置換えが頻発してスラッシングが起こる。

データを一方の端（末尾）から追加し、反対の端（先頭）から取り出すことで、先に入れたデータから先に取り出す（FIFO：先入れ先出し）データ構造。処理の順番待ち、プリンタの印刷待ち、幅優先探索などに使われる。