エンジニアの将来って?

現在8年目エンジニアがプログラムの解説、ゲームの研究を書く雑記ブログです

キャッシュアルゴリズムのLFUを解説します。情報処理試験で出された問題もまとめました!

こんにちは。たいら(@tairaengineer2)です。
この記事ではキャッシュアルゴリズムLFUについて解説します。
最後の方で実際に情報処理試験の午前問題で出題されたものをまとめました。

f:id:Tairax:20180220210221p:plain

スポンサーリンク

 

キャッシュアルゴリズムとは

キャッシュアルゴリズム(英: Cache algorithm)は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。
キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。
置換アルゴリズムあるいは置換ポリシーとも。

キャッシュアルゴリズム - Wikipediaから引用させて頂きました

キャッシュアルゴリズムとは、コンピュータにキャッシュ管理するための方法です。
LFUキャッシュアルゴリズムの中の1つです。

キャッシュアルゴリズムには、FIFO 【 First-In First-Out 】というものもあります。
こちらの記事をご参考ください。

www.tairax.com

LFUとは

LFU 【 Least Frequently Used 】 LFU方式 / LFU制御方式
LFUとは、広さの限られた一時的な保管場所に何を残して何を棄てるか決定するための計算手順(アルゴリズム)の一つ。キャッシュメモリの管理やOSの仮想記憶(仮想メモリ)システムなどで利用される。

LFUとは - IT用語辞典から引用させて頂きました

LFUとはページング方式の1つです。

ページング 【 paging 】
ページングとは、仮想記憶(仮想メモリ)の方式の一つで、メモリ領域をページと呼ばれる一定の大きさの領域に分割し、物理的なアドレス(番地)とは別に仮想的なアドレスを割り当てて管理する方式。
細切れのメモリ空間を連結して一つの連続した空間として利用したり、補助記憶装置(ハードディスクなど)上にも仮想的なメモリ領域を確保することで、物理メモリの容量を超えてメモリ空間を利用することができる。
ページの大きさはOSやハードウェアによって異なるが、現代では多くのシステムが4KBのページを採用している。

ページングとは - IT用語辞典 e-Wordsから引用させて頂きました

LFUとは、参照されたページが最も少ないものから削除していくアルゴリズムです。

どんな方法でやるのかよく分かりません。
具体例を示します。

f:id:Tairax:20180326214904p:plain

最大で4ページ保存できるキャッシュメモリとパソコンがあるとします。

f:id:Tairax:20180328201142p:plain

キャッシュメモリにページ1を格納しろと命令がきたので格納します。

f:id:Tairax:20180328201354p:plain

格納できましたね。これでパソコンからページ1が求められたら渡すことができます。

おお、次々と格納しろと命令が来ました!

f:id:Tairax:20180328202144p:plain

まだ格納できるので格納します。

f:id:Tairax:20180328202406p:plain

今度はあのページを読みたいという命令が飛んできました。

f:id:Tairax:20180328202730p:plain

パソコンの命令を順番どおり、ページ1、ページ2、ページ1、ページ4を渡します。

f:id:Tairax:20180405213350p:plain

落ち着いたかと一息ついていたら

f:id:Tairax:20180405213736p:plain

4つしか格納する場所がないのに新たに格納しろと命令が来ました。
この場合、新たなページを格納するために追い出すページは

f:id:Tairax:20180405214552p:plain

ページ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の解説です。
あなたの勉強に少しでもお役に立てれば幸いです。
ではでは~(・ω・)ノシ

 

ほかにも勉強記事を書いてます。
よければご参考ください。

私が基本情報処理試験に合格したときの勉強方法をご紹介します!

絶対パスと相対パスのちがいを解説します。情報処理試験で出された問題もまとめました!

RFM分析を解説!情報処理試験で出された問題もまとめました!