こんにちは。たいら(@tairaengineer2)です。
この記事ではキャッシュアルゴリズムのLFUについて解説します。
最後の方で実際に情報処理試験の午前問題で出題されたものをまとめました。
スポンサーリンク
キャッシュアルゴリズムとは
キャッシュアルゴリズム(英: Cache algorithm)は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。
キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。
置換アルゴリズムあるいは置換ポリシーとも。
キャッシュアルゴリズム - Wikipediaから引用させて頂きました
キャッシュアルゴリズムとは、コンピュータにキャッシュを管理するための方法です。
LFUはキャッシュアルゴリズムの中の1つです。
キャッシュアルゴリズムには、FIFO 【 First-In First-Out 】というものもあります。
こちらの記事をご参考ください。
LFUとは
LFU 【 Least Frequently Used 】 LFU方式 / LFU制御方式
LFUとは、広さの限られた一時的な保管場所に何を残して何を棄てるか決定するための計算手順(アルゴリズム)の一つ。キャッシュメモリの管理やOSの仮想記憶(仮想メモリ)システムなどで利用される。
LFUとは - IT用語辞典から引用させて頂きました
LFUとはページング方式の1つです。
ページング 【 paging 】
ページングとは、仮想記憶(仮想メモリ)の方式の一つで、メモリ領域をページと呼ばれる一定の大きさの領域に分割し、物理的なアドレス(番地)とは別に仮想的なアドレスを割り当てて管理する方式。
細切れのメモリ空間を連結して一つの連続した空間として利用したり、補助記憶装置(ハードディスクなど)上にも仮想的なメモリ領域を確保することで、物理メモリの容量を超えてメモリ空間を利用することができる。
ページの大きさはOSやハードウェアによって異なるが、現代では多くのシステムが4KBのページを採用している。
ページングとは - IT用語辞典 e-Wordsから引用させて頂きました
LFUとは、参照されたページが最も少ないものから削除していくアルゴリズムです。
どんな方法でやるのかよく分かりません。
具体例を示します。
最大で4ページ保存できるキャッシュメモリとパソコンがあるとします。
キャッシュメモリにページ1を格納しろと命令がきたので格納します。
格納できましたね。これでパソコンからページ1が求められたら渡すことができます。
おお、次々と格納しろと命令が来ました!
まだ格納できるので格納します。
今度はあのページを読みたいという命令が飛んできました。
パソコンの命令を順番どおり、ページ1、ページ2、ページ1、ページ4を渡します。
落ち着いたかと一息ついていたら
4つしか格納する場所がないのに新たに格納しろと命令が来ました。
この場合、新たなページを格納するために追い出すページは
ページ3です。ページ3を追い出して開いたページにページ5を格納します。
このようにLFUとは、参照されたページが最も少ないものから削除していくアルゴリズムです。
実際に出た試験
キャッシュアルゴリズムのLFUについて分かりました!
では、実際に問題を解いてみましょう!
情報処理試験で、午前問題に出題された問題をピックアップします。
基本情報
平成17年秋期問27 ページ置換えアルゴリズム|基本情報技術者試験.com
平成24年秋期問19 LRU方式|基本情報技術者試験.com
平成27年秋期問17 ページ入替え方式|基本情報技術者試験.com
応用情報技術者試験
平成23年特別問21 ページを置き換える回数の組合せ|応用情報技術者試験.com
平成29年春期問16 置換えアルゴリズムはどれか|応用情報技術者試験.com
※平成22年春期問18と平成29年春期問16は同じ問題なので、平成29年春期問16のみ載せてます。
スポンサーリンク
まとめ:LFUとは、参照していない順
以上がキャッシュアルゴリズム、LFUの解説です。
あなたの勉強に少しでもお役に立てれば幸いです。
ではでは~(・ω・)ノシ
ほかにも勉強記事を書いてます。
よければご参考ください。
私が基本情報処理試験に合格したときの勉強方法をご紹介します!