仮想記憶管理におけるページ置換えアルゴリズムとして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は最後に参照されてから最も時間が経ったページを追い出す。初期状態は4000＝1、5000＝2、6000＝3、7000＝4である。5の参照で最も古い1（4000番地）が置き換わり、次の1の参照で4（7000番地）が、6の参照で2（5000番地）が置き換わる。最後の4の参照時に最も古いのは3（6000番地）なので、ページ4は6000番地にページインされる。

選択肢ごとの解説

• ア4000番地は5の参照で置き換わり、その後10番目の5の参照でヒットしているため最も新しい部類である。
• イ5000番地は9番目の6の参照で置き換わったばかりで、追い出し対象にならない。
• ウ正解。6000番地のページ3は7番目に参照されて以降使われておらず最も古いので、ここに4がページインされる。
• エ7000番地は8番目の1の参照で置き換わっており、6000番地より新しい。

この問題に出た用語

• 仮想記憶
• LRU（Least Recently Used）
• 16進数

同じ分野の他の問題

• 手続型言語のコンパイラがコード生成までに行う処理のうち、最後に行うものはどれか。2024年度 秋期 問7
• 仮想記憶方式において、セグメンテーション方式と比較した場合のページング方式の長所はどれか。2024年度 秋期 問6
• 三つの資源X〜Zを占有して処理を行う四つのプロセスA〜Dがある。各プロセスは処理の進行に伴い、表中の数値の順に資源を占有…2024年度 春期 問6
• プリエンプティブな優先度ベースのスケジューリングで実行する二つの周期タスクA及びBがある。タスクBが周期内に処理を完了で…2023年度 秋期 問6
• 二つのタスクが共用する二つの資源を排他的に使用するとき、デッドロックが発生するおそれがある。このデッドロックの発生を防ぐ…2019年度 春期 問6