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

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

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

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

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

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

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でルートアカウントを有効にする方法

推薦する

フロントエンド制作に関する簡単な議論: 互換性のために IE6 はまだ必要ですか?

国内市場ではIE6~7のサポートに対する一定の需要がまだありますが、フロントエンド開発者として、私た...

Linux で ss コマンドと zabbix を組み合わせてソケットを監視する方法の詳細な説明

目次序文1. ssコマンド2. Zabbix監視マシンの全体的なソケットステータス2.1. スクリプ...

JS は VUE コンポーネントに基づいて都市リスト効果を実装します

この記事の例では、VUEコンポーネントに基づいて都市リストエフェクトを実装するための具体的なコードを...

MySQL InnoDB MRR 最適化ガイド

序文MRR は Multi-Range Read の略で、ランダム ディスク アクセスを削減し、ラン...

Nginx の場所と proxy_pass パスの設定の問題の概要

目次1. Nginxロケーションの基本設定1.1 Nginx 設定ファイル1.2 Pythonスクリ...

HTML サブタグと sup タグ

今日はあまり使わないHTMLタグ「subタグ」と「supタグ」を紹介します。定義と使用法: <...

MySQL スロークエリを通じて MySQL のパフォーマンスを最適化する方法

アクセス数が増えると、MySQL データベースへの負荷が増大します。MySQL アーキテクチャを使用...

CSS の新機能には、コントロールページの再描画と再配置の問題が含まれています

新しい CSS プロパティ contain を紹介する前に、読者はページの再描画と再配置が何であるか...

Linuxで中断されたシステムを呼び出す方法

序文低速システム コールとは、決して戻らない可能性があり、プロセスを永久にブロックするシステム コー...

MySQL ストアド プロシージャの使用例の分析

この記事では、MySQL ストアド プロシージャの使用方法について説明します。ご参考までに、詳細は以...

reduxの動作原理と使い方の説明

目次1. redux とは何ですか? 2. 還元の原則3. redux の使い方は? (1)redu...

JavaScript 初心者のための二分探索木アルゴリズムのチュートリアル

目次バイナリ検索木 (BST) とは何ですか?バイナリツリーの基本的な走査(インオーダー、ポストオー...

CSS のインライン スタイルに変換するソリューション (css-inline)

シーンについて話すメールを送信サードパーティのウェブサイトにHTMLを埋め込む他の編集者の記事をコピ...

MySQLの行数カウントに関する簡単な説明

各テーブルの行数をカウントするために使用される MySQL count() 関数は、誰もがよく知って...

MySQLの数値型自動増分における落とし穴

テーブル構造を設計する場合、数値型は最も一般的な型の 1 つですが、数値型をうまく使用するのは想像す...