平成30/ 2018-10-23 22:00
応用情報/ FIFO, LRU
-----FIFOとは
 First In, First Out の頭文字。
 先入れ先出し。

-----LRU(Least Recently Used)とは
 最近最も使われなかったもの。と訳せる。
 たぶん、Leastは最小のという意味なので、Least Recentlyで「最小の最近」つまり「最近の中の最小」=「最近でないもの」の意味になるのだと思う。
 Least Recently Useedで、「最小の最近の使われたもの」=「最も使われていないもの」な感じだと思う。

-----仮想記憶方式のコンピュータにおいて、実記憶に割り当てられるページ数は3とし、アクセス順序が
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
の場合で、FIFOで追い出す場合の、追い出し回数は

まず最初は
2,3,1 となり、4のときに
1回目:4,2,3 となり、5のときに
2回目:5,4,2 となり、3のときに
3回目:3,5,4 となり、、、完了!なので、3回の追い出し回数となる。

LRUの場合は、まず
2,3,1 となり、1のときに
1,2,3 のようになり、4のときに
1回目: 4,1,2 となり、5のときに
2回目: 5,4,1 となり、2のときに
3回目: 2,5,4 となり、3のときに
4回目: 3,2,5 となり、4のときに
5回目: 4,3,2 となり、5のときに
6回目: 5,4,3 となり、、完了!なので、6回の追い出し回数となる。


(Thanks!)
FIFO
http://ja.wikipedia.org/wiki/FIFO
FIFO(ファイフォ、フィフォ、フィーフォー)はFirst In, First Outを表す頭字語である。先入れ先出しと訳されることがある。 この言葉はキューの動作原理を表すものであり、最初に入ってきたものを最初に処理し、次に入ってきたものは最初の処理が終わるまで待たせる、ということを意味している。

情報工学では、キューに格納されたデータの処理方法を意味する。 キュー上の各要素はキューのデータ構造内に格納される。 最初に格納されたデータが(後で)最初に削除される。 処理は常にその順番で行われる。 これはキューの一般的な動作であるが、同じような一時格納をするデータ構造としてスタックまたはLIFOを参照されたい。
典型的なデータ構造は次のようになる。

Least Recently Used
http://ja.wikipedia.org/wiki/Least_Recently_Used
Least Recently Used (LRU) はキャッシュメモリや仮想メモリが扱うデータのリソースへの割り当てを決定するアルゴリズムである。対義語はMost Recently Used (MRU)。
和訳すると「最近最も使われなかったもの」つまり「使われてから最も長い時間が経ったもの」「参照される頻度が最も低いもの」である。
小容量で高速な記憶装置(例えば、キャッシュメモリ)がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置(例えば、主記憶装置)に保存する、というのが基本のアルゴリズムである。
なお、上の括弧内の例はキャッシュメモリの場合である。仮想メモリの場合は、小容量で高速な記憶装置を主記憶装置、大容量で低速な記憶装置を補助記憶装置に置き換えればよい。

#key#FIFO,LRU