[基本情報技術者試験]イメージで覚える！FIFO,LIFO,LRU,LFUとは

FIFO,LIFO,LRU,LFU

FIFO

FIFOは、First In First Out　の略で、文字通り最初に入ったものから最初に追い出すという方式です。

図で見てみましょう！

こんな感じで、クローゼットに入ってきた順が最も古いものから追い出されていくのがFIFOです。

イメージは簡単ですよね。

しかし、１つだけ躓きやすい問題があります。

１問、いやらしい問題を見てみましょう。

この「使用する」が入ってくると、一気に紛らわしくなります。

おそらく、使ったってことは一番新しくなるのかな…と混乱するのだと思います。

でも安心してください！

FIFOでは、最後にいつ使おうと、何回使おうと、

とにかく入った日が古い順に追い出されていくのです。

つまりここでは、赤い服を何回使っても、購入した日が一番古い、赤い服から追い出されるのです。

LIFO

LIFOは、Last In First Out の略で、最後に入ったものから最初に追い出すというものです。

こんな感じで、クローゼットに入ってきた順が新しいものから追い出されていきます。

LRU

LRUは、Least Recently Usedの略で、最後に使われたのが最も古い順に追い出す方式です。

この「使う」ですが、使用するときだけでなく、入ってきたときもカウントします。

LRUは、使った順に順番が決定する方式です。

したがって、使ったものは、一番後ろに持っていきます。

その結果、最後に使ってからの期間が一番長いものから順に追い出されていくんですね。

LFU

LFUは、Least Frequently Usedの略で、使った回数が少ない順に追い出す方式です。

こんな感じで、使った回数が少なかったものから順に追い出されていきます。

まとめ

練習問題

問題１

仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つ考える。あるタスクのページアクセス順序が
　　1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき，ページを置き換える回数の組合せとして適切なものはどれか。

（出典：平成29年度　春期　午前　問19）

問題２

LRUアルゴリズムで、ページ置き換えの判断基準に用いられる項目はどれか。

（出典：平成28年度　秋期　午前　問19）

ア、最後に参照した時刻

イ、最初に参照した時刻

ウ、単位時間当たりの参照頻度

エ、累積の参照回数