問題
仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つ考える。あるタスクのページアクセス順序が
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき，ページを置き換える回数の組合せとして適切なものはどれか。
基本情報技術者平成29年春期 午前問19
問題
ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。ここで，初期状態では主記憶にどのページも存在しないものとする。
ア：1 イ：2 ウ：4 エ：5
基本情報技術者平成27年春期 午前問20
基本情報技術者試験や応用情報技術者試験で出題される「ページ置換えアルゴリズム」の問題。FIFO、LIFO、LRU、LFUの動きを理解していないと難しく感じる問題ですが、動きを理解していればそこまで難しい問題ではありません。
本記事では、ページング方式の「ページ置換えアルゴリズム」について図解を利用して分かりやすく解説しています。
本記事で学べること
- ページング方式のページ置換えアルゴリズムについて理解する
- FIFO（First In First Out）の動きを理解する
- LIFO（Last In First Out）の動きを理解する
- LRU（Least Recently Used）の動きを理解する
- LFU（Least Frequently Used）の動きを理解する
- 基本情報技術者試験の過去問の解き方を学ぶ
目次
ページング方式のページ置換えアルゴリズム
ページング方式とは、仮想記憶（仮想メモリ）の実現方式のひとつで、メモリ領域を「ページ」と呼ばれる一定の大きさの領域に分割し管理する方式のことです。
例えば、次の図のようにプログラムAを仮想記憶に記憶するとき、ページング方式ではメモリ領域を「ページ」単位で管理するため、プログラムAも「ページ」と呼ばれる一定の大きさに分割して、仮想記憶に記憶します。
仮想記憶は"仮想的な記憶領域"です。そのため、実際のデータは主記憶装置（または補助記憶装置）に記憶します。
スポンサーリンク
しかし ページング方式では、ページが必要になるまで主記憶装置にはページを読み込みません。このような手法をデマンドページングといいます。
そしてCPUからの要求でページが必要になったとき、主記憶装置にページを読み込みます。この操作を「ページイン」といいます。
またページインしようとしたとき、主記憶装置の領域に空きがない場合は、いずれかのページを補助記憶装置に追い出して空き領域を作る必要があります。この操作を「ページアウト」といいます。
このように主記憶装置の容量がいっぱいになったとき、いずれかのデータを追い出して、空き領域を作る必要があります。このとき「どのページをページアウトさせるのか」の判断が必要です。
それを決定するためのページ置換えアルゴリズムには、FIFO、LIFO、LRU、LFUがあります。
ページ置換えアルゴリズムの種類
FIFO（First In First Out）
FIFO（First In First Outの略）とは、先に入れたものから先に追い出すというアルゴリズムです。
それでは、FIFOの動作イメージを図解で解説していきます。
例題
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番でページを参照するとき、FIFOではどのような動作をするか。主記憶装置には、最大で3ページしか格納できないものとする。
主記憶装置に「ページ1」～「ページ3」を配置して参照する
まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置（ページイン）して、ページを参照します。（ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
続いて「ページ1」を参照
続いて「ページ1」を参照します。（主記憶装置には先ほど配置済み）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
最初にページインした「ページ1」を追い出す
続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。ここでFIFOでは「先に入れたものから先に追い出す」ため、最初にページインした「ページ1」を追い出し（ページアウト）、主記憶装置に空き領域を作ります。
主記憶装置に「ページ4」を配置して参照する
最後に「ページ4」を主記憶装置に配置（ページイン）して、ページを参照します。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
LIFO（Last In First Out）
LIFO（Last In First Outの略）とは、後に入れたものから先に追い出すというアルゴリズムです。
それでは、LIFOの動作イメージを図解で解説していきます。
例題
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番でページを参照するとき、LIFOではどのような動作をするか。主記憶装置には、最大で3ページしか格納できないものとする。
スポンサーリンク
主記憶装置に「ページ1」～「ページ3」を配置して参照する
まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置（ページイン）して、ページを参照します。（ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
続いて「ページ1」を参照
続いて「ページ1」を参照します。（主記憶装置には先ほど配置済み）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
最後にページインした「ページ3」を追い出す
続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。ここでLIFOでは「後に入れたものから先に追い出す」ため、最後にページインした「ページ3」を追い出し（ページアウト）、主記憶装置に空き領域を作ります。
主記憶装置に「ページ4」を配置して参照する
最後に「ページ4」を主記憶装置に配置（ページイン）して、ページを参照します。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
LRU（Least Recently Used）
LRU（Least Recently Usedの略）とは、最も長い間参照されていないものから順に追い出すというアルゴリズムです。
それでは、LRUの動作イメージを図解で解説していきます。
例題
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]の順番でページを参照するとき、LRUではどのような動作をするか。主記憶装置には、最大で3ページしか格納できないものとする。
主記憶装置に「ページ1」～「ページ3」を配置して参照する
まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置（ページイン）して、ページを参照します。（ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
続いて「ページ1」を参照
続いて「ページ1」を参照します。（主記憶装置には先ほど配置済み）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
最も長い間参照されていない「ページ2」を追い出す
続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。ここでLRUでは「最も長い間参照されていないものから順に追い出す」ため、最も長い間参照されていない「ページ2」を追い出し（ページアウト）、主記憶装置に空き領域を作ります。
主記憶装置に「ページ4」を配置して参照する
最後に「ページ4」を主記憶装置に配置（ページイン）して、ページを参照します。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ4]
LFU（Least Frequently Used）
LFU（Least Frequently Usedの略）とは、最も使用頻度が低いものから順に追い出すというアルゴリズムです。
それでは、LFUの動作イメージを図解で解説していきます。
例題
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]の順番でページを参照するとき、LFUではどのような動作をするか。主記憶装置には、最大で3ページしか格納できないものとする。
主記憶装置に「ページ1」～「ページ3」を配置して参照する
まずは[ページ1]→ [ページ2] → [ページ3]の順番に主記憶装置に配置（ページイン）して、ページを参照します。（ページ1を配置して参照 → ページ2を配置して参照 → ページ3を配置して参照）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
続いて「ページ1」と「ページ3」を参照
続いて「ページ1」と「ページ3」を参照します。（主記憶装置には先ほど配置済み）
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
最も使用頻度が低い「ページ2」を追い出す
続いて「ページ4」を配置しようとするも、主記憶装置の容量はいっぱいのため、いずれかのページを追い出す必要があります。ここでLFUでは「最も使用頻度が低いものから順に追い出す」ため、最も使用頻度が低い「ページ2」を追い出し（ページアウト）、主記憶装置に空き領域を作ります。
（使用頻度は「ページ1：2回」「ページ2：1回」「ページ3：2回」とページ2が最も低い）
主記憶装置に「ページ4」を配置して参照する
最後に「ページ4」を主記憶装置に配置（ページイン）して、ページを参照します。
[ページ1] → [ページ2] → [ページ3] → [ページ1] → [ページ3] → [ページ4]
スポンサーリンク
基本情報技術者試験 過去問の解説
基本情報技術者試験 平成29年春期 午前問19
問題
仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つ考える。あるタスクのページアクセス順序が
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
のとき，ページを置き換える回数の組合せとして適切なものはどれか。
基本情報技術者平成29年春期 午前問19
FIFO（First In First Out）は、先に入れたものから先に追い出すアルゴリズム、LRU（Least Recently Used）は、最も長い間参照されていないものから順に追い出すというアルゴリズムです。
実記憶に割り当てられるページ数は3、ページアクセス順序が「1, 3, 2, 1, 4, 5, 2, 3, 4, 5」のとき、FIFOとLRUでは、どのような動きをするのか考えます。
まずFIFOの動きを見てみると、ページを置き換える（主記憶装置の容量がいっぱいでページアウトが発生し、新しいページをページインした回数）回数は3回です。
続いてLRUの動きを見てみると、ページを置き換える回数は6回です。
基本情報技術者試験 平成27年春期 午前問20
問題
ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。ここで，初期状態では主記憶にどのページも存在しないものとする。
ア：1 イ：2 ウ：4 エ：5
基本情報技術者平成27年春期 午前問20
LRU（Least Recently Used）は、最も長い間参照されていないものから順に追い出すというアルゴリズムです。
実記憶に割り当てられるページ数は4、ページアクセス順序が「1，2，3，4，5，2，1，3，2，6」のとき、LRUでは、どのような動きをするのか考えます。
LRUの動きを見てみると「ページ6」にアクセスするとき置換え対象となるページは「ページ5」です。
