最近使用されていない (NRU) ページ置換アルゴリズム
オペレーティング システムは、メモリを制御するための基本的なページ置換戦術として、最近使用されていない (NRU) ページ置換アルゴリズムを使用します。その主な目的は、しばらくアクセスされていないページをメモリから見つけて削除することです。
この記事では、NRU ページ置換アルゴリズム、そのクラス、関連する手順、使用例、およびその利点について説明します。
NRU アルゴリズムのクラス
使用法または参照ビットに基づいて、ページはNRUアルゴリズムによって4つのクラスに分割されます-
クラス 0 - ページはメモリにロードされたため、参照 (アクセス) または変更 (書き込み) できません。
クラス 1 - メモリへのロード中に変更が加えられたものの、参照されていないページ。
クラス 2 - 参照として使用されているが変更されていないページ。
クラス 3 - 変更および引用されたページが該当します。
通常、各ページの参照ビットは、クロックまたはタイマー デバイスを使用する NRU 方式を使用して定期的にリセットされます。このメソッドは、各クロック ティックまたはタイマー割り込みで削除するページを選択する前にメモリ内のすべてのページを分析し、参照に基づいて各ページを分類し、ビットを変更します。
NRU では、選択手順には、最も小さい番号の空でないクラスを探し、そのクラスからページをランダムに排出することが含まれます。この方法では、最も小さい番号のクラスを選択することにより、最近使用されていないページの削除が優先され、重要度の低いサイトや使用頻度の低いサイトが削除される可能性が高まります。
最も最近使用されていない (LRU) などのより複雑なアルゴリズムが実装上の制限により現実的でない場合、特にリソースが限られているシステムでは、NRU は使用できる合理的に基本的で効果的なページ置換メカニズムです。 NRU ではページ参照が考慮されていないこと、およびそのランダムなエビクション ポリシーが常に最高のパフォーマンスを生み出すとは限らないことに留意することが重要です。
NRU アルゴリズムのステップ
次の手順は、NRU（最近使用されていない）ページ置換メカニズムがどのように機能するかの基礎を形成します-
メモリ内の各ページには、参照ビット (R) と変更ビット (M) が与えられます。通常、ページの各ページ テーブル エントリには次の部分が含まれます。
このアルゴリズムは、一定の間隔で、または指定されたイベント (クロック刻みやタイマー割り込みなど) に応答して、NRU 選択手順を開始します。
R ビットと M ビットに基づいて、アルゴリズムはメモリ内のすべてのページを次の 4 つのクラスのいずれかに分類します。
クラス 0 - ページの R 値と M 値は 0 です。
クラス 1 - ページには R=0 および M=1 が含まれます。
クラス 2 - R=1 および M=0 の年齢。
クラス 3 - R と M が両方とも 1 に等しいページ。
ページが分類された後、アルゴリズムによって削除対象のページが選択されます。まず、空ではない最小の番号を持つクラスを検索します。多数のクラスがある場合、アルゴリズムはページ数の少ないクラスを優先します。たとえば、クラス 0 とクラス 1 の両方にページがある場合は、クラス 0 が選択されます。
プログラムは、指定されたクラスから削除するページをランダムに選択します。これは、クラス内のすべてのページを反復処理した後にランダムにページを選択するか、乱数ジェネレーターを使用することによって実行できます。
選択したページがメモリから削除されたときに、必要に応じて置換ページをロードできます。関連するページ テーブル エントリに適切な変更が加えられます。
最後に、後続の選択サイクルの準備を整えるために、メモリの残りのすべてのページの参照ビット (R) がクリアされます (0 に設定されます)。
NRU は、まだ使用されていないページ (つまり、参照ビットが 0 であるページ) を定期的にスキャンして排除することにより、近い将来に必要になる可能性が低いページを削除しようとします。 NRU ではページ参照の頻度が考慮されないため、状況によっては理想的とは言えないパフォーマンスが発生する可能性があります。
これはNRUアルゴリズムのフローチャートです-
NRU ページ置換アルゴリズムの使用例
オペレーティング システムにおける不連続割り当ての使用例をいくつか見てみましょう。
可変サイズのプロセス - 不連続な割り当ては、さまざまなサイズのプロセスを扱う場合に特に便利です。これにより、メモリを複数の領域に分散できるため、利用可能なメモリを効率的に利用できるようになります。
動的メモリ管理 - 非連続割り当てにより動的メモリ管理が可能になり、アクティビティの開始または終了に応じてメモリの割り当てと割り当て解除が可能になります。この柔軟性は、プロセスのメモリ要件が変化する環境では不可欠です。
効果的なメモリ利用 - 非連続割り当てにより、プロセスの実際のニーズに応じてメモリ ブロックを割り当てることで、効率的なメモリ利用が保証されます。各プロセスに必要な量のメモリのみを割り当てることで、メモリの無駄を防ぎます。
断片化管理 - 不連続な割り当てにより外部の断片化が増加する可能性がありますが、内部の断片化を軽減するのに役立ちます。内部フラグメンテーションは、割り当てられたメモリ ブロックに空のスペースがあるか、部分的に使用されているスペースがある場合に発生します。プロセスの特定のニーズに基づいてメモリ ブロックを割り当てることにより、内部の断片化が最小限に抑えられます。
大規模なデータセットの処理 - 単一の連続したメモリ ブロックに収まらない大規模なデータセットを扱う場合、非連続割り当ては有益です。複数の非連続ブロックにメモリを割り当てる機能により、プロセスは利用可能なメモリ リソースを使い果たすことなく、大量のデータを処理できます。
仮想メモリ システム - 不連続な割り当ては、仮想メモリ システムで使用される基本的な技術です。これにより、オペレーティング システムが柔軟な方法で論理アドレスを物理アドレスにマップできるようになり、プロセスが不連続な方法でメモリにアクセスできるようになります。
マルチプログラミング環境 - 複数のプロセスが同時に実行されているマルチプログラミング環境では、不連続な割り当てにより、メモリ ブロックを異なるプロセスに効率的に割り当てることができます。各プロセスには、その特定の要件に基づいてメモリを割り当てることができるため、最適なメモリ使用が可能になります。
リアルタイム システム - プロセスに厳しいタイミング要件があるリアルタイム システムでは、不連続な割り当てが役立ちます。これにより、メモリの動的割り当てと割り当て解除が可能になり、プロセスが厳しいタイミング制約を満たしながらメモリ リソースを効率的に管理できるようになります。
不連続な割り当てを採用することにより、オペレーティング システムはプロセスの多様なメモリ ニーズに対応し、効率的なメモリ利用を促進し、さまざまなワークロードとデータ サイズを処理するために必要な柔軟性を提供できます。
NRU ページ置換アルゴリズムの利点
状況によっては、NRU (最近使用されていない) ページ置換メカニズムには多くの利点があります。 NRU アルゴリズムの利点をいくつか示します-
シンプルさ - NRU は、比較的簡単に実装できるページ置換方法です。たとえば、NRU のシンプルさは、メモリ制限のある組み込みシステムや古いハードウェアを支援する可能性があります。
めったにアクセスされないページを優先する - NRU は、めったにアクセスされないページを優先的に削除します。 NRU を使用すると、特定のアプリケーションまたはデータ セットの使用頻度は低いものの、大量のメモリを必要とするシステム上で、使用頻度の低いページが最初に削除され、より頻繁に使用されるページのためのスペースが確保されます。
アクセス パターンの変化に対する迅速な適応性 - アクセス パターンの変化に対する迅速な適応性は、そのための簡単な技術を提供する NRU によって可能になります。これにより、アルゴリズムは、最新のアクセス パターンに応じて、大まかではありますが、エビクションの決定を変更できます。
ランダムな削除 - 各クラスからどのページを削除するかを選択するために、NRU はランダム選択手法を使用します。さらに、エビクションの予測が難しくなり、悪意のあるソフトウェアが特定のエビクション パターンを利用することがより困難になる可能性があります。
結論
NRU (最近使用されていない) ページ置換手法は簡単で、オーバーヘッドがほとんどなく、めったに使用されないページを優先的に削除することができます。これは構築するのが簡単なアルゴリズムなので、リソースが最小限のシステムや、より複雑なアルゴリズムが現実的ではない環境に適しています。参照ビットを定期的にリセットすることで、NRU は変化するアクセス パターンに適応できます。ランダム化は、ページの削除でも使用され、削除の負荷を分散し、予測可能性を回避します。