少しでも分かりやすく伝えたいページ置換アルゴリズム
皆さんこんにちは！！
今回はページ置換アルゴリズムについて説明していきたいと思います！
ページ置換アルゴリズムとは
容量が満タンになってしまった時に、新しくデータを入れなくてはならなくなった場合にどこのデータと置き換えるかを示した方法です。
今回はページ置換アルゴリズムの中でも「FIFO」「LIFO」「LFU」「LRU」について説明していきたいと思います！
FIFOとは
「First In First Out」の略称で、日本語で言う「先入れ先出し法」のことです。「キュー」とも仕組みは同じです。
今言った言葉のどれかを知っていれば、ぶっちゃけると説明はいりません。飛ばしてもらっても構いません。
・聞いた事の無い方向けに詳しく説明していきます。
「First In First Out」を日本語に訳すと(直訳)先に入ったものが先に出ていくという意味になります。
例えば、容量の上限が「3」のメモリがあったとして容量が「1」あるデータ「A」「B」「C」「D」があったとします。
「A」→「B」→「C」の順番に入れていったときに「D」は入りませんよね。そんな時FIFOだと最初に入った「A」が「D」に置き換わります。
「A」が「D」に置き換わるので上の画像のようになります。
LIFOとは
「Last In First Out」の略称で、日本語で言う「後入れ先出し法」のことです。「スタック」とも仕組みは同じです。
今言った言葉のどれかを知っていれば、ぶっちゃけると説明はいりません。飛ばしてもらっても構いません。
・聞いた事の無い方向けに詳しく説明していきます。
「Last In First Out」を日本語に訳すと(直訳)後に入ったものが先に出ていくという意味になります。
先ほどと同じように、容量の上限が「3」のメモリがあったとして容量が「1」あるデータ「A」「B」「C」「D」があったとします。
「A」～「C」までは先ほどと同様すんなり入りますが、「D」を入れるとなったときに今度は最後に入ったものが先に出ていくので今回の場合だと「C」が「D」に置き換わります。
「A」が「D」に置き換わるので上の画像のようになります。
LFUとは
「Least Frequently Used」の略称で、使用頻度が最も少ないものを置き換える方法です。
今回は、
「A」→「B」→「C」→「B」→「C」→「C」→「B」→「A」のようにデータ参照された後に「D」が入るような例とします。
使用頻度が最も低いものが置き換わるので、「A」「B」「C」のそれぞれ参照された回数をカウントしていきます。
「A」：2回
「B」：3回
「C」：3回
今回だと、「A」が最も使用頻度が少ないので、「A」が「D」に置き換わります。
LRUとは
「Least Recently Used」の略称で、最後に使われてから最も参照されていなものを置き換える方法です。
今回は、
「A」→「B」→「C」→「B」→「A」のようにデータ参照された後に「D」が入るような例とします。
まず、最初の3つである「A」→「B」→「C」までは問題なく入りますね。
次に「B」が参照されます。「B」が参照されたので、順番としては最も新しくなります。
次に「A」が参照されます。「A」が参照されたので、順番としては最も新しくなります。
この時、最後に使われてから最も参照されていない「C」が「D」に置き換わります。
まとめ
- FIFO:先に入ったものが先に置き換えられる
- LIFO:後に入ったものが先に置き換えられる
- LFU:使用頻度が最も少ないものが先に置き換えられる
- LRU:最後に使われてから最も参照されていないものが先に置き換えられる
基本情報技術者試験やITパスポートにも今回説明したような問題が出てくるのでぜひ覚えてください！