少しでも分かりやすく伝えたいページ置換アルゴリズム

少しでも分かりやすく伝えたいページ置換アルゴリズム

こんにちは、しゃねろんです。
今回はページ置換アルゴリズムについて説明していきたいと思います!

ページ置換アルゴリズムとは

容量が満タンになってしまった時に、新しくデータを入れなくてはならなくなった場合にどこのデータと置き換えるかを示した方法です。
今回はページ置換アルゴリズムの中でも「FIFO」「LIFO」「LFU」「LRU」について説明していきたいと思います!

・FIFOとは

「First In First Out」の略称で、日本語で言う「先入れ先出し法」のことです。「キュー」とも仕組みは同じです。
今言った言葉のどれかを知っていれば、ぶっちゃけると説明はいりません。飛ばしてもらっても構いません。

・聞いた事の無い方向けに詳しく説明していきます。
「First In First Out」を日本語に訳すと(直訳)先に入ったものが先に出ていくという意味になります。

FIFO参考例

例えば、容量の上限が「3」のメモリがあったとして容量が「1」あるデータ「A」「B」「C」「D」があったとします。
「A」→「B」→「C」の順番に入れていったときに「D」は入りませんよね。そんな時FIFOだと最初に入った「A」が「D」に置き換わります。

FIFO置換後

「A」が「D」に置き換わるので上の画像のようになります。

・LIFOとは

「Last In First Out」の略称で、日本語で言う「後入れ先出し法」のことです。「スタック」とも仕組みは同じです。
今言った言葉のどれかを知っていれば、ぶっちゃけると説明はいりません。飛ばしてもらっても構いません。

・聞いた事の無い方向けに詳しく説明していきます。
「Last In First Out」を日本語に訳すと(直訳)後に入ったものが先に出ていくという意味になります。
先ほどと同じように、容量の上限が「3」のメモリがあったとして容量が「1」あるデータ「A」「B」「C」「D」があったとします。

LIFO参考例

「A」~「C」までは先ほどと同様すんなり入りますが、「D」を入れるとなったときに今度は最後に入ったものが先に出ていくので今回の場合だと「C」が「D」に置き換わります。

LIFO変更後

「A」が「D」に置き換わるので上の画像のようになります。

・LFUとは

「Least Frequently Used」の略称で、使用頻度が最も少ないものを置き換える方法です。
今回は、
「A」→「B」→「C」→「B」→「C」→「C」→「B」→「A」のようにデータ参照された後に「D」が入るような例とします。
使用頻度が最も低いものが置き換わるので、「A」「B」「C」のそれぞれ参照された回数をカウントしていきます。

「A」:2回
「B」:3回
「C」:3回

LFU変更後

今回だと、「A」が最も使用頻度が少ないので、「A」が「D」に置き換わります。

・LRUとは

「Least Recently Used」の略称で、最後に使われてから最も参照されていなものを置き換える方法です。
今回は、
「A」→「B」→「C」→「B」→「A」のようにデータ参照された後に「D」が入るような例とします。

LRU変更1

まず、最初の3つである「A」→「B」→「C」までは問題なく入りますね。

LRU変更2

次に「B」が参照されます。「B」が参照されたので、順番としては最も新しくなります。

LRU変更3

次に「A」が参照されます。「A」が参照されたので、順番としては最も新しくなります。

LRU変更後

この時、最後に使われてから最も参照されていない「C」が「D」に置き換わります。

まとめ

・FIFO:先に入ったものが先に置き換えられる
・LIFO:後に入ったものが先に置き換えられる
・LFU:使用頻度が最も少ないものが置き換えられる
・LRU:最後に使われてから最も参照されていないものが置き換えられる

基本情報技術者試験やITパスポートにも今回説明したような問題が出てくるのでぜひ覚えてください!

テーマ

現在使用中テーマは最新版

v.1.0v.2.0v.3.0v.3.1v.3.2v.3.3v.3.4v.3.5v.3.6v.3.7v.3.8v.shaneron選択しない(安定版)