ページ置換アルゴリズム

仮想メモリ管理にページングを使用するコンピュータ オペレーティング システムでは、メモリページを割り当てる必要があるときに、ページ置換アルゴリズムによって、どのメモリ ページをページ アウト (スワップ アウトとも呼ばれる) するか、またはディスクに書き込むかが決定されます。ページ置換は、要求されたページがメモリ内になく (ページ フォールト)、空きページがまったくないか、空きページの数がしきい値より少ないために、空きページを使用して割り当てを満たすことができない場合に発生します。

置換対象として選択され、ページ アウトされたページが再度参照されるときは、ページ イン (ディスクから読み込まれる) する必要があり、これには I/O の完了を待つことが含まれます。これにより、ページ置換アルゴリズムの品質が決まります。ページ インを待つ時間が短いほど、アルゴリズムの品質は高くなります。ページ置換アルゴリズムは、ハードウェアによって提供されるページへのアクセスに関する限られた情報を調べ、アルゴリズム自体のコスト (プライマリ ストレージとプロセッサ時間) とのバランスを取りながら、ページ ミスの総数を最小化するために置換する必要があるページを推測します。

ページ置換問題は、最適な決定論的アルゴリズムが既知であるという意味で、競合分析の観点からは 典型的なオンライン問題です。

ページ置換アルゴリズムは、1960 年代と 1970 年代に研究と議論のホットな話題でした。その話題は、洗練された LRU (最も最近使われていない) 近似とワーキング セットアルゴリズムの開発でほぼ終わりました。それ以来、従来のページ置換アルゴリズムによって行われたいくつかの基本的な仮定が無効になり、研究が復活しました。特に、基盤となるハードウェアとユーザー レベルのソフトウェアの動作における次の傾向が、ページ置換アルゴリズムのパフォーマンスに影響を与えています。

• プライマリ ストレージのサイズは桁違いに増加しています。プライマリ メモリが数ギガバイトになると、すべてのメモリ フレームを定期的にチェックする必要があるアルゴリズムはますます実用的でなくなってきています。
• メモリ階層が高くなり、CPU キャッシュミスのコストがはるかに高くなりました。これにより、前述の問題がさらに悪化します。
• ユーザー ソフトウェアの参照の局所性は弱まっています。これは主に、多数の小さな関数を好むオブジェクト指向プログラミング手法の普及、無秩序なメモリ参照パターンをもたらす傾向のあるツリーやハッシュ テーブルなどの高度なデータ構造の使用、およびアプリケーションのメモリ アクセス動作を大幅に変更したガベージ コレクションの出現に起因しています。

ページ置換アルゴリズムの要件は、オペレーティングシステムのカーネルアーキテクチャの違いにより変化しています。特に、最近の OS カーネルのほとんどは仮想メモリとファイルシステムのキャッシュを統合しており、ページ置換アルゴリズムはユーザープログラムの仮想アドレス空間とキャッシュされたファイルの両方のページの中よりページを選択する必要があります。後者のページには特定のプロパティがあります。たとえば、ロックされたり、ジャーナリングによって書き込み順序の要件が課せられたりする場合があります。さらに、ページ置換の目標はメモリを待機する合計時間を最小限に抑えることであるため、メモリを割り当てる他のカーネルサブシステムによって課せられるメモリ要件を考慮する必要があります。その結果、最近のカーネル ( Linux、FreeBSD、およびSolaris ) のページ置換は、仮想メモリサブシステムのより高いレベルではなく、汎用カーネルメモリアロケータのレベルで動作する傾向があります。

置換アルゴリズムはローカルまたはグローバルにすることができます。

プロセスでページ フォールトが発生すると、ローカル ページ置換アルゴリズムによって、同じプロセス (またはメモリ パーティションを共有するプロセス グループ) に属するページが置換対象として選択されます。グローバル置換アルゴリズムでは、メモリ内の任意のページを自由に選択できます。

ローカル ページ置換では、特定のプロセスまたはプロセス グループに割り当てるページ数を決定するメモリ パーティショニングが前提となります。最も一般的なパーティショニング形式は、固定パーティショニングとワーキング セットモデルに基づくバランス セットアルゴリズムです。ローカル ページ置換の利点は、そのスケーラビリティです。各プロセスはページ フォールトを独立して処理できるため、そのプロセスのパフォーマンスがより安定します。ただし、システム全体ではグローバル ページ置換の方が効率的です。^[1]

最新の汎用コンピュータと一部の組み込みプロセッサは、仮想メモリをサポートしています。各プロセスには独自の仮想アドレス空間があります。ページ テーブルは、プロセス仮想アドレスのサブセットを物理アドレスにマップします。さらに、ほとんどのアーキテクチャでは、ページ テーブルには、ページ テーブル内の各ページの「アクセス」ビットと「ダーティ」ビットが保持されます。プロセスがそのページのメモリを読み取ったり書き込んだりすると、CPU はアクセス ビットを設定します。プロセスがそのページのメモリを書き込むと、CPU はダーティ ビットを設定します。オペレーティング システムは、アクセス ビットとダーティ ビットを変更できます。オペレーティング システムは、次の方法でメモリとファイルへのアクセスを検出できます。

• プロセスのページ テーブルにあるページのアクセス ビットをクリアします。しばらくすると、OS はページ テーブルをスキャンして、CPU によってアクセス ビットが設定されたページを探します。アクセス ビットは CPU によって自動的に設定されるため、この処理は高速ですが、OS はアクセスの通知をすぐには受け取らず、プロセスがこれらのページにアクセスした順序に関する情報も持っていないため、不正確です。
• プロセスのページ テーブルからページを削除しますが、必ずしも物理メモリからページを削除する必要はありません。そのページへの次のアクセスは、ページ フォールトが発生するため、すぐに検出されます。ページ フォールトには、OS へのコンテキスト スイッチ、対応する物理アドレスのソフトウェア検索、ページ テーブルの変更、プロセスへのコンテキスト スイッチが含まれるため、これは低速ですが、アクセスは発生後すぐに検出されるため正確です。
• readプロセスがやwritePOSIX のようにページ キャッシュにアクセスする可能性のあるシステム コールを直接実行する場合。

ほとんどの置換アルゴリズムは、結果としてターゲット ページを返すだけです。つまり、ターゲット ページがダーティ(つまり、ページを再利用する前に安定したストレージに書き込む必要があるデータが含まれている) の場合、そのページを安定したストレージに送信する (ページをクリーンにする) ために I/O を開始する必要があります。仮想メモリの初期の頃は、仮想メモリは安定したストレージへの全二重チャネルを備えたシステムで最初に実装され、クリーニングはページングと通常重複していたため、クリーニングにかかる​​時間はあまり問題ではありませんでした。一方、現代のコモディティ ハードウェアは全二重転送をサポートしていないため、ターゲット ページのクリーニングが問題になります。

この状況に対処するために、さまざまな事前クリーニングポリシーが実装されています。事前クリーニングは、すぐに置き換えられる (可能性が高い) ダーティ ページで I/O を開始するメカニズムです。事前クリーニングされたページが実際に置き換え対象として選択されるまでに、I/O が完了し、ページがクリーンになるという考え方です。事前クリーニングでは、次に置き換えられるページを識別できることを前提としています。事前クリーニングが早すぎると、置き換え対象として選択される前に再びダーティになるページを書き込むことで、I/O 帯域幅を無駄にする可能性があります。

(h,k) ページング問題は、ページング問題のモデルの一般化です。h、k を となる正の整数とします。理論的に最適なページ置換アルゴリズムと比較して、サイズのキャッシュを持つアルゴリズムのパフォーマンスを測定します。 の場合、厳密に少ないリソースで最適なページ置換アルゴリズムを提供します。 ${\displaystyle h\leq k}$${\displaystyle h\leq k}$${\displaystyle h<k}$

(h,k) ページング問題は、オンライン アルゴリズムのパフォーマンスを最適なアルゴリズムのパフォーマンスと比較することで測定する方法であり、具体的には、オンライン アルゴリズムと最適なアルゴリズムのキャッシュ サイズを個別にパラメーター化します。

マーキング アルゴリズムは、ページング アルゴリズムの一般的なクラスです。各ページを、マークと呼ばれるビットに関連付けます。最初は、すべてのページをマークなしに設定します。ページ要求のステージ (操作期間または要求のシーケンス) 中に、そのステージで最初に要求されたページをマークします。マーキング アルゴリズムは、マークされたページをページ アウトしないアルゴリズムです。

ALG がサイズ k のキャッシュを持つマーキング アルゴリズムであり、OPT がサイズ h のキャッシュを持つ最適アルゴリズムである場合 ( ) 、ALG は-競合的です。したがって、すべてのマーキング アルゴリズムは-競合比を達成します。 ${\displaystyle h\leq k}$${\displaystyle {\tfrac {k}{k-h+1}}}$${\displaystyle {\tfrac {k}{k-h+1}}}$

LRU はマーキング アルゴリズムですが、FIFO はマーキング アルゴリズムではありません。

アルゴリズムは保守的であり、k 個以下の異なるページ参照を含む連続したリクエスト シーケンスで、アルゴリズムによって発生するページ フォールトは k 個以下になります。

ALG がサイズ k のキャッシュを持つ保守的なアルゴリズムであり、OPT が のキャッシュを持つ最適アルゴリズムである場合、ALG は-競合的です。したがって、すべての保守的なアルゴリズムは-競合比を達成します。 ${\displaystyle h\leq k}$${\displaystyle {\tfrac {k}{k-h+1}}}$${\displaystyle {\tfrac {k}{k-h+1}}}$

LRU、FIFO、CLOCK は保守的なアルゴリズムです。

ページ置換アルゴリズムには様々なものがある: ^[2]

理論的に最適なページ置換アルゴリズム（OPT、千里眼置換アルゴリズム、またはBéládyの最適ページ置換ポリシーとも呼ばれる） ^{[3] [4] [2]}は、次のように動作するアルゴリズムです。ページをスワップインする必要がある場合、オペレーティングシステムは次に使用されるのが最も遠い将来のページをスワップアウトします。たとえば、今後6秒間使用されないページは、今後0.4秒以内に使用されるページよりもスワップアウトされます。

このアルゴリズムは、システムで実行されるすべてのソフトウェアが事前にわかっていてメモリ参照パターンの静的分析に適しているか、実行時分析が可能なアプリケーションのクラスのみである場合を除いて、ページが使用されるまでの時間を確実に計算することが不可能であるため、汎用オペレーティングシステムには実装できません。この制限にもかかわらず、ほぼ最適なパフォーマンスを提供できるアルゴリズムが存在します^[5]。オペレーティングシステムはプログラムによって参照されるすべてのページを追跡し、それらのデータを使用して、後続の実行でどのページをスワップインおよびスワップアウトするかを決定します。このアルゴリズムは、ほぼ最適なパフォーマンスを提供できますが、プログラムの最初の実行では提供されず、プログラムのメモリ参照パターンが実行されるたびに比較的一貫している場合のみです。

ページング問題の分析はオンライン アルゴリズムの分野でも行われており、ページング問題に対するランダム化オンライン アルゴリズムの効率は償却分析を使用して測定されます。

最近使用されていない (NRU) ページ置換アルゴリズムは、最近使用されたページをメモリ内に保持することを優先するアルゴリズムです。このアルゴリズムは、次の原則に基づいて動作します。ページが参照されると、そのページの参照ビットが設定され、参照済みとしてマークされます。同様に、ページが変更されると (書き込まれると)、変更ビットが設定されます。ビットの設定は通常ハードウェアによって行われますが、ソフトウェア レベルで行うこともできます。

一定の固定時間間隔で、タイマー割り込みがトリガーされ、すべてのページの参照ビットがクリアされるため、現在のタイマー間隔内で参照されたページのみが参照ビットでマークされます。ページを置き換える必要がある場合、オペレーティング システムはページを次の 4 つのクラスに分割します。

3. 参照、変更

2. 参照されているが、変更されていない

1. 参照されていない、変更されていない

0. 参照されていない、変更されていない

ページが変更されているのに参照されていないということはあり得ないように思えますが、これはクラス 3 ページの参照ビットがタイマー割り込みによってクリアされたときに発生します。NRU アルゴリズムは、削除するページを最下位のカテゴリからランダムに選択します。したがって、上記の 4 つのページ カテゴリのうち、参照も変更もされていないページが存在する場合、NRU アルゴリズムはそのようなページを置き換えます。このアルゴリズムは、変更されているが参照されていないページ (最後のタイマー間隔内) は、頻繁に参照されている変更されていないページよりも重要度が低いことを意味していることに注意してください。

NRU はマーキング アルゴリズムなので、競争的です。 ${\displaystyle {\tfrac {k}{k-h+1}}}$

最も単純なページ置換アルゴリズムは FIFO アルゴリズムです。先入れ先出し (FIFO) ページ置換アルゴリズムは、オーバーヘッドの少ないアルゴリズムで、オペレーティング システム側ではほとんど記録を必要としません。そのアイデアは名前から明らかです。オペレーティング システムは、メモリ内のすべてのページをキューで追跡し、最新のページを後ろに、最も古いページを前にします。ページを置換する必要がある場合は、キューの先頭にあるページ (最も古いページ) が選択されます。FIFO は低コストで直感的ですが、実際のアプリケーションではパフォーマンスが低くなります。したがって、変更されていない形式で使用されることはほとんどありません。このアルゴリズムでは、Bélády の異常が発生します。簡単に言うと、ページ フォールトが発生すると、メモリ内に最も長く存在していたフレームが置換されます。

FIFOページ置換アルゴリズムは、OpenVMSオペレーティングシステムで使用されていますが、いくつかの変更が加えられています。^[6]有効な変換テーブル参照を持つ限られた数のエントリをスキップすることで、部分的な2回目のチャンスが提供されます。^[7]さらに、ページはプロセスのワーキングセットからシステム全体のプールに移動され、まだ再利用されていない場合はそこから回復できます。

FIFO は保守的なアルゴリズムなので、競争的です。 ${\displaystyle {\tfrac {k}{k-h+1}}}$

FIFO ページ置換アルゴリズムの修正版であるセカンドチャンス ページ置換アルゴリズムは、改善コストをほとんどかけずに FIFO よりも比較的優れた性能を発揮します。FIFO と同様にキューの先頭を調べますが、そのページをすぐにページ アウトするのではなく、参照ビットが設定されているかどうかを確認します。設定されていない場合、ページはスワップ アウトされます。設定されている場合、参照ビットはクリアされ、ページはキューの後ろに挿入され (新しいページであるかのように)、このプロセスが繰り返されます。これは、循環キューと考えることもできます。すべてのページの参照ビットが設定されている場合、リストの最初のページに 2 度目に遭遇すると、そのページの参照ビットがクリアされているため、そのページはスワップ アウトされます。すべてのページの参照ビットがクリアされている場合、セカンドチャンス アルゴリズムは純粋な FIFO に退化します。

名前が示すように、セカンドチャンスはすべてのページに「セカンドチャンス」を与えます。参照されている古いページはおそらく使用中であり、参照されていない新しいページに交換されるべきではありません。

クロックは、ページを常にリストの後ろにプッシュする必要がないため、セカンドチャンスよりも効率的な FIFO のバージョンですが、セカンドチャンスと同じ一般的な機能を実行します。クロック アルゴリズムは、ページの循環リストをメモリ内に保持し、「ハンド」(反復子) はリスト内の最後に検査されたページ フレームを指します。ページ フォールトが発生し、空のフレームが存在しない場合は、ハンドの位置で R (参照) ビットが検査されます。R が 0 の場合、「ハンド」が指すページの代わりに新しいページが配置され、ハンドが 1 つ進みます。それ以外の場合は、R ビットがクリアされ、クロックの針がインクリメントされ、ページが置き換えられるまでプロセスが繰り返されます。^[8]このアルゴリズムは、1969 年にFernando J. Corbatóによって初めて説明されました。^[9]

• GCLOCK: 一般化されたクロックページ置換アルゴリズム。^[10]
• Clock-Proは、メモリ内のすべてのMページとページアウトされた最新のMページを含む、最近参照されたページに関する情報の循環リストを保持します。ページアウトされたページに関するこの追加情報は、ARCによって保持される同様の情報と同様に、大規模なループや1回限りのスキャンでLRUよりもうまく機能します。^[11]
• WSclock。^[12] Clockアルゴリズムをワーキングセット（つまり、ある時間間隔でそのプロセスによって使用されると予想されるページのセット）の概念と組み合わせることで、アルゴリズムのパフォーマンスを向上させることができます。実際には、「エージング」アルゴリズムと「WSClock」アルゴリズムがおそらく最も重要なページ置換アルゴリズムです。^{[13] [14]}
• クロックと適応型置換（CAR）は、 ARCに匹敵する性能を持ち、LRUとCLOCKの両方を大幅に上回るページ置換アルゴリズムです。 ^[15]アルゴリズムCARは自己調整型であり、ユーザー指定のマジックパラメータを必要としません。

CLOCK は保守的なアルゴリズムなので、競争力があります。 ${\displaystyle {\tfrac {k}{k-h+1}}}$

最も最近使われていない (LRU) ページ置換アルゴリズムは、名前は NRU に似ていますが、LRU は短期間のページ使用状況を追跡するのに対し、NRU は最後のクロック間隔での使用状況のみを調べるという点で異なります。LRU は、過去数個の命令で最も頻繁に使用されたページは、次の数個の命令でも頻繁に使用される可能性が高いという考えに基づいて機能します。LRU は理論上はほぼ最適なパフォーマンス (アダプティブ置換キャッシュとほぼ同等) を提供できますが、実際に実装するにはかなりコストがかかります。このアルゴリズムには、コストを削減しながらパフォーマンスを可能な限り維持しようとする実装方法がいくつかあります。

最もコストのかかる方法は、リンク リスト メソッドです。この方法では、メモリ内のすべてのページを含むリンク リストを使用します。このリストの最後尾には、最も最近使用されていないページがあり、先頭には最近使用されたページがあります。この実装のコストは、リスト内の項目をメモリ参照ごとに移動する必要があり、非常に時間のかかるプロセスであるという事実にあります。

ハードウェア サポートを必要とする別の方法は次のとおりです。ハードウェアに、命令ごとに増加する 64 ビット カウンターがあるとします。ページがアクセスされるたびに、ページ アクセス時のカウンターと同じ値を取得します。ページを置き換える必要があるときはいつでも、オペレーティング システムはカウンターが最も低いページを選択してスワップアウトします。

実装コストを考慮すると、LRU に似ているがより安価な実装を提供するアルゴリズム (次のようなもの) を検討することもできます。

LRU アルゴリズムの重要な利点の 1 つは、完全な統計分析が可能なことです。たとえば、LRU では OPT アルゴリズムよりも N 倍以上のページ フォールトが発生することは決してないことが証明されています。ここで、N は管理対象プール内のページ数に比例します。

一方、LRU の弱点は、非常に一般的な多くの参照パターンではパフォーマンスが低下する傾向があることです。たとえば、LRU プールに N ページがある場合、N + 1 ページの配列をループするアプリケーションは、アクセスのたびにページ フォールトを引き起こします。大きな配列をループすることはよくあることなので、そのような状況でより適切に動作するように LRU を変更することに多くの努力が払われてきました。提案されている LRU 変更の多くは、ループ参照パターンを検出し、Most Recently Used (MRU) などの適切な置換アルゴリズムに切り替えることを試みます。

1. LRU-K ^[16]は、 K番目に最近アクセスされたページが最も過去に遡るページを削除します。たとえば、LRU-1は単純にLRUですが、LRU-2は最後から2番目のアクセスの時間に従ってページを削除します。LRU-Kは、時間的局所性に関してLRUを大幅に改善しています。
2. ARC ^{[17]アルゴリズムは}、最近削除されたページの履歴を保持することでLRUを拡張し、これを使用して最近または頻繁にアクセスされたページの優先順位を変更します。特にシーケンシャルスキャンに対して耐性があります。
3. 2Q ^[18]アルゴリズムは、LRUおよびLRU/2アルゴリズムを改良したものです。ホットパス項目用とスローパス項目用の2つのキューを用意することで、項目は最初にスローパスキューに配置され、2回目のアクセス後にホットパス項目に配置されます。追加された項目への参照はLRUおよびLRU/2アルゴリズムよりも長く保持されるため、より優れたホットパスキューとなり、キャッシュのヒット率が向上します。

ARCと他のアルゴリズム（LRU、MQ、2Q、LRU-2、LRFU、LIRS）の比較については、Megiddo & Modha 2004を参照してください。^[19]

LRU はマーキング アルゴリズムなので、競合性があります。 ${\displaystyle {\tfrac {k}{k-h+1}}}$

ランダム置換アルゴリズムは、メモリ内のページをランダムに置換します。これにより、ページ参照を追跡するためのオーバーヘッドコストがなくなります。通常、このアルゴリズムは FIFO よりも優れており、ループするメモリ参照の場合は LRU よりも優れていますが、実際には LRU の方がパフォーマンスが優れています。OS /390 はグローバル LRU 近似を使用し、LRU パフォーマンスが低下するとランダム置換にフォールバックします。また、Intel i860プロセッサはランダム置換ポリシーを使用していました (Rhodehamel 1989 ^[20] )。

あまり使用されない (NFU) ページ置換アルゴリズムにはカウンターが必要で、各ページには 1 つのカウンターがあり、最初は 0 に設定されます。各クロック間隔で、その間隔内に参照されたすべてのページのカウンターが 1 ずつ増加します。実際には、カウンターはページが使用された頻度を追跡します。したがって、カウンターが最も低いページは、必要に応じてスワップ アウトできます。

NFU の主な問題は、使用期間に関係なく使用頻度を追跡することです。したがって、マルチパス コンパイラでは、最初のパスで頻繁に使用されたが 2 番目のパスでは必要のないページは、2 番目のパスで比較的使用頻度が低いページよりも優先されます。これは、それらのページの頻度カウンターが高いためです。この結果、パフォーマンスが低下します。OS の起動など、NFU が同様に機能する一般的なシナリオが他にもあります。ありがたいことに、同様の優れたアルゴリズムが存在し、その説明は次のとおりです。

ページ テーブルに NULL ポインター値が含まれている場合、あまり使用されないページ置換アルゴリズムでは、最も最近使用されていないページ置換アルゴリズムよりもページ フォールトが少なくなります。

エージング アルゴリズムは NFU アルゴリズムの派生で、使用期間を認識できるように変更されています。参照されたページのカウンターを単に増加させるのではなく、時間に関係なくページ参照に同等の重点を置き、まずページの参照カウンターを右にシフト (2 で割る) してから、そのバイナリ数値の左側に参照ビットを追加します。たとえば、ページが過去 6 クロック ティックでビット 1、0、0、1、1、0 を参照した場合、参照カウンターは時系列で次のようになります: 10000000、01000000、00100000、10010000、11001000、01100100。現在時刻に近いページ参照は、ずっと前のページ参照よりも影響が大きくなります。これにより、より最近参照されたページは、参照頻度は低くても、過去に頻繁に参照されたページよりも優先度が高くなります。したがって、ページをスワップアウトする必要がある場合は、カウンターが最も低いページが選択されます。

次のPythonコードはエージングアルゴリズムをシミュレートします。カウンターは次のように初期化されます。${\displaystyle V_{i}}$0となり、算術シフト演算子を使用して、上記のように更新されます。 ${\displaystyle V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)}$

 collections.abc からシーケンスをインポート 

def  sit_aging ( Rs :  Sequence ,  k :  int )  ->  None : 
    # 経年変化をシミュレートする
    print ( " t | R-bits (0- {length} ) | Counters for pages 0- {length} " . format ( length = len ( Rs ))) 
    Vs  =  [ 0 ]  *  len ( Rs [ 0 ]) 
    for  t ,  R  in  enumerate ( Rs ): 
        Vs [:]  =  [ R [ i ]  <<  ( k  -  1 )  |  V  >>  1 
                 for  i ,  V  in  enumerate ( Vs )] 
        print ( " {:02d}   |   {}   | [ {} ]" . format ( t ,  R , 
                                              ", " . join ([ "{:0 {} b}" . format ( V ,  k ) 
                                                         for  V  in  Vs ])))

5クロックティックにわたる6ページのRビットの例では、関数は次の出力を出力します。これは、各クロックティックtのRビットと各ページの個々のカウンター値をバイナリ表現でリストします。^[21]${\displaystyle V_{i}}$

>>> Rs  =  [[ 1 , 0 , 1 , 0 , 1 , 1 ],  [ 1 , 1 , 0 , 0 , 1 , 0 ], [ 1 , 1 , 0 , 1 , 0 , 1 ] , [ 1 , 0 , 0 , 0 , 1 , 0 ], [ 0 , 1 , 1 , 0 , 0 , 0 ]] >>> k = 8 >>> simulation_aging ( Rs , k ) t | R ビット (0-5) | ページ 0-5 のカウンター00 | [1, 0, 1, 0, 1, 1] | [10000000、00000000、10000000、00000000、10000000、10000000] 01 | [1, 1, 0, 0, 1, 0] | [11000000、10000000、01000000、00000000、11000000、01000000] 02 | [1、1、0、1、0、1] | [11100000、11000000、00100000、10000000、01100000、10100000] 03 | [1, 0, 0, 0, 1, 0] | [11110000、01100000、00010000、01000000、10110000、01010000] 04 | [0, 1, 1, 0, 0, 0] | [01111000、10110000、10001000、00100000、01011000、00101000]   
  
 

エージングは​​LRUとは異なり、最新の参照のみを追跡できることに注意してください。16/32 (プロセッサの整数のビット サイズによって異なります) の時間間隔。その結果、1 つのページが 9 間隔前に参照され、もう 1 つのページが 1000 間隔前に参照された場合でも、2 つのページの参照カウンタが 00000000 になることがあります。一般的に、過去 16 間隔内の使用状況がわかれば、どのページをスワップ アウトするかを適切に判断できます。したがって、エージングにより、適度なコストでほぼ最適なパフォーマンスを実現できます。

このアルゴリズムの基本的な考え方は、LRU で使用される参照の局所性ですが、LDF では、局所性は使用される参照ではなく距離に基づいているという点が異なります。LDF では、現在のページから最も遠い距離にあるページを置き換えます。2 つのページが同じ距離にある場合は、反時計回りで現在のページの次のページが置き換えられます。^{[引用が必要]}

上で説明した手法の多くは、各ページに関連付けられた参照ビットの存在を前提としています。一部のハードウェアにはそのようなビットがないため、効率的に使用するには、そのようなビットがなくても適切に動作する手法が必要です。

注目すべき例の 1 つは、OpenVMSを実行しているVAXハードウェアです。このシステムは、ページが変更されたかどうかは認識しますが、ページが読み取られたかどうかは必ずしも認識しません。その方法は、セカンダリ ページ キャッシュとして知られています。ワーキング セット (通常はプロセス専用メモリ) から削除されたページは、物理メモリ内にしばらく残っている間に、専用リストに配置されます。ワーキング セットからページを削除することは、技術的にはページ置換操作ではありませんが、実質的にそのページを候補として識別します。バッキング ストアがまだ有効なページ (コンテンツがダーティでないか、または保持する必要がないページ) は、空きページ リストの末尾に配置されます。バッキング ストアへの書き込みが必要なページは、変更ページ リストに配置されます。これらのアクションは通常、空きページ リストのサイズが調整可能なしきい値を下回ったときにトリガーされます。

ワーキング セットの削除対象としてページが選択される場合、選択を誤ると、将来の参照でそのページが物理メモリから削除される前に、空きリストまたは変更リストから取得される可能性があるという想定のもと、基本的にランダムに選択されます。このように参照されたページは、空きリストまたは変更リストから削除され、プロセスのワーキング セットに戻されます。変更ページ リストでは、複数のページをまとめてバックアップ ストアに書き出す機会も提供されるため、効率が向上します。これらのページは、空きページ リストに配置できます。空きページ リストの先頭まで進むページのシーケンスは、LRU または NRU メカニズムの結果に似ており、全体的な効果は前述のセカンドチャンス アルゴリズムと似ています。

もう 1 つの例は、ARM上のLinux カーネルで使用されています。ハードウェア機能の不足は、参照ビットもダーティ ビットもないプロセッサ ネイティブ ページ テーブルと、必要なビットが存在するソフトウェア管理ページ テーブルの 2 つのページ テーブルを提供することで補われています。ソフトウェア管理テーブル内のエミュレートされたビットは、ページ フォールトによって設定されます。ページ フォールトを取得するには、2 番目のテーブル内のエミュレートされたビットをクリアして、対応するページへのアクセス権の一部を取り消します。これは、ネイティブ テーブルを変更することで実装されます。

Linuxは統合ページキャッシュを使用して

• brkおよび匿名のmmaped領域。これには、ユーザー空間プログラムのヒープとスタックが含まれます。ページアウトされるとスワップに書き込まれます。
• 非匿名 (ファイル バック)mmap領域。メモリ内に存在し、非公開に変更されていない場合、物理ページはファイル キャッシュまたはバッファと共有されます。
• を通じて取得された共有メモリshm_open。
• tmpfsメモリ内ファイルシステム。ページアウト時にスワップに書き込まれます。
• ファイル キャッシュには、ページ アウト時に基礎となるブロック ストレージに書き込まれるもの (バッファーを通過する場合もあります。以下を参照) が含まれます。
• ブロック デバイスのキャッシュ。Linux では「バッファ」と呼ばれます (Linux で内部的に使用されるパイプやバッファに使用されるバッファなどの、バッファと呼ばれる他の構造と混同しないでください)。ページ アウトされると、基礎となるストレージに書き込まれます。

統合ページキャッシュは、CPU がサポートする最小のページサイズ ( ARMv8、x86、x86-64では 4 KiB ) の単位で動作し、次に大きいサイズ ( x86-64では 2 MiB ) のページは Linux では「巨大ページ」と呼ばれます。ページキャッシュ内のページは、「アクティブ」セットと「非アクティブ」セットに分割されます。両方のセットはページの LRU リストを保持します。基本的なケースでは、ページがユーザー空間プログラムによってアクセスされると、そのページは非アクティブ セットの先頭に配置されます。繰り返しアクセスされると、アクティブ リストに移動されます。Linux は、必要に応じてページをアクティブ セットから非アクティブ セットに移動し、アクティブ セットが非アクティブ セットよりも小さくなるようにしています。ページが非アクティブ セットに移動されると、物理メモリからページ アウトされることなく、すべてのプロセス アドレス空間のページ テーブルから削除されます。^{[22] [23]}ページが非アクティブ セットから削除されると、物理メモリからページ アウトされます。 「アクティブ」および「非アクティブ」リストのサイズは/proc/meminfo、「アクティブ」、「非アクティブ」、「アクティブ(匿名)」、「非アクティブ(匿名)」、「アクティブ(ファイル)」および「非アクティブ(ファイル)」フィールドで照会できます。

プロセスのワーキング セットとは、ある時間間隔中にそのプロセスによって使用されることが予想されるページのセットです。

「ワーキング セット モデル」は厳密な意味でのページ置換アルゴリズムではありません (実際には中期スケジューラの一種です) ^{[説明が必要]}