目次
ページング方式のページ置換えアルゴリズム
ページング方式とは、仮想記憶（仮想メモリ）の実現方式のひとつで、メモリ領域を「ページ」と呼ばれる一定の大きさの領域に分割し管理する方式のことです。
仮想記憶とページング方式の詳細はこちら
次の図は、ページング方式のイメージ例です。プログラムを「ページ」単位に分割して仮想記憶に記憶しています。
仮想記憶は"仮想的な記憶領域"です。そのため、実際のデータは主記憶装置に記憶します。ただしページング方式では、ページが必要になるまで主記憶装置にページを読み込みません。（デマンドページング）
そして、CPUからの要求でページが必要になったとき、主記憶装置にページを読み込みます。この操作を「ページイン」といいます。
またページインしたときに、主記憶装置上の領域に空きがない場合は、いずれかのページを補助記憶装置に追い出して空き領域を作る必要があります。この操作を「ページアウト」といいます。
このとき「どのページをページアウトさせるのか」の判断が必要です。それを決定するためのページ置換えアルゴリズムには、次のような種類があります。
スポンサーリンク
ページ置換えアルゴリズムの種類
FIFO（First In First Out）
FIFO（First In First Out）とは、先に入れたものから先に取り出すというアルゴリズムです。「先入れ先出し」とも呼ばれています。
以下は、FIFOを利用した置換えアルゴリズムの動作イメージ例です。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番で参照するという要求があったとします。
1.「ページ1」を参照
主記憶装置に「ページ1」は存在しないため、「ページ1」をページインして参照します。
2.「ページ2」を参照
主記憶装置に「ページ2」は存在しないため、「ページ2」をページインして参照します。
3.「ページ3」を参照
主記憶装置に「ページ3」は存在しないため、「ページ3」をページインして参照します。
4. 再び「ページ1」を参照
主記憶装置に「ページ1」は存在するため、そのまま「ページ1」を参照します。
5.「ページ4」を参照
主記憶装置に「ページ4」は存在しないため、「ページ4」をページインします。
しかし主記憶装置に空き領域がないため、最初にページインした「ページ1」をページアウトさせて空き領域を作ります。
そして、その領域に「ページ4」をページインして参照します。
LIFO（Last In First Out）
LIFO（Last In First Out）とは、後に入れたものから先に取り出すというアルゴリズムです。「後入れ先出し」とも呼ばれています。
以下は、LIFOを利用した置換えアルゴリズムの動作イメージ例です。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番で参照するという要求があったとします。
1.「ページ1」を参照
主記憶装置に「ページ1」は存在しないため、「ページ1」をページインして参照します。
2.「ページ2」を参照
主記憶装置に「ページ2」は存在しないため、「ページ2」をページインして参照します。
3.「ページ3」を参照
主記憶装置に「ページ3」は存在しないため、「ページ3」をページインして参照します。
4. 再び「ページ1」を参照
主記憶装置に「ページ1」は存在するため、そのまま「ページ1」を参照します。
5.「ページ4」を参照
主記憶装置に「ページ4」は存在しないため、「ページ4」をページインします。
しかし主記憶装置に空き領域がないため、最後にページインした「ページ3」をページアウトさせて空き領域を作ります。
そして、その領域に「ページ4」をページインして参照します。
LRU（Least Recently Used）
LRU（Least Recently Used）とは、最も長い間参照されていないものから順に取り出すというアルゴリズムです。
スポンサーリンク
以下は、LRUを利用した置換えアルゴリズムの動作イメージ例です。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番で参照するという要求があったとします。
1.「ページ1」を参照
主記憶装置に「ページ1」は存在しないため、「ページ1」をページインして参照します。
2.「ページ2」を参照
主記憶装置に「ページ2」は存在しないため、「ページ2」をページインして参照します。
3.「ページ3」を参照
主記憶装置に「ページ3」は存在しないため、「ページ3」をページインして参照します。
4. 再び「ページ1」を参照
主記憶装置に「ページ1」は存在するため、そのまま「ページ1」を参照します。
5.「ページ4」を参照
主記憶装置に「ページ4」は存在しないため、「ページ4」をページインします。
しかし主記憶装置に空き領域がないため、最も長い間参照されていない「ページ2」をページアウトさせて空き領域を作ります。
※前回参照したのが「ページ1」その前が「ページ3」その前が「ページ2」なので、最も長い間参照されていないのは「ページ2」
そして、その領域に「ページ4」をページインして参照します。
LFU（Least Frequently Used）
LFU（Least Frequently Used）とは、最も使用頻度が低いものから順に取り出すというアルゴリズムです。
以下は、LFUを利用した置換えアルゴリズムの動作イメージ例です。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]の順番で参照するという要求があったとします。
1.「ページ1」を参照
主記憶装置に「ページ1」は存在しないため、「ページ1」をページインして参照します。
2.「ページ2」を参照
主記憶装置に「ページ2」は存在しないため、「ページ2」をページインして参照します。
3.「ページ3」を参照
主記憶装置に「ページ3」は存在しないため、「ページ3」をページインして参照します。
4. 再び「ページ1」を参照
主記憶装置に「ページ1」は存在するため、そのまま「ページ1」を参照します。
5. 再び「ページ3」を参照
主記憶装置に「ページ3」は存在するため、そのまま「ページ3」を参照します。
6. 「ページ4」を参照
主記憶装置に「ページ4」は存在しないため、「ページ4」をページインします。
しかし主記憶装置に空き領域がないため、最も使用頻度が低い「ページ2」をページアウトさせて空き領域を作ります。
※「ページ1」は2回、「ページ2」は1回、「ページ3」は2回で、最も使用頻度が低いのは「ページ2」
そして、その領域に「ページ4」をページインして参照します。