はじめに
基本情報のLRU方式について学んだことをまとめました。
最終更新日
2025年7月14日
注意
最新の状態を確認して下さい。
参考はこちら
https://www.fe-siken.com
https://www.irasutoya.com
https://www.fe-siken.com/kakomon/04_menjo/q17.html
問題
仮想記憶管理におけるページ置換えアルゴリズムとしてLRU方式を採用する。
主記憶のページ枠が、
4000、5000、6000、7000番地 (いずれも16進数) の4ページ分で、
プログラムが参照するページ番号の順が、
1→2→3→4→2→5→3→1→6→5→4のとき、
最後の参照ページ4は何番地にページインされているか。
ここで、最初の1→2→3→4の参照で、
それぞれのページは4000、5000、6000、7000番地にページインされるものとする。
4000
5000
6000
7000
考えかた
よくわからないので、ストーリー風にしてみました。
あるところに、本を並べる司書さんがいました。
本棚は2つあり、
「1」「2」「3」「4」という感じで、
本を入れていくようにお願いされました。
置く場所には、それぞれ名前がついていました。
本の順番はこちら。
ルールがいくつかあるようです。
①新しい本を置く場合は、1番長く使っていない方を取り除いてから、新しい本を置く。
②本は4つしか置けない。
③順番が決まっている。
④同じ本はいらない。かぶらないようにしないといけない。
司書さんはさっそく、並べていきます。
1→2→3→4：まず4枠をぜんぶ1冊ずつ埋めました。
2：既にあるからOK。
5：「1」だけ長らく使われていないので、「1」を追い出して「5」をその棚へ。
…と、この要領で続いていきます。
3：あるからOK。
1：今使っていない「4」が一番古いので、そこを追い出して「1」投入。
6：「2」が古いので「2」を外し、「6」入る。
5：あるからOK。
4：今、最も使われてないのは…「3」
「3」を追い出して「4」を入れる。
これで「4」は6000番の本棚に格納されて終わります！
答え
6000
LRU方式？
アルゴリズム。
「一番長く使われてないページを置き換える」
最もしばらく出番のなかった枠を追い出す。