ページ置換アルゴリズム_html/css_WEB-ITnose

最適置換アルゴリズム

最適置換アルゴリズムは、最高のパフォーマンスを持つ理想化されたアルゴリズムですが、実際には (現時点では) 達成できません。

最適置換アルゴリズムは、1966 年に Belady によって提案された理論的なアルゴリズムです。削除対象として選択されるページは、将来的には決して使用されず、最も長い期間 (将来) にはアクセスされなくなるページである可能性があります。通常、最適な置換アルゴリズムを使用すると、ページ フォールト率を最小限に抑えることができます。ただし、プロセスのメモリの複数のページのうち、将来的にどのページが最も長くアクセスされなくなるかは現時点では予測できないため、このアルゴリズムを実装することはできません 。以下に例を示します。

システムが 3 つの物理ブロックを 1 つのプロセスに割り当てると仮定し、次のページ番号参照文字列を考慮します:

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0 , 3, 2, 1, 2, 0, 1, 7, 0, 1

プロセスの実行中、最初に 3 つのページ 7、0、1 がメモリにロードされます。その後、プロセスがページ 2 にアクセスしようとすると、
はページ フォールト割り込み を生成します。このとき、OS は最適置換アルゴリズムに基づいて、選択されたページ 7 を削除します。これは、ページ 0 は 5 番目に訪問されるページであり、ページ 1 は 14 番目に訪問されるページであり、ページ 7 は 18 番目に訪問されるまでロードされないためです。次回ページ 0 がアクセスされるとき、ページ 0 はすでにメモリ内にあるため、ページ フォールト割り込みを生成する必要はありません。プロセスがページ 3 にアクセスすると、ページ 1 が削除されます。これは、既存の 3 つのページ 1、2、および 0 のうち、今後アクセスされるのはページ 1 であるためです。図 4-26 は、最適置換アルゴリズムを使用した場合の置換グラフを示しています。図からわかるように、最適置換アルゴリズムを使用すると、6 ページの置換が発生しました。

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

これは最も早い置換アルゴリズムです。このアルゴリズムは常に

最初にメモリに入ったページを削除します、つまり、メモリ内に最も長く存在していたページを選択して削除します。このアルゴリズムは、プロセスの実際の実行ルールと互換性がありません。プロセスでは一部のページが頻繁にアクセスされ、FIFO アルゴリズムはこれらのページが削除されないことを保証できないためです。
上記の例を引き続き使用しますが、ページ置換には FIFO アルゴリズムを使用します (以下に示すように)。プロセスが最初にページ 2 にアクセスすると、最初にメモリに転送されるためページ 7 がスワップアウトされ、ページ 3 に初めてアクセスすると、ページ 0 がメモリ内にあるためスワップアウトされます。既存の 3 ページ 2、0、1 のうち、最も古いページです。図 4-27 からわかるように、FIFO アルゴリズムを使用すると、

12 ページの置換が実行されます。これは、最適な置換アルゴリズムのちょうど 2 倍です。

注: 3 が初めてメモリに置き換えられると、1 ではなく 0 に置き換えられます (0 は 3 より前にアクセスされたばかりですが、メモリ内の 0 は依然として 1 ページより前に到着したメモリです)

最近使用されていない最長 (LRU) 置換アルゴリズム

最近最も長く使用されていない (LRU) ページの置換アルゴリズムは、それに基づいて決定を行います。ページがメモリに転送された後の使用法について。 LRU 置換アルゴリズムは、
最近使用されていないページを選択し、それらを削除します

。このアルゴリズムは、各ページに 訪問フィールド を与えます。これは、ページを削除する必要がある場合に、最大の t 値を持つ既存のページを 記録するために使用されます。選択されている場合、つまり、長期間使用されていないページは削除されます。 上記の例で LRU アルゴリズムを使用したページ置換の結果を図に示します。プロセスが初めてページ 2 にアクセスすると、長期間アクセスされていなかったため、ページ 7 が置き換えられます。プロセスが初めてページ 3 にアクセスすると、ページ 1 が最後に使用されていなかったページになるため、スワップアウトされます。最適な置換アルゴリズムは「後ろ向き」の観点、つまり各ページの将来の使用状況に基づいていますが、LRU アルゴリズムは「前向き」、つまり各ページの以前の使用状況に基づいています。ページの過去と将来の方向の間には必然的なつながりはありません。

この記事は Cout_Sev

によって収集、整理、および修正されました

『Computer Operating System (Third Edition)』 (Xidian University Press) より

転載する場合は出典を明記してください。

ありがとうございます！