図: ページ置換アルゴリズム

[[398509]]

この記事はWeChatの公開アカウント「Jingyu」から転載したもので、著者はJingyuです。記事を転載する場合はJingyuの公式アカウントまでご連絡ください。

ページ置換アルゴリズム

機能: ページ フォールトが発生し、新しいページをロードする必要があるがメモリがいっぱいの場合、メモリ内のどの物理ページを置き換えるかを選択します。

目標: ページスワップ (ページフォールト) の数を可能な限り減らします。具体的には、将来使用されなくなるページや短期的に使用頻度が低いページのスワップアウトは、通常、ローカル原則のガイダンスに従って過去の統計データに基づいてのみ予測できます。

最適なページ置換アルゴリズム

基本的な考え方は、ページ フォールトが発生すると、メモリに格納されている各論理ページについて、次のアクセスまでの待機時間を計算し、待機時間が最も長いページを置換するページとして選択することです。

これは単なる理想的な状況であり、オペレーティング システムは各ページが再度アクセスされるまでにどれだけの時間を待機するかを認識できないため、実際には実現できません。

他のアルゴリズムのパフォーマンス評価の基礎として使用できます (シミュレータ上でプログラムを実行し、各ページ アクセスを記録し、2 回目の実行で最適なアルゴリズムを使用します)。

簡単に言えば、最適なページ置換アルゴリズムは、将来最も長い間必要とされないページを置換することです。

ページ フレームのサイズが 4 で、要求されたページの順序が 7、0、1、2、0、3、0、4、2、3、0、3、2 であると仮定します。最適なページ置換アルゴリズムを使用すると、ページ フォールトはいくつ発生しますか。

最初はすべてのページ スロットが空なので、要求されたページ 7 0 1 2 は空のページ スロットに割り当てられ、4 つのページ フォールト例外が発生します。

次に、ページ 0 が要求されると、ページ フレーム内に既に存在することが判明し、ページ フォールト例外が 0 個発生します。

ページ 3 が要求されると、ページ 7 は将来最も長い間アクセスされないため、ページ 3 に置き換えられ、ページ フォールト例外が発生します。

ページ 0 ヒット、ページ例外 0 件。

要求されたページ 4 はページ フレームに存在しないため、ページ 1 が置き換えられ、ページ フォールト例外が 1 つ発生します。

後続の要求されたページ シーケンス 2、3、0、3、2 はすべてヒットなので、ページ フォールト例外は発生しません。

したがって、合計 6 個のページ フォールト例外が発生しました。これは、図の Miss 状態です。Hit はヒットを意味し、ページ フォールト例外は発生しませんでした。

最適なページ置換アルゴリズムをシミュレートして実装します。

入力: ページフレーム番号 fn = 3

ページpg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

出力: ヒット数 = 11 ページフォールト数 = 9

入力: ページフレーム番号 fn = 4 ページ pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};

出力: ヒット数 = 7 ページフォールト数 = 6

ページフレーム番号 4 とリクエストシーケンス {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2} を例に挙げます。

まず、ページ フレームをシミュレートするために空の配列 fr を作成します。

ページ 7 を要求し、それが配列 fr に存在せず、配列 fr のサイズが fr.size() < fn ページ フレーム サイズであることがわかったら、要求されたページ 7 を配列 fr に直接挿入します。

ページ {0,1,2} を要求することはページ 7 を要求することと似ているため、順番に配列に追加します。

次に、ページ 0 が要求され、配列 fr が走査されます。ページ 0 がすでに配列内に存在することが判明した場合、ヒット カウント hit が 1 増加します。

ページ 3 を要求し、配列 fr を走査して、その中にページが存在せず、配列がいっぱい (fr.size == fn) であることを確認したら、置き換えるページを見つける必要があります。この時点で、将来最も長い間必要とされないページを置き換えることを選択します。ここで、ページ配列 pg[] の添え字を使用して、将来最も長い間必要とされないページを表すことができます。

配列 fr[] を走査し、それをリクエスト ページ配列 pg[] と組み合わせて、将来最も長い間必要とされないページを見つけます。

fr[0] = 7。ページ3から始めて、配列pg[]でページ7を逆方向に検索します。ページ7は存在しないことがわかります。これは、ページ7が将来最も長い間必要とされないページであることを意味します。したがって、ページ 3 がページ 7 に置き換えられます。

ページ 0 に再度アクセスし、存在する場合はスキップします。

ページ 4 にアクセスし、ページ フレーム配列 fr にないことがわかったら、今後長期間必要のないページ 1 を置き換えます。

その後、ページ {2、3、0、3、2} がすべてヒットし、合計 6 件のヒットがありました。

リファレンス実装

#include <bits/stdc++.h>
名前空間 std を使用します。 
 
 // 現在アクセスしているページキーがページフレーム内に存在するかどうかを確認するために使用されます 
ブール検索( int  キー、ベクトル< int >& fr)
 {
 ( int i = 0; i < fr.size ( ) ); i++)の場合
        if (fr[i] ==キー)
戻る 真実;
戻る 間違い;
 } 
 
 // 未来を予測するために使用される
int予測( int pg[], ベクトル< int >& fr, int pn, int  索引）
 {
    // 将来最も最近使用されるページのインデックスを保存します
int res = -1、farthest =インデックス;
 ( int i = 0; i < fr.size ( ) ); i++) {
整数j;
 ( j =インデックス; j < pn; j++) {
           fr[i] == pg[j]の場合{
                (j > 最も遠い) の場合 {
                     最も遠い = j;
                     解像度 = i;
                }
                壊す;
            }
        } 
 
        // ページが将来参照されない場合は、そのページを返します。
        (j == pn)の場合
iを返します。
     }
      // fr 内のすべてのページが将来表示されない場合は、いずれのページに対しても 0 を返します。それ以外の場合は res を返します。
戻り値(res == -1) ? 0 : res;
 } 
 
 /**
 * pg[] リクエストページシーケンス
 * pn リクエストページ番号
 * fn ページフレーム
 */
 。
 void 最適なページ( int pg[], int pn, int fn)
 {
    // 指定されたフレーム数の配列を作成し、空に初期化します。
   ベクトル< int > fr; 
 
   // ページ参照配列を反復処理し、ミスとヒットをチェックします。
ヒット= 0;
 ( int i = 0; i < pn; i++)の場合{
      // メモリ内のページをヒット: HIT
      if (search(pg[i], fr)) {
         ヒット++;
続く;
      }
      // ページがメモリ内に存在しません: MISS
      // ページ フレームに使用可能なスペースがある場合は、不足しているページをそのスペースに追加するだけです。
      fr.size () < fnの場合{
           fr.push_back(pg[i]);
      }
 else { // 置き換えるページを見つける
整数j = 予測 (pg、fr、pn、i + 1)。
           fr[j] = pg[i];
        }
     }
     cout << "ヒット数 = " << hit << endl;
     cout << "ミス数 = " << pn - hit << endl;
 } 
 
 intメイン()
 {
 int pg[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 };
 pg[0]のサイズを整数pnで割ったもの。
整数fn = 4;
     最適なページ(pg、pn、fn);
 0を返します。
 }

検索関数は、ハッシュやバイナリ検索などに置き換えることができます。最も重要なのは、将来最も長い間使用されないページを見つけるために使用される、predict() 関数です。実際には、これは 2 層のネストされた for ループです。

先入先出アルゴリズム

FIFO (First In, First Out) は先入れ先出しアルゴリズムです。

基本的な考え方は、メモリ内に最も長く保存されているページを選択して削除することです。具体的には、システムはメモリ内のすべての論理ページを記録するリンク リストを維持します。リンク リストの順序から、チェーンの先頭にあるページの滞留時間が最も長く、チェーンの末尾にあるページの滞留時間が最も短くなります。ページ フォールトが発生すると、チェーンの先頭にあるページが削除され、新しいページがリンク リストの末尾に追加されます。

パフォーマンスが悪く、呼び出されるページが頻繁にアクセスされるページである可能性があり、Belady 現象が発生します。FIFO アルゴリズムが単独で使用されることはほとんどありません。

ページ フレームのサイズが 4 で、要求されたページの順序が 7、0、1、2、0、3、0、4、2、3、0、3、2 であると仮定します。FIFO アルゴリズムを使用すると、ページ フォールト例外はいくつ発生しますか。

上の図に示すように、FIFO (先入れ先出し) にはキューのような機能があります。

要求されたページ 7、0、1、および 2 では、それぞれ割り当てられたページである 4 つのページ フォールトが発生します。

ページ 0 にアクセスすると、ヒットします。

ページ3にアクセスすると、ページフォールト例外が発生します。このとき、キューの先頭にあるページ7は削除され、キューの最後にページ3が挿入されます。つまり、メモリ内に最も長く常駐していたページが選択され、削除されます。

ページ 0 ヒット;

ページ 4 にアクセスするとページ フォールト例外が発生し、ページ 0 が削除されます。

ページ 2 と 3 にアクセスすると、両方ヒットします。

ページ 0 にアクセスするとページ フォールトが発生し、ページ 1 が削除され、ページ 0 が挿入されます。

最後にアクセスしたページ 3 と 2 は両方ともヒットしました。

合計 7 個のページ フォールト例外が発生しました。

最も最近使われていないアルゴリズム

最も最近使われていないページ置換アルゴリズムの詳細については、「最も最近使われていない LRU アルゴリズム」を参照してください。

時計ページ置換アルゴリズム

クロック ページ置換アルゴリズム、LRU の近似、FIFO の改良。

基本的な考え方:

• ページ テーブルの上部にあるアクセス ビットが必要です。ページがメモリにロードされると、ビットは 0 に初期化されます。その後、このページがアクセスされると (読み取りまたは書き込み)、この位置は 1 に設定されます。
• ページを循環リンク リスト (時計の文字盤に似ています) に整理し、ポインターが最も古いページ (最初に表示されたページ) を指すようにします。
• ページ フォールトが発生した場合、ポインターが指している最も古いページをチェックします。そのアクセス ビットが 0 の場合は、すぐにそのページを削除します。アクセス ビットが 1 の場合は、位置を 0 に設定し、ポインターを 1 グリッド下に移動します。このプロセスは、削除されたページが見つかるまで継続され、その後ポインターは次のページに移動します。

ページ フレームのサイズが 4 で、要求されたページの順序が 7、0、1、2、0、3、0、4、2、3、0、3、2 であると仮定します。クロック ページ置換アルゴリズムを使用すると、ページ フォールト例外はいくつ発生しますか。

最初は、ページ フレームは空で、下の図に示すように、円形のリンク リストのようになっています。時計のように見えませんか?

ページ 7 を要求するとページ フォールト割り込みが生成されるため、ページ 7 がメモリにロードされ、ページのアクセス ビットが 0 に初期化されます。

前の方法と同様に、ページ 0、1、2 を順番にアクセスします。

次に、ページ 0 の要求が行われます。ページ 0 がすでにメモリ内にある場合、ハードウェアはアクセス ビットを 1 に設定し、ポインタを下に移動します。

ページ 3 が要求されると、ページ フォールトが発生します。このとき、ポインタが指すページ 7 のアクセス ビットは 0 であるため、すぐに削除され、アクセス ビットが 1 のページ 3 に置き換えられます。

すでにメモリ内にあるページ 0 を要求し、ハードウェアがそのアクセス ビットを 1 に設定します。前の図と同じで、変更はありません。

ページ 4 を要求すると、ページ フォールトが発生し、最初にページ 3 のアクセス位置を 0 に設定し、ページ 0 のアクセス位置を 0 に設定してポインタを下に移動し、ページ 1 のアクセス ビットが 0 であることを確認します。次に、ページ 1 を削除してページ 4 に置き換え、アクセス位置 1 に設定してポインタを下に移動します。

すでにメモリ内にあるページ 2 を要求し、ハードウェアはそれをアクセス位置 1 に配置します。

ページ 3 を要求し、ページ 3 のアクセス ビットを 1 に設定し、ポインタを下に移動します。

ページ 0 を要求し、ページ 0 のアクセス位置を 1 に設定し、ポインターを下に移動します。

ページフォールトの合計数は 5 です。

最も使用頻度の低いアルゴリズムLFU

基本的な考え方: ページ フォールトが発生した場合、アクセス回数が最も少ないページを選択して排除します。

実装方法：ページごとにアクセスカウンターを設定します。ページがアクセスされるたびに、ページのアクセスカウンターが 1 増加します。ページ フォールトが発生すると、カウント値が最も小さいページが削除されます。すべてのページの頻度が同じ場合、そのページに対して LRU アプローチが採用され、ページが削除されます。

LRU と LFU の違い: LRU はアクセスされていない時間を調べ、時間が短いほど優れています。一方、LFU はアクセス回数または頻度を考慮し、アクセスが多いほど優れています。

この記事はWeChatの公式アカウント「Jingyu」から転載したもので、以下のQRコードからフォローできます。記事を転載する場合はJingyuの公式アカウントまでご連絡ください。