応用情報技術者 2019年春期午前2 問19

問題文

仮想記憶管理におけるページ置換えアルゴリズムとして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

🔒 解説は解答すると表示されます

LRUページ置換【午前2解説】

正解の理由

ページ参照列をLRU（Least Recently Used）方式で追跡すると、最後にページ4を参照した時点でページ4はメインメモリ内に存在しない状態になっており、ページ置換で空いた枠は元々ページ3が占めていた枠（6000）であるため、ページ4はアドレス6000にページインされます。したがって選択肢はウです。

解法ステップ

LRUでは「最も長く参照されていないページ」を追い出す。初期状態としてページ番号1〜4が各枠に以下のようにマップされている（16進表記）:

ページ1 → 4000
ページ2 → 5000
ページ3 → 6000
ページ4 → 7000

参照列：1 → 2 → 3 → 4 → 2 → 5 → 3 → 1 → 6 → 5 → 4

各参照ごとに「ヒットかミスか」「置換があればどれを追い出すか」「MRU（直近順）」を更新します。主要ステップを時刻 t1…t11 として示します。

t1: 1（ヒット／ロード済） → MRU: 1
t2: 2（ヒット） → MRU: 2,1
t3: 3（ヒット） → MRU: 3,2,1
t4: 4（ヒット） → MRU: 4,3,2,1
t5: 2（ヒット） → MRU: 2,4,3,1
t6: 5（ミス） → LRUはページ1（末尾）→ ページ1(4000)を追い出し、ページ5を4000にロード → MRU: 5,2,4,3
t7: 3（ヒット） → MRU: 3,5,2,4
t8: 1（ミス） → 直近順が 3(t7),5(t6),2(t5),4(t4) なので最古はページ4であり、7000 の枠を使ってページ1をロード → MRU: 1,3,5,2
- （ここは重要：t4で使われたページ4が最も古いため、その枠7000が再利用される）
t9: 6（ミス） → 現在のMRU 1,3,5,2 の末尾はページ2 → ページ2(5000)を追い出し、6を5000にロード → MRU: 6,1,3,5
t10: 5（ヒット） → MRU: 5,6,1,3
t11: 4（ミス） → 現在のMRU 5,6,1,3 の末尾はページ3 → ページ3(6000)を追い出し、4を6000にロード → MRU: 4,5,6,1

以上より、最後に参照したページ4はアドレス6000にページインされる。

（まとめ）ページ4は6000に置かれるため、選択肢ではウが正しい。

選択肢別の誤答解説

ア: 4000
誤り。4000は最初ページ1の枠だったが、t6でページ1が追い出されページ5が4000に入り、以降4000にはページ5が入ったまま（t8でページ1は7000枠に入る）。よって最後にページ4が入る枠ではない。
イ: 5000
誤り。5000は最終的にt9でページ6がロードされる枠である（ページ2が追い出された枠）。よってページ4は5000には入らない。
ウ: 6000
正解。t11でMRU順が 5,6,1,3 のため最も古いのはページ3(6000)であり、ページ3の枠を使ってページ4をロードする。したがってページ4は6000になる。
エ: 7000
誤り。7000はt8でページ4が追い出されていたため（そのときページ1が7000にロードされた）、以後7000にはページ1が存在する。よってページ4は7000には戻らない。

よくある誤解

LRUとFIFOを混同する
- FIFOは「最初に入れた順」を追い出す。LRUは「最も長く参照されていないもの」を追い出すため、同じ初期配置でも動作が異なる点に注意。
ヒット時にMRU順を更新し忘れる
- メモリ内参照（ヒット）でもそのページは「最も新しく使われた」としてMRUリストの先頭へ移動する。これを忘れると次の置換判断が誤る。
アドレス（枠）とページ番号を取り違える
- 問題は「ページがどの枠（アドレス）に入るか」を問うているため、ページ番号の追跡に加え、どの枠が空くか（古いページがどのアドレスに対応していたか）を正確に管理する必要がある。

補足コラム

LRUを厳密に実装するには各参照時にタイムスタンプを更新するか参照順のリストを維持する必要があり、オーバーヘッドが大きい。そのため実務では近似アルゴリズム（Clockアルゴリズムなど）がよく用いられます。
本問題では16進表記のアドレスが与えられているが、アルゴリズムの判断においては数値の大小ではなく「どのページがどの枠を占めているか」が重要です。

FAQ

Q. 同じページへの連続参照があるとどうなる？
A. 連続参照は最初の参照でヒット／ミス判定し、その後はヒットが続く。LRUでは各ヒットで当該ページがMRUへ移動するため、追い出されにくくなります。

Q. 「最古」の定義は？
A. LRUにおける「最古」は「最後に参照された時刻が最も古いページ」を指します（直近使用時刻が最も遠い）。直近順を並べた際の末尾が最古です。

Q. どの枠（アドレス）を使うかはどう決まる？
A. 追い出されるページが占めていた枠（そのページに対応するアドレス）を再利用します。例えばページ3が追い出されれば、その枠（ここでは6000）が空いて新しいページが入ります。

関連キーワード: 仮想記憶, ページ置換, LRU, ページフォルト, クロックアルゴリズム

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！