FIFOページ置き換えがやり方がわからない

質問

FIFOページ置き換えが色々見てもやり方がわかりません
わかりやすい説明をお願いします。

こんな質問ですみません。

回答No.1

seastar3 · ベストアンサー

キャッシュメモリのFIFOのことでしょうね。先入れ先出し法もしくは行列待ちのやり方でデータのブロックを取り出しやすいメモリに待機させます。取り出しやすいメモリも無駄なほどは広くないので、あるルールでデータのブロックを明け渡すのです。
この工夫には、ＦＩＦＯ方式やＬＲＵ方式などがあります。

まずＦＩＦＯ方式をくだけた例で言うと、２種類の調味料しかのせられない調味料棚がレンジのそばにあるとします。２種類以外の調味料はちょっと離れた冷蔵庫に入れていて、調味料棚にない調味料を使ったときには先にのせた調味料を冷蔵庫にしまいます。調味料棚にあるものは使ったらそのまま棚に戻します。これがＦＩＦＯ方式です。そうやってできるだけ冷蔵庫まで歩かなくていいように工夫するのです。
ＬＲＵ方式は、先に出したものをしまうのではなくて、一番長い間使っていない方をしまうルールです。

次にハードウェアとして説明します。前提として、２区画のキャッシュメモリがあり、そこにデータＥとデータＣが入っているとします。そして右側が古い区画です。

図１　　　　［Ｃ］［Ｅ］

これでＥかＣかのデータをＣＰＵが取りに来たら、明け渡しなしでキャッシュメモリから提供します。
また、データＡが必要になったらキャッシュメモリにはないので、メインメモリから取り出されます。そして、この２区画のキャッシュメモリの右側にあふれる形で、図２のようにデータＥがキャッシュメモリからなくなります。

図２　　　　［Ａ］［Ｃ］ --> データＥはこぼれる。

これでＣかＡかのデータをＣＰＵが取りに来たら、明け渡しなしでキャッシュメモリから提供します。
また、データＢが必要になったらキャッシュメモリにはないので、メインメモリから取り出されます。そして、この２区画のキャッシュメモリの右側にあふれる形で、図３のようにデータＣがキャッシュメモリからなくなります。

図３　　　　［Ｂ］［Ａ］ --> データＣはこぼれる。

このようにキャッシュメモリという踊り場をもうけて、使いそうなデータをわざわざメインメモリやハードディスクまで取りに行かなくても早く処理できる工夫をしています。