I. ベスト・リプレイスメントOPT
アイデア
ページが削除のために選択されるたびに、そのページは二度と使用されないか、最長期間アクセスされないページとなります。
システムがプロセスに3つのメモリー・ブロックを割り当てたと仮定すると、実行は次のページに順番にアクセスします：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, そしてそのプロセスは次のようになります：
| ページ番号 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
| ページ番号 | T | T | T | T | F | T | ||||||||||||||
| メモリーブロック1 | 7 | 7 | 2 | |||||||||||||||||
| メモリーブロック2 | 0 | 0 | 0 | |||||||||||||||||
| メモリーブロック3 | 1 |
最初のアクセスは、すべての3つのメモリブロックが占有されていないので、最初に、アクセスされるページの順序に従って、7、0、1が順番にメモリブロック1、2、3に入れられ、ページ2への4回目のアクセスに、アルゴリズムの考え方によると：最長の時間でアクセスされているページの優先順位の排除は再びアクセスされることはありません、それは7、0、1にアクセスされているページで、0ページ目が再び5回目にアクセスされることを知っていることができます。5回目に再びアクセスされるように、ページ1は、第thの時間に再びアクセスされ、ページ7は、第I回に再びアクセスされますので、ここで優先順位はページ7を排除することである、つまり、ページ7は、メモリからスワップアウトし、次のページに置くことができます - 2。
その後、5回目のアクセスが行われ、ページ番号が0になったとき、ページ0はすでにメモリ上にあることがわかり、ページの欠落は発生しないので、ページの状況は変わりません。
そして、その後、6回目のアクセスが行われ、ページ番号が3になると、3がメモリ上にないことが判明し、欠落ページが発生し、スケジューリング-前のアクセスでは、2、0、1がページ内にあり、以降のアクセス順では、2、0ページが1ページに先行することが判明したため、1ページがはずれ、3ページがメモリに入ります。上の表の6列目のように
というような順番で、あとは全部：
プロセス全体を通して、ページ欠落割り込みは 9 回発生し、ページ置換は 6 回発生します。したがって、ページ欠落時にページ置換が発生しない可能性があります。
欠落ページ＝欠落ページ数／訪問ページ総数＝9/20＝45パーセント
Tip
SO、OPT置換アルゴリズムは、ページ番号とページ・アクセスの順序がわかっていなければならないことを前提としていますが、実際には、次にどのページにアクセスするかを知る唯一の方法はプロセスの実行中です。オペレーティング・システムはページ・アクセスの順序を事前に予測できないため、++最適置換アルゴリズムは達成できません++。
II. 先入れ先出し交換式FIFO
アイデア
各選択で消去されるページは、メモリに入る最も古いページです。
実現
メモリに転送されたページは、転送された順番に従ってキューに並べられ、++ページをスワップアウトする必要があるときは、キューの先頭ページ++を選択するだけです。キューの最大長は、プロセスに割り当てられているメモリブロックの数に依存します。
システムが1つのプロセスに3つのメモリ・ブロックを割り当て、次のページ番号参照文字列を考え るとします。
FIFOの考え方に従えば、アクセス順序は次のようになります：
| ページ番号 | 3 | 2 | 1 | 0 | 3 | 2 | 4 | 3 | 2 | 1 | 0 | 4 |
| ページ番号 | T | T | T | T | T | T | T | F | F | T | T | F |
| メモリーブロック1 | ++3++ | 3 | 3 | 0 | 0 | 4 | 4 | |||||
| メモリーブロック2 | ++2++ | 2 | 2 | 3 | 3 | 1 | ||||||
| メモリーブロック3 | ++1++ | 1 | 1 | 2 | 2 |
Belady Exception: プロセスに割り当てられる物理ブロックの数が増えると、見つからないページの数は減るどころか増えます。
Tip
FIFOアルゴリズムだけがI. ベスト・リプレイスメントOPT生成します。加えて、FIFOアルゴリズムは実装が簡単ですが、最初にアクセスされるページが最も頻繁にアクセスされる可能性も高いため、実際にプロセスが実行されている時の法則には合いません。そのため、FIFOアルゴリズムの性能は劣ります。
III.最近使用されていない交換用LRUのうち最も長いもの
アイデア
毎回削除されるページは、最近使用された最も古いページです。 最近使われたページ
実現
ページがアクセスされてから経過した時間 ++t++ は、各ページに対応するページテーブルエントリのアクセスフィールドで記録されます。ページを削除する必要がある場合、++t++の値が最も大きい既存のページ、つまり、最近未使用のページが選択されます。
4メモリブロック、ページ参照順：1、8、1、7、8、2、7、2、1、8、3、8、2、1、3、1、7、1、3、7
B列から遡ると、A回目、9回目、8回目、7回目にアクセスされたページは、8、1、2、7です。 つまり、最近最も長く使われていないページは7なので、7番をメモリから取り出して、3番をメモリに転送します。
Tip
ニアレストとは：最後に欠落していないページの状態に最も近いという意味です。
個人的な感想
それはFIFOに非常に似ていると感じています。しかし、違いがあります - FIFO処理は、メモリがいっぱいである限り、単純にFIFOであり、ページの不足は、キューページの先頭から排除され、その場合、限り、それが最初にあるように、最も頻繁に使用されるページが頻繁にメモリから/に転送されるにつながる可能性があります - 、FIFOFIFOは常にこれらのページとの追跡関係を維持する必要はありませんが、LRUは常にこれらのページを追跡する必要があります。LRUの考え方によれば、誰がLeast Recently Usedページであるかを決定するためには、これらのページのLast Visit Timeを保存する必要があるからです。なぜなら、LRUは最近使われたページをメモリに保持するからです。
1.1比較例です。
クロック交換 CLOCK
アイデア
NRU（Not Recently Used）とも呼ばれます。
実現
各ページにアクセスビットRを設定し、リンクポインタを介してメモリ上のすべてのページを循環キューにリンクします。ページがアクセスされると、そのページのRビットは1にセットされます。もしそれが0なら、そのページはスワップアウトのために選択され、もしそれが1なら、それは0にセットされ、当分の間スワップアウトされず、次のページのためにチェックが続けられます。
第1スキャンの全ページのRビットが1の場合、第2スキャンに進む前に、これらのページのRビットを順番に0に設定します。
2回目のスキャンにはRビット0のページが必ず含まれるため、単純なCLOCKアルゴリズムで排除されたページを選択する場合、最大でも2回のスキャンを経ることになります。
システムがプロセスに対して5つのメモリブロックを割り当て、次のページ番号参照文字列を考えたとします：
1, 3, 4, 2, 5, 6, 3, 4, 7
通常のアクセスを開始すると、最初の5ページがRビットが1のメモリブロックに順次ロードされ、サーキュラーキューは++1(R=1) → 3(R=1) → 4(R=1) → 2(R=1) → 5(R=1) → 1++を読み込みます。次に、リンクポインタが現在指しているサーキュラーキューの位置からスキャンを開始し、Rビットが0のページを見つけ、それが1であれば0に変更しようとします。
つまり、最初のスキャンが完了した後のループ・キューは、++1(R=0) → 3(R=0) → 4(R=0) → 2(R=0) → 5(R=0) → 1++となり、リンク・ポインタは現在Rの位置1、R=0を指しています。キューは、++6(R=1) → 3(R=1) → 4(R=1) → 2(R=1) → 5(R=1) → 6++。
次にページ3にアクセスする場合、3はメモリ内にあるので、ページ3のRの位置を1にセットするだけです。
Tip
++ポインタの移動は置換が発生したときだけなので、この時点でのポインタはまだ3ページを指しており、キューの先頭は3があるノードです。
だから7にアクセスし、このように不足しているページの発生は、順番にスキャン3の先頭からポインタ4、Rの4≠0、Rの4を修正= 0; 2にスキャンし、Rの2 = 0、2からの置換、7に調整、Rの7を修正= 1; + + +ポインタ5の次のページには、Rの5を修正= 0 + + +;この時点でキューは次のとおりです。 + + 6（R = 1）→ 3（R = 1）→ 4（R = 1）→ 7（R = 1）→ 5(R=0) → 6++.
V. 時計交換の改善
単純なクロック置換アルゴリズムでは、ページが最近アクセスされたかどうかだけを考慮します。実際、消去されたページが変更されていなければ、外部メモリに書き戻すためにI/0操作を実行する必要はありません。++消去されたページが変更された場合のみ、外部メモリに書き戻す必要があります。
アイデア
ページが最近アクセスされたかどうかを考慮することに加えて、オペレーティング・システムはページが変更されたかどうかも考慮する必要があります。他のすべての条件が同じであれば、I/O操作を避けるために、変更されていないページを排除することが優先されるべきです。
説明：NRUは、RビットとMビット++を元に、ページの入れ替えを近似的に行います。 プロセスの起動時には、OSによって全ページのページビットが0++にセットされます。 プロセスが起動されると、オペレーティング・システムによってすべてのページのページ・ビットが0++に設定されます。 定期的に++、Rビットがクリアされ、最近参照されなかったページと最近参照されたページを区別します。ページ・フォールトが発生すると、オペレーティング・システムはすべてのページを検査し、4つに分割します。ページ・フォールトが発生すると、オペレーティング・システムはすべてのページを検査し、RビットとMビットの現在の値に基づいて4つのカテゴリーに分けます。
Case 0 : not referenced, not modified ++ = ++
Case 1 : not referenced, modified ++ = ++
Case 2 : referenced, not modified ++ = ++
Case 3 : referenced, modified ++ = ++
実現
新しい変更ビットMが追加され、M=1はそのページが最近変更されたことを意味し、0は変更されていないことを意味します。各ページの状態を示すために使用される形式。
置き換え可能なすべてのページの循環キューを形成します。
ラウンド1：現在の位置から最初のフレームまでをスキャンして入れ替えます。このラウンドのスキャンでは、フラグビットは変更されません。
ラウンド 2: 最初のスキャンが失敗した場合、再スキャンして置き換えに使用する最初のフレームを見つけます。このラウンドでは、スキャンされたすべてのフレームのRビットを0にします。
第 3 ラウンド：第 2 ラウンドのスキャンが失敗した場合、置換に使用する最初のフレームを見つけるためにスキャンが再開されます。このラウンドのスキャンでは、フラグビットは変更されません。
ラウンド4：3ラウンド目のスキャンが失敗した場合、スキャンが再開され、最初のフレームが置換のために検出されます。
すべてのフレームのアクセス・ビットは2ラウンド目で0に設定されているため、3ラウンド目と4ラウンド目のスキャンの後にフレームを選択する必要があります。
NRUアルゴリズムは、最も低い番号の空でないクラスからランダムにページを削除します：
Page-0 is of class-2 ++ = ++
Page-1 is of class-1 ++ = ++
Page-2 is of class-0 ++ = ++
Page-3 is of class-3 ++ = ++
So ++lowest class++ Page-2 need to be replaced by NRUそしてクラスPage-1 pages and so on.
Tip
RM、00、01、10、11。
未定。
まとめ
| 0 | 長期間訪問されないページの削除を優先します。 | ページ欠損率が小さい、最高のパフォーマンス、達成不可能 |
| 先入れ先出し | メモリに最初に入るページの排除を優先 | シンプルな実装、低いパフォーマンス、ベラディ例外 |
| LRU | 最近長い間訪問されていないページを優先的に削除します。 | 素晴らしいパフォーマンス、素晴らしいオーバーヘッド |
| クロック | サイクリックスキャンニング、最初の消去ラウンドR=0、Rを1に変更； | ページが変更されたかどうかに関係なく、実装が簡単でオーバーヘッドが少ない |
| エヌアールユー | 第1次予選 第2次予選、Rを0に修正 第3ラウンド 第4ラウンド |
低いオーバーヘッドと優れたパフォーマンス |
NRUラウンドでどちらが先に敗退するかについては、同じバージョンはまだ見つかっていません
