Operating-system-os-memory-allocation-qa3
提供：Dev Guides
OSメモリ割り当てQ＆A＃3
- 質問：*ページ違反はいつ発生しますか？ さまざまなページ置換戦略/アルゴリズムを説明します。
- 回答：*デマンドページングメモリ管理手法では、実行に必要なページがメインメモリに存在しない場合、ページフォールトが発生します。 オンデマンドでページをメインメモリにロードするには、空きページフレームがメインメモリで検索され、割り当てられます。 空きページフレームがない場合、メモリマネージャはそのコンテンツをセカンダリストレージにスワップしてフレームを解放する必要があるため、必要なページのためのスペースを空けます。 ページを交換するには、多くのスキームまたは戦略が使用されます。
さまざまなページ置換戦略/アルゴリズム
- 最適なページ置換アルゴリズム-このアルゴリズムは、最も長期間使用されないページを置換します。 ページフォールトが発生すると、ページの一部のセットがメモリ内にあります。 これらのページの1つは、次の指示で参照されます。 他のページは、10,100またはおそらく1000の命令まで参照されない場合があります。 この情報は、PMT（Page Map Table）の各ページに保存できます。 + P#
- * NRU（Not Recent Used）ページ置換アルゴリズム*-このアルゴリズムでは、各ページにそれぞれ参照ビットおよび変更ビットと呼ばれる2つの追加のステータスビット 'R’および 'M’が必要です。 参照ビット（R）は、ページが参照されるたびに自動的に1に設定されます。 変更ビット（M）は、ページが変更されるたびに1に設定されます。 これらのビットはPMTに保存され、メモリ参照ごとに更新されます。 ページフォールトが発生すると、メモリマネージャーはすべてのページを検査し、RビットとMビットに基づいて4つのクラスに分割します。
- クラス1：（0,0）-最近使用も変更もされていない-置き換えるのに最適なページ。
- クラス2：（0,1）-最近は使用されていないが変更されている-置換前にページを書き出す必要があります。
- クラス3：（1,0）-最近使用されたがクリーン-おそらくすぐに再び使用されるでしょう。
- クラス4：（1,1）-最近使用および変更された-おそらく再び使用され、それを置き換える前に書き込みが必要になります。 +このアルゴリズムは、番号が最も小さい空でないクラスからページをランダムに削除します。
==== 利点：
- わかりやすいです。 実装するのが効率的です。 . FIFO（先入れ先出し）ページ置換アルゴリズム*-これは最も単純なページ置換アルゴリズムの1つです。 メモリ内で最も長い時間を費やした最も古いページが選択され、置き換えられます。 このアルゴリズムは、メモリ内のページを保持するFIFOキューを使用して実装されます。 ページはキューの後端に挿入され、キューの前で置き換えられます。 + FIFO +図では、参照文字列は5、4、3、2、5、4、6、5、4、3、2、6であり、空の3フレーム。 最初の3つの参照（5、4、3）はページ違反を引き起こし、空のフレームに入れられます。 ページ5が最初にロードされたため、次の参照（2）はページ5を置き換えます。 7ページのフォールトの後、次の参照は5であり、5はすでにメモリ内にあるため、この参照のページフォールトはありません。 同様に、次の参考文献4。 +マークはページの着信を示し、円は削除のために選択されたページを示します。
- わかりやすいです。 実装するのが効率的です。 . FIFO（先入れ先出し）ページ置換アルゴリズム*-これは最も単純なページ置換アルゴリズムの1つです。 メモリ内で最も長い時間を費やした最も古いページが選択され、置き換えられます。 このアルゴリズムは、メモリ内のページを保持するFIFOキューを使用して実装されます。 ページはキューの後端に挿入され、キューの前で置き換えられます。 + FIFO +図では、参照文字列は5、4、3、2、5、4、6、5、4、3、2、6であり、空の3フレーム。 最初の3つの参照（5、4、3）はページ違反を引き起こし、空のフレームに入れられます。 ページ5が最初にロードされたため、次の参照（2）はページ5を置き換えます。 7ページのフォールトの後、次の参照は5であり、5はすでにメモリ内にあるため、この参照のページフォールトはありません。 同様に、次の参考文献4。 +マークはページの着信を示し、円は削除のために選択されたページを示します。
==== 利点
- FIFOは簡単に理解できます。
- 実装は非常に簡単です。
不利益
- パフォーマンスが必ずしも良いとは限りません。 アクティブなページを置き換えて新しいページを作成し、そのページのページフォールトをすぐに引き起こす可能性があります。 別の予期しない副作用は、FIFOの異常またはBeladyの異常です。 この異常は、割り当てられたページフレームの数が増えるとページフォールト率が増加する可能性があることを示しています。 + e.g. 次の図は、同じページトレースを示していますが、メモリが大きくなっています。 ここで、ページフレームの数は4です。 + FIFO Anamoly +ここでのページフォルトは9ではなく10です。 . LRU（最長時間未使用）アルゴリズム*-最長時間使用されていないページは、最長時間未使用（LRU）アルゴリズムに置き換えられます。 これは、長期間使用されていないページがおそらく最も長い時間使用されずに置き換えられるという観察に基づいています。 + LRU +最初は、3ページのフレームは空です。 最初の3つの参照（7、0、1）はページフォールトを引き起こし、これらの空のフレームに取り込まれます。 次の参照（2）は7ページを置き換えます。 次のページ参照（0）は既にメモリにあるため、ページフォールトはありません。 さて、次の参考文献（3）では、メモリ内の3つのフレームのうち、ページ1が最も最近使用されており、したがって置き換えられていることをLRU交換で確認します。 したがって、プロセスは継続します。
==== 利点
- LRUページ置換アルゴリズムは静かで効率的です。
- Belady’s Anomalyの影響を受けません。
デメリット
- その実装は非常に簡単ではありません。
- その実装には、実質的なハードウェア支援が必要になる場合があります。
