平成31年度 春期 午前 問19
ソフトウェア
LRUに関する問題
仮想記憶管理におけるページ置換えアルゴリズムとして 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
答えと解説を見る
✓ これが正解ウ6000
解説
最も長く使っていない枠が、新しいページで置き換わります。
LRU は、参照が起きるたびに直近に使われた時刻を更新し、置換えが必要になった時点で最も古い時刻の枠を追い出す方式です。設問では最初の四つの参照で 1 〜 4 のページがそれぞれ 4000 〜 7000 番地に並んだあと、2 が来て 5000 番地の使用時刻が更新されます。次に 5 が来ると、この時点で最古の 4000 番地（ページ 1）が追い出されて 5 が入ります。3 の再参照で 6000 番地の時刻が更新され、次の 1 では最古が 7000 番地（ページ 4）となり、そこに 1 が置き換わります。続く 6 では 5000 番地（ページ 2）が最古で追い出されて 6 が入り、5 の再参照で 4000 番地の時刻が更新されます。最後の 4 が来た時点で最古は 6000 番地（ページ 3）となり、そこにページ 4 が置き換わります。よって最後の 4 は 6000 番地に入ります。
ほかの選択肢はなぜ違うのか
- ア4000：4000 になるのは、最終参照の直前で 4000 番地が最古と読み違えた場合の値です。実際は 5 が直前に参照されて 4000 番地の時刻が更新されており、そこは最古の候補ではありません。
- イ5000：5000 になるのは、6 が入る前に別の枠が追い出されたと数えた場合の値です。実際は 6 が入る段で 5000 番地が置き換わっており、その時刻は 6000 番地の 3 の再参照より新しいため、そこは最古ではありません。
- エ7000：7000 になるのは、1 が入る段で追い出されたページを別の枠と数えた場合の値です。実際は 1 が入るときに 7000 番地が最古として追い出されており、その時刻は 6000 番地の 3 の再参照より新しいため、7000 番地は最古の候補にはなりません。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成31年度 春期 応用情報技術者試験 午前 問19
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）