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

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

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

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

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

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

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 つの中断の間に中断がなかった回数を示します) を使用してしきい値と比較します。しきい値より大きい場合、現在のワーキング セットのページはスワップ アウトされなくなり、ワーキング セットのサイズがリセットされます。しきい値より小さい場合、不足しているページはワーキング セットにスワップされ、ワー​​キング セットのサイズがリセットされます。

以上がこの記事の全内容です。皆様の勉強のお役に立てれば幸いです。また、123WORDPRESS.COM を応援していただければ幸いです。

以下もご興味があるかもしれません:
  • Python機械学習ライブラリxgboostの使用
  • エンジニアはLRUキャッシュ除去アルゴリズムとPython実装プロセスを理解する必要があります
  • Nginx 7層負荷分散のいくつかのスケジューリングアルゴリズムの簡単な理解
  • 機械学習について知っておくべきトップ10のアルゴリズムについて簡単に説明します
  • マージソートの時間計算量の導出の詳細な説明

<<:  バントリストコンポーネントをスクロールしても、スクロールバーの位置は保持されます。

>>:  Ubuntu 20.04でルートアカウントを有効にする方法

推薦する

HTML で入力プロンプトのテキスト スタイルを変更するためのサンプル コード

多くのウェブサイトでは、入力ボックスにヒントテキストが表示されています。入力ボックスにヒントテキスト...

Vue がルート変更を監視するときに watch メソッドが複数回実行される理由と解決策

目次要件の説明:要件分析:ニーズの解決問題解決私はフロントエンドの新人ですが、バックエンドのバグの中...

この記事では、Vue 3.0 レスポンシブの使い方を説明します。

目次ユースケースリアクティブAPI関連プロセス反応的なcreateReactiveObjectはレス...

iconfontアイコンライブラリをvueに導入するエレガントな実践記録

目次序文SVGを生成するSVGスプライトの紹介プロジェクトアイコンを取得するプロジェクトのセットアッ...

Mysql で group_concat の長さ制限を変更する方法

MySQL には、「group_concat」という関数があります。通常の使用では問題がないかもしれ...

MySQL フラッシュリストとダーティページフラッシュメカニズム

1. レビューMySQL の起動後にバッファ プールが初期化されます。バッファ プールは N 個の空...

MySQL トリガーの定義と使用方法の簡単な例

この記事では、MySQL トリガーの定義と使用方法について説明します。ご参考までに、詳細は以下の通り...

アプレットにおけるwx.getUserProfileインターフェースの具体的な使用

最近、WeChatミニプログラムは、監査ミニプログラムのwx.loginおよびwx.getUserI...

MySQLデータベースインデックスの欠点と適切な使用

目次インデックスの適切な使用1. 通常のインデックスのデメリット2. 主キーインデックスの落とし穴3...

MySQL スロークエリログの設定と使用方法のチュートリアル

序文MySQL スロー クエリ ログは、日常業務でよく遭遇する機能です。MySQL スロー クエリ ...

Win10 DVWA のダウンロード、インストール、構成のグラフィック チュートリアルの詳細な説明 (初心者向け学習侵入)

コンピュータ システムが再インストールされ、侵入テスト学習環境 DVWA を再インストールする必要が...

Vue のループフォーム項目例の詳細な説明

場合によっては、ユーザーがボタンをクリックして同様のフォームを追加し、クリックごとに 1 回追加でき...

Vue3.0はドロップダウンメニューのカプセル化を実装します

Vue3.0 がリリースされてからしばらく経ちましたが、勉強を始める必要があります。まず、達成したい...

MySQLの半同期の詳細な説明

目次序文MySQL マスタースレーブレプリケーションMySQL でサポートされているレプリケーション...

フォームファイル選択ボックスのスタイルをカスタマイズする例

コードをコピーコードは次のとおりです。 <!DOCTYPE html> <html...