コード例を通してページ置換アルゴリズムの原理を理解する

ページ置換アルゴリズム: 本質は、限られたメモリをワイヤレスプロセスに対応できるようにすることです。

まず、ページフォールトを処理するプロセスについて説明します。

ページングハードウェアは、ページテーブルを介してアドレスを変換するときに無効なビットが設定されていることに気づき、オペレーティングシステムをトラップします。このトラップは、オペレーティングシステムが必要なページをメモリに取り込むことに失敗したために発生します。

ページフォールトの処理:

1. このプロセスの内部テーブルをチェックして、参照が有効なメモリアクセスであるかどうかを判断します (このメモリは現在のプロセスで使用できることがわかります)。無効な場合は、プロセスを直接終了します。有効であるがページがメモリにロードされていない場合は、ページをメモリにロードします。

2. 次に、アイドルフレームリストからアイドルフレームを見つけます。

3. プロセスに必要なメモリをページフレームに読み込むようにディスクをスケジュールします。

4. ディスクの読み取りが完了したら、空きフレームがページ番号に対応するようにページテーブルを変更します。そして、ページテーブルの有効/無効ビットを有効に変更します。

ページテーブル内のいくつかのフラグに注意してください。

変更ビット: 有効ビットが1の場合は変更されていることを意味するため、ページを置き換えるときにメモリをディスクに書き込む必要があります。0の場合は変更されていないことを意味するため、ページ置き換えアルゴリズムを使用して直接解放します。

保護ビット: 読み取り専用、書き込みとしてマークできます。

有効無効ビット: i: 論理ページ番号が物理ページフレームに対応していないことを示し、V は対応する物理ページフレームがあることを示します。

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

FIFO: アルゴリズム

オペレーティングシステムは、メモリ内に最も長く留まっているページを常に置き換えます。この場所を指すためにポインタを使用できます (オーバーヘッドは非常に小さく、キューを使用して実装できます。ページフォールトが発生するたびに、最後のページが削除され、新しいページがキューの先頭に追加されます。ページフォールトが発生しない場合は、キューを操作する必要はありません)

LRU アルゴリズム: オペレーティングシステムは、メモリ内で最も長い時間使用されていないページを常に置き換えます。このアルゴリズムを実装するには、リンクリストを使用できます。テーブルの先頭は最近使用されたページを示し、テーブルの末尾は最も長い時間使用されていないページを示します。ページフォールトの発生に関係なく、リンクリストの追加、削除、変更、およびチェックを毎回チェックして、各リンクリストが必要なものかどうかを確認する必要があります (オーバーヘッドが大きすぎます)

近似 LRU アルゴリズム: ページテーブルに参照ビットクロックを追加します。クロックが 1 の場合、移動できません。クロックが 0 の場合、削除できることを示します。

手順 t: {
  ポインタ p: 現在のページを指す p = 0; // 初期位置を指す boolean: フラグ ビット クロック
  プロセスに含まれるすべてのページの循環リンクリスト: linklist //プロセスが実行中の場合、リンクリストが存在し、プロセスが終了すると、リンクリストは消えます while (プロセス実行中) {
    
    p.clock == 1の場合{
      p.クロック = 0;
      p++; // ポインタは次のポインタを指す }
    p.clock == 0の場合{
      p が指すページを削除し、p に新しいページを追加します。
      p.クロック = 1;
      p++;
    }
  }
}

近似LRU拡張アルゴリズム：変更ビットと参照ビットを置換条件として組み合わせる：（変更ビット、参照ビット）=（0、0）の場合、置換可能であることを示す

手順 t: {
  ポインタ p: 現在のページを指す p = 0; // 初期位置を指す boolean: フラグ ビット クロック
  ブール値: ビット m を変更する
  プロセスに含まれるすべてのページの循環リンクリスト: linklist //プロセスが実行中の場合、リンクリストが存在し、プロセスが終了すると、リンクリストは消えます while (プロセス実行中) {
    
  
    p.(時計,m) == (0,0) の場合{
      
      p が指すページを削除し、p に新しいページを追加します。
      p.(時計,m) = (1,0);
      p++;
    }
    p.(時計,m) == (0,1) の場合{
      
      
      p.(時計,m) = (0,0);
      p++;
    }
    p.(時計,m) == (1,0) の場合{
      
      
      p.(時計,m) = (0,0);
      p++;
    }
    p.(時計,m) == (1,1) の場合{
      
      p.(時計,m) = (0,1);
      p++;
    }
    if (ページを変更) {
      p.(時計,m) = (1,1);
      p++
    }
    if (ページを読む) {
      p.(時計,m) = (1,0);
      p++;
    }
  }
}

ページバッファーアルゴリズム: オペレーティングシステムは空きフレームのプールを予約します。

ページフォールトが発生すると、必要なページは空きフレームを読み取り、置き換えられた犠牲フレームをバッファプールに入れます。ページングアイドル期間中、バッファプール内の犠牲フレームの内容がディスクに書き込まれます（ページテーブルの変更ビットが 1 の場合）（オペレーティングシステムのページング中の直接ディスクアクセスのプロセスが削減され、ページング効率が向上します）。

2 番目の方法は、犠牲フレームの内容をディスクに書き込むが、フレームの内容を解放しないことです。プロセスが前のページを呼び出す可能性があるため、バッファプール内のフレームが直接メモリに書き込まれるため、(ディスクからデータを読み取る操作) が削減されます。

上記はすべてローカルページ置換アルゴリズムであり、単一プロセス内で実行されるページ置換操作です。ただし、オペレーティングシステムの動作中に異なるプロセスを並行して実行できるため、ページの置換は単一プロセスに限定されません。

次に、グローバル置換アルゴリズムを学習します。作業セットと常駐セットを指定します。ワーキングセットは、現在のプログラムがアクセスする必要がある Δ ページを示し、常駐セットは、オペレーティングシステムが使用しているページを示します。

ワーキングセット: WS(Δ, t) = {} ワーキングセットは常に移動しており、オペレーティングシステムはワーキングセットにないページを置き換えます。

動的ワーキングセットページ置換アルゴリズム: 下の図に示すように、しきい値ウィンドウサイズを 2 に設定します。2 つのページフォールト中断の差 (2 つの中断の間に中断がなかった回数を示します) を使用してしきい値と比較します。しきい値より大きい場合、現在のワーキングセットのページはスワップアウトされなくなり、ワーキングセットのサイズがリセットされます。しきい値より小さい場合、不足しているページはワーキングセットにスワップされ、ワーキングセットのサイズがリセットされます。