fifo は、先入れ先出しのページ置換アルゴリズムを指します。置換ごとに最初にメモリに転送されるページは、メモリ内での待ち時間が最も長いページです。利点: 実装が比較的簡単で、ハードウェアのサポートを必要としないため、システムのコストを増加させる必要がありません。
このチュートリアルの動作環境: Windows 10 システム、Dell G3 コンピューター。
fifo (先入れ先出しページ置換アルゴリズム)
基本的な考え方: メモリ内で最も古いページ、つまりメモリ内に最も長く存在したページです。
このアルゴリズムの実装は簡単で、メモリに転送されたページを順序に従ってキューにリンクし、常に最も古いページを指すようにポインタを設定するだけです。ただし、一部のページはプロセス中に頻繁にアクセスされるため、このアルゴリズムはプロセスの実際の実行ルールには適していません。
実装プロセス:
システムが 3 つの物理ブロックを 1 つのプロセスに割り当てると仮定し、次のページ番号参照文字列を考慮します: 7、0、1、2、 0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1。ページの置換には FIFO アルゴリズムが使用されており、プロセスがページ 2 にアクセスすると、最も早くメモリに入ったページ 7 がスワップアウトされます。次に、ページ 3 がアクセスされると、最初にメモリに入ったページ 2、0、1 がスワップアウトされます。以下の図からわかるように、FIFO アルゴリズムを使用すると 12 ページの置換が実行されます。
ページにアクセス | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
物理ブロック 1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 |
0 |
0 | 7 |
7 | 7 | ||||||
0 |
0 | 0 |
3 |
3 | 3 | 2 | 2 | 2 | ##1 | 11 | 00 | 物理ブロック 3 | ||||||||
1 |
1 |
0 |
0 | 0 | 3 | 3 |
2 |
##2 |
2 | 1欠落ページなし | √ | |||||||||
√ | √ | √ | √ | √√ | √ | √ | √ | √ √ | √
√ |
短所: FIFO アルゴリズムにより、割り当てられる物理ブロックの数も増加します。以下の図に示すように、ページ フォールトの数が減少するどころか増加する現象は、1969 年に Belady によって発見されたため、Belady アノマリーと呼ばれています。 Belady の異常が発生する可能性があるのは FIFO アルゴリズムのみですが、LRU および OPT アルゴリズムでは Belady の異常が発生することはありません。 | 関連知識の詳細については、 |
以上がfifo とはどのようなページ置換アルゴリズムですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。