fifo とはどのようなページ置換アルゴリズムですか?-よくある問題-php.cn

fifo とはどのようなページ置換アルゴリズムですか?

青灯夜游

リリース： 2023-01-13 00:37:55

オリジナル

9025 人が閲覧しました

fifo は、先入れ先出しのページ置換アルゴリズムを指します。置換ごとに最初にメモリに転送されるページは、メモリ内での待ち時間が最も長いページです。利点: 実装が比較的簡単で、ハードウェアのサポートを必要としないため、システムのコストを増加させる必要がありません。

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 ページの置換が実行されます。

#224440物理ブロック 2100物理ブロック 3##113 1欠落ページなし√√√√√√√√√√ 短所: FIFO アルゴリズムにより、割り当てられる物理ブロックの数も増加します。以下の図に示すように、ページフォールトの数が減少するどころか増加する現象は、1969 年に Belady によって発見されたため、Belady アノマリーと呼ばれています。 Belady の異常が発生する可能性があるのは FIFO アルゴリズムのみですが、LRU および OPT アルゴリズムでは Belady の異常が発生することはありません。関連知識の詳細については、FAQ 列をご覧ください。