基本情報でわかる FIFO LFU LRU 「略語の意味がわかればわかる」
2021-12-02 更新
error
この記事は基本情報技術者試験の旧制度（ 2022 年以前）の記事ですが、試験対策ではなく、技術用語を理解する上では問題ないと考えています。
試験対策としてお読みになる場合は、現在の試験制度では出題されない午後問題を一部題材にしているので、ご注意ください。
この連載では、基本情報技術者試験によく出題されるテクノロジー関連の用語を、午前問題と午後問題のセットを使って解説します。
午前問題で用語の意味や概念を知り、午後問題で技術の活用方法を知ってください。それによって、単なる丸暗記では得られない明確さで、用語を理解できるようになります。
今回のテーマは、 仮想メモリのページングアルゴリズム FIFO / LFU / LRU です。
もくじ
仮想メモリのページングアルゴリズム FIFO / LFU / LRU とは？
はじめに、仮想メモリのページングアルゴリズムとは何かを説明しましょう。
現在の一般的なコンピュータには、大容量のメモリが搭載されていますが、同時に複数のプログラムを起動したり、巨大なプログラムを実行したりすると、メモリが足りなくなってしまうことがあります。
その場合に備えて、コンピュータの基本ソフトウェアである OS には、メモリの中で今後使われる可能性が少ないページを、ハードディスクに一時的に退避させることで、メモリを空けるというという機能があり、これを仮想メモリと呼びます。
ハードディスクを、仮想的にメモリとして使うからです。ページとは、プログラム全体を固定サイズに区切った部分・部分のことであり、 Windows では 1 ページのサイズが 4K バイトです。
仮想メモリのページングアルゴリズムとは、メモリの中で今後使われる可能性が少ないページを決める方法のことであり、
- FIFO
- LFU
- LRU
の 3 つがあります。
仮想メモリであるハードディスクから、実メモリである主記憶装置（これまでメモリと呼んでいたもの）にページを読み込むことを ページイン と呼び、実メモリから仮想メモリにページを退避させることを ページアウト と呼びます。
- FIFO では
- 「最初にページインしたページ」
- LFU では
- 「利用された回数が最も少ないページ」
- LRU では
- 「最後に利用してから最も時間が経過しているページ」
それぞれ今後使われる可能性が少ないページとして、それを仮想メモリに退避させます。
FIFO、LFU、LRUの例
FIFO, LFU, LRU の例を示しましょう。
ハードディスクの中に A, B, C, D という 4 つのページから構成されたプログラムがあり、それらを 3 つのページを持つ実メモリで実行するとします。
プログラムの内容が、
Aarrow_forwardBarrow_forwardBarrow_forwardCarrow_forwardA
という順に利用されたとすれば、この時点でメインメモリの 3 つのページは［ A ］［ B ］［ C ］で満杯になっています。
次に、 D を利用したい場合には、今後使われる可能性が少ないページを決めて、それを仮想メモリに退避させ、実メモリを空ける必要があります。退避させるページは、採用したページングアルゴリズムによって、以下のように異なります。
- ページングアルゴリズムに FIFO を採用した場合
- A → B → B → C → A で最初にページインしたページは A なので、 A を仮想メモリに退避させます。
- ページングアルゴリズムに LFU を採用した場合
- A → B → B → C → A において、 A は 2 回、 B は 2 回、 C は 1 回使われていて、利用された回数が最も少ないページは C なので、 C を仮想メモリに退避させます。
- ページングアルゴリズムに LRU を採用した場合
- A → B → B → C → A で最後に利用してから最も時間が経過しているページは B なので、 B を仮想メモリに退避させます。
Aarrow_forwardBarrow_forwardBarrow_forwardCarrow_forwardAFIFO では A を退避LRU では B を退避LFU では C を退避
どれがFIFO、LFU、LRUなのかを覚えるコツ
これで、「最初にページインしたページ」「利用された回数が最も少ないページ」「最後に利用してから最も時間が経過しているページ」の意味がわかったと思います。
ただし、どれが FIFO, LFU, LRU に該当するのかを覚えなければ問題を解けません。このような英語の略語を覚えるコツは、略語の意味を調べて、それを日本語に直訳することです。
- FIFO
- First In First Out の略語で、直訳すると「最初に入れたものを、最初に出す」です。これは、「最初にページインしたページ」に該当します。
- LFU
- Least Frequently Used の略語で、直訳すると「最もそうでない（ Least は、 Little の最上級です）、頻繁に、使われる」です。これは、「最も頻繁でない」が「最も回数が少ない」と同じなので、「利用された回数が最も少ないページ」に該当します。
- LRU
- Least Recently Used の略語で、直訳すると「最もそうでない、最近、使われる」です。これは、「最も、最近ではない」が、「最後に利用してから最も時間が経過しているページ」に該当します。
いかがでしょう？ FIFO, LFU, LRU という略語の意味を調べて、それを日本語に直訳すれば、それぞれが、どういうページングアルゴリズムに該当するかを覚えられたでしょう。
仮想メモリのページングアルゴリズム FIFO、LFU、LRU に関する午前問題
それでは、仮想メモリのページングアルゴリズムに関する午前問題を解いてみましょう。
仮想記憶管理のページ入替え方式のうち，最後に使われてからの経過時間が最も長いページを入れ替えるものはどれか。
ア FIFO イ LFU ウ LIFO エ LRU
「最後に使われてからの経過時間が最も長い」は、「最も、最近ではない」であり、「最近」が Recently 、「最もそうでない」が Least なので、これは LRU = Least Recently Used です。正解は、選択肢エです。
午前問題は、選択肢が 4 つ必要なので、ページングアルゴリズムとは関係のない LIFO という略語が選択肢ウにあります。これは、気にしないでください。
解答 エ
仮想メモリのページングアルゴリズム FIFO / LFU / LRU に関する午後問題
今度は、仮想メモリのページングアルゴリズムに関する午後問題（一部抜粋）を解いてみましょう。以下は、問題の冒頭部分です。
このように、長々とした説明文があるのが午後問題の特徴ですが、これを見て怖気づいてはいけません。FIFO, LFU, LRU の意味がわかれば、ほとんどの設問に正解できるからです。
「ページフォールト」という新たな用語が登場しますが、これは、実行しようとしたページが実メモリに存在しないことです。ページフォールトとなったときには、そのシステムで採用されているページングアルゴリズムを使って、今後使われる可能性が少ないページを決め、そのページをハードディスクに退避させます。
仮想記憶方式に関する次の記述を読んで，設問 1 ~ 3 に答えよ。
OS の主記憶管理において，仮想記憶方式は， OS が提供する論理的な記憶領域（以下，仮想記憶という）上のアドレスと主記憶上の物理的なアドレスを対応付けて管理する方式である。仮想記憶方式では，補助記憶装置を仮想記憶として用いるので，仮想記憶上に主記憶の容量を超えるプログラムを格納することができる。仮想記憶上のアドレス空間を仮想アドレス空間，主記憶上のアドレス空間を物理アドレス空間と呼び，それぞれの空間の記憶場所を仮想アドレスと物理アドレスで指定する。
仮想記依方式の一つに，ページング方式がある。ページング方式は，仮想アドレス空間と物理アドレス空間のそれぞれをページと呼ぶ固定長の領域に分割しておき，ページ単位でアドレス空間を管理する。ページング方式による仮想アドレス空港のページと物理アドレス空間のページの対応例を，図1に示す。図1では，補助記憶装置に格納されているプログラム A は，a1, a2, a3, a4, a5 に分割されて，仮想ページ番号 1 ~ 5 のページに格納されている。
以下は、設問 1 です。ちょっと言葉が悪いですが、「冒頭で、あれだけ小難しそうな説明をしておきながら、こんな簡単な設問なのか！」と言いたくなるような内容でしょう。
プログラムの実行過程で存在ビットを調べ，プログラムの実行に必要なページがaに存在していないときには，ページフォールトという割込みが発生する。ページフォールトが発生すると，ページアウトやページインなどのページ置換え処理が実行される。ページ置換え処理のアルゴリズムには，ページインしてから最も時間が経過しているページを置換え対象とする FIFO アルゴリズムや，参照されていない時間が最も長いページを置換え対象とする bアルゴリズムなどがある。
解答群
ア LFU イ LIFO ウ LRU
エ 仮想アドレス空間 オ 物理アドレス空間
ページフォールトが発生するのは、実行しようとしたページが実メモリに存在しないときです。解答群を見ると、「実メモリ」に該当するのは、選択肢オの「物理アドレス空間」です。
したがって、空欄 a の正解は、選択肢オです。選択肢エの「仮想アドレス空間」は、「仮想メモリ」に該当します。
空欄 b は、「参照されていない時間が最も長いページを置き換え対象とする」のですから、これは「最後に使われてからの経過時間が最も長い」と同じであり、「最もそうでない、最近、使われる」の LRU ＝ Least Recently Used です。
したがって、空欄 b の正解は、選択肢ウの「 LRU 」です。
ページングアルゴリズムを手作業でコツコツやる
全問掲載すると長くなりすぎるので、設問 2 を飛ばして、設問 3 を見てみましょう。
さすが、 1 問あたりの解答時間が長い午後問題だけあって、手間がかかることをやらせます。 FIFO のページングアルゴリズムを実際にやってみよ、という内容です。
それも、物理ページ（実メモリ）が 3 個と 4 個、ぞれぞれの場合です。この手の問題は、手作業でコツコツやるしかありません。
「なぜ、同じことを 2 回もやらせるのだろう？」と疑問に思うでしょう。
あらかじめ種明かしをしてしまうと、ページフォールトの回数は、物理ページの個数が多い方が少ないと思うかもしれませんが、物理ページの個数が多い方が多くなる場合もあるのです。それを知ってほしい、という教育的な意図があって、同じことを 2 回もやらせるのでしょう（たぶん）。
後でわかりますが、この問題では、物理ページが 3 個より 4 個の方がページフォールトの回数が多くなります。
ページ置換えアルゴリズムとして FIFO アルゴリズムを採用する。プログラムの実行過程で仮想ページが次の順で参照されるとき，物理ページの個数が 3 の場合のページフォールトの回数は， c回である。そして，物理ページの個数を 4 に増やした場合のページフォールトの回数はd回である。ここで，プログラムの実行開始時点では，物理アドレス空間にはどのページも存在していないものとする。
【仮想ページの参照順を示す仮想ページ番号の並び】
1 → 4 → 3 → 2 → 1 → 4 → 5 → 1 → 4 → 3 → 2 → 5 → 1
解答群
ア 8 イ 9 ウ 10 エ 11 オ 12
それでは、がんばって手作業でページングアルゴリズムをやってみましょう。
ここでは、
参照するページの順序を縦に書き、
ページフォールトの発生を fault の頭文字の F で示し、
参照後の物理ページの内容を ［ と ］ で囲んで示し、
その時点で退避するページの候補をstarで示します。
物理ページが 3 個のときは、以下のように 10 回のページフォールトが発生します。したがって、空欄 c の正解は、選択肢ウです。
参照するページ 参照後の物理ページの内容 1 F ［★1］［ ］［ ］ ↓ 4 F ［★1］［ 4 ］［ ］ ↓ 3 F ［★1］［ 4 ］［ 3 ］ ↓ 2 F ［ 2 ］［★4］［ 3 ］ ↓ 1 F ［ 2 ］［ 1 ］［★3］ ↓ 4 F ［★2］［ 1 ］［ 4 ］ ↓ 5 F ［ 5 ］［★1］［ 4 ］ ↓ 1 ［ 5 ］［★1］［ 4 ］ ↓ 4 ［ 5 ］［★1］［ 4 ］ ↓ 3 F ［ 5 ］［ 3 ］［★4］ ↓ 2 F ［★5］［ 3 ］［ 2 ］ ↓ 5 ［★5］［ 3 ］［ 2 ］ ↓ 1 F ［ 1 ］［★3］［ 2 ］
物理ページが 4 個のときは、以下のように 11 回のページフォールトが発生します。
参照するページ 参照後の物理ページの内容 1 F ［★1］［ ］［ ］［ ］ ↓ 4 F ［★1］［ 4 ］［ ］［ ］ ↓ 3 F ［★1］［ 4 ］［ 3 ］［ ］ ↓ 2 F ［★1］［ 4 ］［ 3 ］［ 2 ］ ↓ 1 ［★1］［ 4 ］［ 3 ］［ 2 ］ ↓ 4 ［★1］［ 4 ］［ 3 ］［ 2 ］ ↓ 5 F ［ 5 ］［★4］［ 3 ］［ 2 ］ ↓ 1 F ［ 5 ］［ 1 ］［★3］［ 2 ］ ↓ 4 F ［ 5 ］［ 1 ］［ 4 ］［★2］ ↓ 3 F ［★5］［ 1 ］［ 4 ］［ 3 ］ ↓ 2 F ［ 2 ］［★1］［ 4 ］［ 3 ］ ↓ 5 F ［ 2 ］［ 5 ］［★4］［ 3 ］ ↓ 1 F ［ 2 ］［ 5 ］［ 1 ］［★3］
したがって、空欄 d の正解は、選択肢エです。物理ページが3個のときは 10 回だったので、物理ページが 4 個のときの方が多くなっています。
解答 設問 1 a – オ、b – ウ 設問 3 c – ウ、d – エ
いかがでしたか？ FIFO, LFU, LRU という略語の意味がわかれば、仮想メモリのページングアルゴリズムに関する午前問題も午後問題も、すんなり正解できたでしょう。
この連載では、今後も、多くの受験者が苦手としている用語を取り上げて行きます。それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
基本情報でわかる IPアドレス と サブネットマスク
update
基本情報でわかる ホワイトボックステスト
update
基本情報でわかる トランザクション
update
基本情報でわかる コンパイラ 最適化
update
基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる」
update
基本情報でわかる 浮動小数点 「3つの情報で1つの数を表す仕組みを知れば、浮動小数点数がわかる」
update
基本情報でわかる MIME タイプ 「電子メールの仕組みを知れば役割がわかる」
update
基本情報でわかる 7セグメントLED 「 1 と 0 を書き込めば点灯するパターンがわかる」
update
基本情報でわかる 論理演算 「真理値表を書けば、半加算器と全加算器の仕組みがわかる」
update
基本情報でわかる SMTP ／ POP3 「ITエンジニア視点で見れば役割がわかる」
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
