LFU（Least Frequently Used）とは

LFU（Least Frequently Used）

LFU（Least Frequently Usedの略）とは、キャッシュメモリや仮想記憶（仮想メモリ）が扱うデータのリソースの割り当てを決定するアルゴリズムのことで、最も使用頻度が低いものから順に追い出す方式のことです。

キャッシュメモリや仮想記憶で使用する主記憶装置の容量がいっぱいになったとき、いずれかのデータを追い出して、空き領域を作る必要があります。このときLFUのアルゴリズムでは、最も使用頻度が低いものから順にデータを追い出します。

スポンサーリンク

LFUの動作イメージ

それでは、仮想記憶（仮想メモリ）の実現方式のひとつであるページング方式（プログラムをページという単位に分割し、ページ単位で主記憶装置に格納する方式）を例に、LFUの動作イメージを図解で解説します。

主記憶装置に「ページ1」～「ページ3」を配置して参照する

まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置（ページイン）して、ページを参照します。（ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照）

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

続いて「ページ1」と「ページ3」を参照

続いて「ページ1」と「ページ3」を参照します。（主記憶装置には先ほど配置済み）

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

最も使用頻度が低い「ページ2」を追い出す

続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。

ここでLFUでは、最も使用頻度が低い「ページ2」を追い出し（ページアウト）、主記憶装置に空き領域を作ります。（使用頻度は「ページ1：2回」「ページ2：1回」「ページ3：2回」とページ2が最も低い）

主記憶装置に「ページ4」を配置して参照する

最後に「ページ4」を主記憶装置に配置（ページイン）して、ページを参照します。

[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]

このようにLFU（Least Frequently Used）は、最も使用頻度が低いページから順に追い出すというアルゴリズムです。