ページ置換アルゴリズムとは何ですか?

アドレスマッピング処理中に、アクセスしようとしているページがメモリ上に存在しないことがページ内で判明した場合、ページフォルト割り込みが発生します。ページ フォールトが発生したとき、オペレーティング システムのメモリに空きページがない場合、オペレーティング システムはメモリ内のページを選択し、それをメモリの外に移動して、ページが転送されるスペースを確保する必要があります。削除するページを選択するために使用されるルールは、ページ置換アルゴリズムと呼ばれます。

一般的な置換アルゴリズム

最適置換アルゴリズム (OPT)

これは、理想的なページ置換アルゴリズムですが、実際には実装することは不可能です。このアルゴリズムの基本的な考え方は次のとおりです。ページ フォールトが発生すると、一部のページがメモリ内に存在し、そのうちの 1 つはすぐにアクセスされますが (次の命令のページも含まれます)、他のページは 10 時までアクセスされない可能性があります。 100 または 1000 命令後にアクセスされます。ページに初めてアクセスする前に、各ページに実行する命令の数を [1] マークすることができます。最適なページ置換アルゴリズムは、マークアップが最も大きいページを置換する必要があると単純に示します。このアルゴリズムの唯一の問題は、実装できないことです。ページフォールトが発生すると、オペレーティングシステムは各ページが次にいつアクセスされるかを知ることができません。このアルゴリズムを実装することはできませんが、最適なページ置換アルゴリズムを使用して、達成可能なアルゴリズムのパフォーマンスを測定および比較することができます。

先入れ先出し置換アルゴリズム (FIFO)

最も単純なページ置換アルゴリズムは、先入れ先出し (FIFO) 方式です。このアルゴリズムの本質は、メイン メモリに最も長く残っている (つまり最も古い) ページを常に選択して置換することです。つまり、最初にメモリに入り、最初にメモリから出るページです。その理由は、メモリに転送された最初のページは、メモリに転送されたばかりのページよりも使用されなくなる可能性が高いためです。すべてのページをメモリに保存するための FIFO キューを作成します。置換されたページは常にキューの先頭に配置されます。ページがメモリに置かれると、キューの最後に挿入されます。

このアルゴリズムは、アドレス空間 [1] に線形順序でアクセスする場合にのみ理想的であり、それ以外の場合は効率的ではありません。頻繁にアクセスされるページはメイン メモリに最も長く留まる傾向があり、その結果、「古くなった」ため置き換える必要があるからです。

FIFO のもう 1 つの欠点は、ストレージ ブロックを追加するとページ フォルト割り込み率が増加するという異常現象があることです。もちろん、この異常を引き起こすページ方向は実際にはまれです。

最近未使用 (LRU) アルゴリズム

FIFO アルゴリズムと OPT アルゴリズムの主な違いは、FIFO アルゴリズムではページが入ってからの時間の長さを使用することです。代替としてのメモリ OPT アルゴリズムの基礎は、ページが将来使用される時刻です。最近の過去を近い将来の近似値として使用する場合、過去に最も長期間使用されていないページを置き換えることができます。その本質は、ページを置換する必要がある場合、以前の期間で最も長期間使用されていないページが置換対象として選択されることです。このアルゴリズムは、最も最近使用されていないアルゴリズム (Least Recently Used、LRU) と呼ばれます。

LRU アルゴリズムは、各ページが最後に使用された時間に関連しています。ページを置換する必要がある場合、LRU アルゴリズムは、過去の期間で最も使用されていないページを選択します。

LRU アルゴリズムは頻繁に使用されるページ置換アルゴリズムであり、非常に優れていると考えられていますが、実装方法に問題があります。

LRU アルゴリズムには、実際のハードウェアのサポートが必要です。

問題は、最終使用時刻の順序をどのように決定するかですが、これには 2 つの方法が考えられます:

1. カウンタ。

最も単純なケースは、各ページ テーブル エントリを使用時間フィールドに対応させ、論理クロックまたはカウンタを CPU に追加することです。このクロックはメモリアクセスごとに 1 ずつ増加します。ページがアクセスされるたびに、クロック レジスタの内容が、対応するページ テーブル エントリの使用時間フィールドにコピーされます。こうすることで、各ページが最後にアクセスされたときの「時刻」を常に保持することができます。ページを入れ替える場合は、時間値が最も小さいページを選択します。その際、ページ テーブルをルックアップするだけでなく、(CPU スケジューリングにより) ページ テーブルが変更されたときにページ テーブル内の時間を維持する必要があり、クロック値のオーバーフローの問題も考慮する必要があります。 。

2. スタックします。

スタックを使用してページ番号を保持します。ページがアクセスされるたびに、そのページはスタックから取り出され、スタックの一番上に置かれます。このようにして、最も使用されているページは常にスタックの一番上に配置され、最も使用されていないページはスタックの一番下に配置されます。項目はスタックの中央から削除する必要があるため、先頭ポインタと末尾ポインタを持つ双方向チェーンを使用して接続します。最悪の場合、ページを削除してスタックの一番上に置くには、6 つのポインターを変更する必要があります。変更ごとにオーバーヘッドが発生しますが、テールポインタがスタックの一番下、つまり置換されるページがある場所を指しているため、置換する必要があるページは検索せずに直接取得できます。

LRU アルゴリズムの実装には大量のハードウェア サポートが必要であるため、ある程度のソフトウェア オーバーヘッドも必要になります。したがって、実際に実装されるのは、シンプルで効果的な LRU 近似アルゴリズムです。

LRU 近似アルゴリズムの 1 つは、最近使用されていない (NUR) アルゴリズムです。

ストレージ ブロック テーブルの各エントリに参照ビットを追加し、オペレーティング システムはそれらを定期的に 0 に設定します。ページがアクセスされると、このビットはハードウェアによって設定されます。時間の経過とともに、これらのビットを検査して、最後に 0 に設定されてからどのページが使用され、どのページが使用されていないかを判断できます。ビットが 0 のページは、最近アクセスされていないため、削除できます。

4) クロック置換アルゴリズム (LRU アルゴリズムのおおよその実装)

5) 最も使用されていない (LFU) 置換アルゴリズム

最も使用されていない置換アルゴリズムを使用する場合、次のようにする必要があります。メモリ内の各ページには、ページがアクセスされる頻度を記録するためのシフト レジスタが設定されています。置換アルゴリズムは、前の期間で最も使用されていなかったページを排除ページとして選択します。

メモリは 100 ns などの高速アクセス速度を持っているため、1 ミリ秒以内にページに連続して数千回アクセスされる可能性があるため、通常はカウンタを直接使用してページ数を記録することはできません。ページがアクセスされる回数の代わりに、シフト レジスタ方式を使用します。ページにアクセスするたびにシフトレジスタの最上位ビットが1にセットされ、一定時間(例えば100ns)ごとに右にシフトされます。このようにして、最近の期間で最も使用されていないページが、ΣRi が最も小さいページになります。

LFU 置換アルゴリズムのページ アクセス グラフは、LRU 置換アルゴリズムのアクセス グラフとまったく同じです。つまり、このようなハードウェアのセットを使用すると、LRU アルゴリズムと LFU アルゴリズムの両方を実装できます。 LFU アルゴリズムはページ使用量を実際には反映しないことに注意してください。各時間間隔でページ使用量の記録にレジスタの 1 ビットのみが使用されるため、1 回のアクセスは 10,000 回のアクセスに相当します。

6) ワーキング セット アルゴリズム

7) ワーキング セット クロック アルゴリズム

8) エージング アルゴリズム (LRU によく似た効率的なアルゴリズム)

9) NRU (最近使用されていません) アルゴリズム

10) セカンド チャンス アルゴリズム

セカンド チャンス アルゴリズムの基本的な考え方は FIFO と同じですが、頻繁に使用されるページを避けるように改良されました交換してください。置換ページが選択されると、そのアクセス ビットがチェックされます。 0 の場合、そのページは削除され、アクセス ビットが 1 の場合、2 回目のチャンスが与えられ、次の FIFO ページが選択されます。ページが 2 回目のチャンスを得るとき、そのアクセス ビットは 0 にクリアされ、その到着時刻は現在時刻に設定されます。この期間中にページが訪問された場合、位置 1 が訪問されます。このようにして 2 回目のチャンスが与えられたページは、他のすべてのページが削除されるまで (または 2 回目のチャンスが与えられるまで) 削除されません。したがって、頻繁に使用されるページのアクセスビットは常に 1 のままとなり、削除されることはありません。

セカンド チャンス アルゴリズムは、循環キューとして見ることができます。ポインタを使用して、次に削除するページを示します。メモリのブロックが必要な場合、アクセス ビットが 0 のページが見つかるまでポインタが進みます。ポインタが進むと、アクセス ビットは 0 にクリアされます。最悪の場合、すべてのアクセス ビットが 1 になり、ポインタは 1 週間キュー全体を通過し、各ページに 2 回目のチャンスが与えられます。このとき、FIFO アルゴリズムに縮退します。

以上がページ置換アルゴリズムとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。