・LRUってなに??
・図を使ってわかりやすく!
という方にとって有用な記事になっています。丁寧な図を用いていますので、詰まることなく読み進めることが可能です。では、見ていきましょう!
そもそもページとは何か、ページフォルトやページインの意味が分かっていない方は、
【図解】ページング方式が3分でわかる!【全用語解説】
・ページング方式ってなに??・他の専門用語もちゃんと説明して・図を使ってわかりやすくお願い 今回の記事では、このような方のお役に立てる記事になっています。ページング方式とは何なのか、関連用語も含めて理解し...
まずはこちらをご確認ください。
LRU(Least Recently Used)とは
ページ置き換えに使われるアルゴリズムの一種です。ページフォルト時に、最も長い間使用していないページをページアウトしようってアルゴリズムです。他にFIFO(最も古いページをどける)、OPT(最小のページフォルトで済むようにする理論上のアルゴリズム)などがあります。
LRUアルゴリズム
では、LRUアルゴリズムを具体例で解説していきます。今回の具体例の前提条件は以下の通りです。
前提条件
- ページ枠数:3
- プログラムの大きさ:5ページ
- 参照ページ番号順:0→1→2→3→0→3→4→2→3→2→1→3
では、アルゴリズムを見ていきましょう。図を見るだけでほぼ理解できると思います。
具体例
分かりやすいようにスタック(データ構造の一種)っぽく実装した場合は上図のような感じになります。参照ページがページ枠内になければ、スタックの最下部をページアウトし、スタックの最上部に参照ページ(使いたいページ)を挿入します。使われないページはどんどんスタックの下部にいく…という感じですね。
ページフォルトは、ページアウトしなくても発生していることに注意してください。勘違いが多いところです。図で見ると結構簡単に思えたのではないでしょうか。
まとめ
用語を先に確認し、図で理解すれば簡単ですね!
お疲れ様でした。
コメント