LRU(Least Recently Used)
LRU(Least Recently Usedの略)とは、キャッシュメモリや仮想記憶(仮想メモリ)が扱うデータのリソースの割り当てを決定するアルゴリズムのことで、最も長い間参照されていないものから順に追い出す方式のことです。
キャッシュメモリや仮想記憶で使用する主記憶装置の容量がいっぱいになったとき、いずれかのデータを追い出して、空き領域を作る必要があります。このときLRUのアルゴリズムでは、最も長い間参照されていないもの(最も過去に使用したもの)から順にデータを追い出します。
スポンサーリンク
LRUの動作イメージ
それでは、仮想記憶の実現方式のひとつであるページング方式(プログラムをページという単位に分割し、ページ単位で主記憶装置に格納する方式)を例に、LRUの動作イメージを図解で解説します。
例題
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番でページを参照するとき、LRUではどのような動作をするか。主記憶装置には、最大で3ページしか格納できないものとする。
主記憶装置に「ページ1」~「ページ3」を配置して参照する
まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置(ページイン)して、ページを参照します。(ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照)
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
続いて「ページ1」を参照
続いて「ページ1」を参照します。(主記憶装置には先ほど配置済み)
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
最も長い間参照されていない「ページ2」を追い出す
続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。ここでLRUでは、最も長い間参照されていない「ページ2」を追い出し(ページアウト)、主記憶装置に空き領域を作ります。
主記憶装置に「ページ4」を配置して参照する
最後に「ページ4」を主記憶装置に配置(ページイン)して、ページを参照します。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]