LIRSキャッシングアルゴリズム

すべてのページ置換アルゴリズムは、機能するために参照局所性の存在に依存していますが、異なる置換アルゴリズム間の大きな違いは、この局所性をどのように定量化するかにあります。LIRSは、ページの再利用距離、つまり、そのページへの2つの連続した参照の間にアクセスされた異なるページの数を使用して局所性を定量化します。具体的には、LIRSはこの目的のために、最後の参照と最後から2番目の参照（存在する場合）を使用します。ページが初めてアクセスされた場合、その再利用距離は無限です。対照的に、LRUは、ページの参照後にアクセスされた異なるページの数であるページの最新性を使用して局所性を定量化します。最新のアクセス履歴を考慮するために、LIRSの実装では、実際には、ページの再利用距離と最新性のうち大きい方を局所性を定量化するメトリックとして使用し、RD-Rと表記します。キャッシュの容量がCページであると仮定すると、LIRSアルゴリズムは、最近アクセスされたページをRD-R値に従ってランク付けし、最もランクの高いCページをキャッシュに保持します。

再利用距離と再利用の最新性の概念は以下のように視覚化できます。ここで、T1とT2はそれぞれページBの最後から2番目と最後の参照時刻であり、T3は現在時刻です。

. . . B . . . B . . . . . . . . . . B . . . . . ^----再利用距離---^--最新性--^ T1 T2 T3

LIRSはキャッシュされたページと一部のキャッシュされていないページのメタデータを整理し、以下に説明する置換操作を実行します。これはグラフ^{[ 3 ]}の例でも示されています。

1. キャッシュは、低参照最新性（LIR）パーティションと高参照最新性（HIR）パーティションに分割されます。LIRパーティションには最もランクの高いページ（LIRページ）が格納され、HIRパーティションにはその他のページ（HIRページ）が格納されます。
2. LIRパーティションにはキャッシュの大部分が格納されており、すべてのLIRページはキャッシュ内に常駐しています。
3. 最近アクセスされたすべてのページは、LIRSスタック（グラフのスタックS ）と呼ばれるFIFOキューに配置され、常駐HIRページも別のFIFOキュー（グラフのスタックQ ）に配置されます。
4. アクセスされたページはスタックSの最上部に移動され、スタックの最下部にあるHIRページは削除されます。例えば、グラフ(a)でページBにアクセスした後、グラフ(b)が生成されます。
5. スタックS内のHIRページにアクセスすると、それはLIRページに変換され、それに伴い、スタックSの最下部にあるLIRページがHIRページに変換されてスタックQの最上部に移動します。例えば、グラフ(a)上のページEにアクセスした後、グラフ(c)が生成されます。
6. ミスが発生し、常駐ページを置き換える必要がある場合、スタックQの最下部にある常駐HIRページが置き換え対象として選択されます。例えば、グラフ(a)でページDとページCにアクセスした後、それぞれグラフ(d)とグラフ(e)が生成されます。