ページ置換えアルゴリズムとは？図解でわかる【基本情報技術者試験対策】

基本情報技術者試験や応用情報技術者試験で出題される「ページ置換えアルゴリズム」の問題。FIFO、LIFO、LRU、LFUの動きを理解していないと難しく感じる問題ですが、動きを理解していればそこまで難しい問題ではありません。

本記事では、ページング方式の「ページ置換えアルゴリズム」について図解を利用して分かりやすく解説しています。

ページング方式のページ置換えアルゴリズム

ページング方式とは、仮想記憶（仮想メモリ）の実現方式のひとつで、メモリ領域を「ページ」と呼ばれる一定の大きさの領域に分割し管理する方式のことです。

例えば、次の図のようにプログラムAを仮想記憶に記憶するとき、ページング方式ではメモリ領域を「ページ」単位で管理するため、プログラムAも「ページ」と呼ばれる一定の大きさに分割して、仮想記憶に記憶します。

仮想記憶は"仮想的な記憶領域"です。そのため、実際のデータは主記憶装置（または補助記憶装置）に記憶します。

スポンサーリンク

しかし ページング方式では、ページが必要になるまで主記憶装置にはページを読み込みません。このような手法をデマンドページングといいます。

そしてCPUからの要求でページが必要になったとき、主記憶装置にページを読み込みます。この操作を「ページイン」といいます。

またページインしようとしたとき、主記憶装置の領域に空きがない場合は、いずれかのページを補助記憶装置に追い出して空き領域を作る必要があります。この操作を「ページアウト」といいます。

このように主記憶装置の容量がいっぱいになったとき、いずれかのデータを追い出して、空き領域を作る必要があります。このとき「どのページをページアウトさせるのか」の判断が必要です。

それを決定するためのページ置換えアルゴリズムには、FIFO、LIFO、LRU、LFUがあります。

ページ置換えアルゴリズムの種類

FIFO（First In First Out）

FIFO（First In First Outの略）とは、先に入れたものから先に追い出すというアルゴリズムです。

それでは、FIFOの動作イメージを図解で解説していきます。

主記憶装置に「ページ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」～「ページ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」～「ページ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」～「ページ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

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（Least Recently Used）は、最も長い間参照されていないものから順に追い出すというアルゴリズムです。

実記憶に割り当てられるページ数は4、ページアクセス順序が「1，2，3，4，5，2，1，3，2，6」のとき、LRUでは、どのような動きをするのか考えます。

LRUの動きを見てみると「ページ6」にアクセスするとき置換え対象となるページは「ページ5」です。

基本情報技術者試験おすすめの参考書・問題集

いちばんやさしい 基本情報技術者	『基本情報技術者試験』試験に、短期間で一発合格するための試験対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。
かやのき先生の基本情報技術者教室	基本情報技術者をめざす方のためのやさしいオールインワンタイプの参考書＆問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。
基本情報技術者 パーフェクトラーニング過去問題集	科目A・Bともに万全の対策ができる、定番の過去問題集！科目A・科目Bの両方について万全の対策ができる。
キタミ式イラストIT塾 基本情報技術者	すべての解説をイラストベースで行っているため，とてもわかりやすい解説本。いちばん最初に読む基本情報技術者試験関連の書籍を探している人におすすめ！
出るとこだけ！基本情報技術者［科目B］	基本情報技術者【科目Ｂ】対策の定番書！前提知識＋解き方＋試験問題を掲載。効率よく学習できる。
基本情報技術者 合格教本	出題範囲を体系的にきちんと理解しながら学習したい人におすすめ！基本情報技術者試験の定番テキストの改訂版。
基本情報技術者 超効率の教科書＋よく出る問題集	動画でスムーズに学習スタート、テキストでしっかり理解度を深める！よく出る問題を反復学習することで、合格に直結するチカラが身に付く！