【図解】LRU方式アルゴリズムを具体例付き徹底解説

ソフトウェア
スポンサーリンク

 

・LRUってなに??

・図を使ってわかりやすく!

 

という方にとって有用な記事になっています。丁寧な図を用いていますので、詰まることなく読み進めることが可能です。では、見ていきましょう!

そもそもページとは何か、ページフォルトやページインの意味が分かっていない方は、

【図解】ページング方式が3分でわかる!【全用語解説】
 ・ページング方式ってなに??・他の専門用語もちゃんと説明して・図を使ってわかりやすくお願い 今回の記事では、このような方のお役に立てる記事になっています。ページング方式とは何なのか、関連用語も含めて理解し...

まずはこちらをご確認ください。

 

LRU(Least Recently Used)とは

ページ置き換えに使われるアルゴリズムの一種です。ページフォルト時に、最も長い間使用していないページをページアウトしようってアルゴリズムです。他にFIFO(最も古いページをどける)、OPT(最小のページフォルトで済むようにする理論上のアルゴリズム)などがあります。

 

LRUアルゴリズム

では、LRUアルゴリズムを具体例で解説していきます。今回の具体例の前提条件は以下の通りです。
 

前提条件

  • ページ枠数:3
  • プログラムの大きさ:5ページ
  • 参照ページ番号順:0→1→2→3→0→3→4→2→3→2→1→3

では、アルゴリズムを見ていきましょう。図を見るだけでほぼ理解できると思います。
 

具体例

lruイラスト図

分かりやすいようにスタック(データ構造の一種)っぽく実装した場合は上図のような感じになります。参照ページがページ枠内になければ、スタックの最下部をページアウトし、スタックの最上部に参照ページ(使いたいページ)を挿入します。使われないページはどんどんスタックの下部にいく…という感じですね。

ページフォルトは、ページアウトしなくても発生していることに注意してください。勘違いが多いところです。図で見ると結構簡単に思えたのではないでしょうか。

 

まとめ

用語を先に確認し、図で理解すれば簡単ですね!

お疲れ様でした。

 

基本・応用情報の解説まとめ記事へ

 

コメント

タイトルとURLをコピーしました