応用情報技術者 2012年秋期午前2 問19

問題文

仮想記憶管理におけるページ置換えアルゴリズムとして、LRU 方式を採用する。参照かつ更新されるページ番号の順番が、1,2,3,4,1,2,5,1,2,3,65でページ枠が 4のとき、ページフォールトに伴って発生するページアウトは何回か。ここで、初期状態では、いずれのページも読み込まれていないものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：3

イ：4（正解）

ウ：5

エ：6

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

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

正解の理由

選択肢の中で試験の「正答」とされるのはイ（4回）です。LRU（最長未使用）方式では、ページ枠が満杯のときに最も長く参照されていないページを退避（置換）します。問題文の「参照かつ更新される」ため、置換されたページはすべてディスクへ書き戻される（＝ページアウト）とみなします。本問で公式解答が 4 とされるのは、与えられた参照列の末尾表記「65」を「6, 5」（二つの別ページ参照）と読む（＝元の出題意図）ときに、LRU による置換（＝ページアウト）が 4 回発生するためです。なお、もし「65」を単一ページ番号 65 と読むと、LRU の通常の追跡ではページアウトは 3 回になります（この点が以前の解説でのズレの原因です）。

解法ステップ

まず出題意図に合わせ「65」を「6, 5」と解釈した場合の逐次追跡を示します（ページ枠＝4、初期は空、各参照は参照かつ更新）。

参照列（解釈）: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 5

フレームの状態と置換（LRU：左が最も古い＝置換候補）を時系列で示します。
（空欄は未使用）

1 → [1, -, -, -]（フォールト、置換なし）
2 → [1, 2, -, -]（フォールト、置換なし）
3 → [1, 2, 3, -]（フォールト、置換なし）
4 → [1, 2, 3, 4]（フォールト、置換なし）
1 → [2, 3, 4, 1]（ヒット、LRU 更新）
2 → [3, 4, 1, 2]（ヒット、LRU 更新）
5 → [4, 1, 2, 5]（フォールト、LRU = 3 を退避 → ページアウト 1回）
1 → [4, 2, 5, 1]（ヒット、LRU 更新）
2 → [4, 5, 1, 2]（ヒット、LRU 更新）
3 → [5, 1, 2, 3]（フォールト、LRU = 4 を退避 → ページアウト 2回）
6 → [1, 2, 3, 6]（フォールト、LRU = 5 を退避 → ページアウト 3回）
5 → [2, 3, 6, 5]（フォールト、LRU = 1 を退避 → ページアウト 4回）

以上より置換（書き戻し＝ページアウト）は合計 4 回、よってイ（4回）が正答となります。

補足として、本問の記述どおり「65」を単一ページ 65 と読み替えると参照列は 11 回になり、同じ LRU 追跡を行うとページアウトは 3 回になります。問題文の表記揺れ（65＝「6,5」か「65」か）が、以前の解説と正答の不一致の原因でした。

選択肢別の誤答解説

ア: 3 — 「65」を単一ページ 65 と解釈した場合はページアウト 3 回となるため、この値が出る計算はあり得るが、試験の正答（イ）は 4。出題意図が末尾を 6,5 と読む場合は誤り。
イ: 4 — 出題意図どおり末尾を 6,5 と読み、LRU を正しく適用すると置換（ページアウト）は 4 回になるため正しい。
ウ: 5 — 置換回数 5 を得るには参照の読み違いや LRU の更新忘れなど誤った手順が必要（例えばヒットで LRU を更新しない等）。
エ: 6 — 同様に過剰な置換回数。初期フレームを空とするという条件を無視している可能性が高い。

よくある誤解

「ページフォールト」と「ページアウト（ページ書き戻し）」を混同する：ページフォールトはページが見つからない事象、ページアウトは置換時に更新済みページを書き戻す動作。ページフォールトの回数はページアウトより大きくなることが多い。
「ヒット時にLRUの更新を忘れる」：ヒットしてもそのページは最も最近使用された扱いに更新する必要があり、これを忘れると置換対象が変わり誤答になる。
問題文の表記解釈ミス：今回のように "65" が「6,5」か「65」かで答えが変わることがあるため、参照列の区切り・表記はよく確認する。

補足コラム

一般的に、すべての参照ページが「参照かつ更新される」場合、ページアウト回数は「ページフォールト回数 − 初期空き枠数」と表現できます。すなわち初期の空き枠に入る分は書き戻しが発生しないため差し引きます。記号で表すと、ページアウト回数 = max(0, フォールト数 − F)（ただし F は枠数、初期が空の場合）。本問（「6,5」と読む場合）はフォールト数が 8 で枠数 4 のため置換は 8−4＝4 となります。
LRU の追跡は「各ページの最終参照時刻」を記録する方法、またはスタックアルゴリズム（参照のたびにページをトップに移動）で実装可能です。

FAQ

Q1: 「ページアウト」とは具体的に何を数えるのですか？
A1: 本問では「参照かつ更新される」ため、置換時に退避されるページは全て書き戻される（＝ページアウト）と見なします。したがってページアウト回数＝置換回数です。

Q2: ヒットしたページは LRU の位置を更新しますか？
A2: はい。LRU ではヒット時にもそのページを「最新使用」に更新します。これを忘れると置換対象が変わります。

Q3: 問題の表記が曖昧（例：65）な場合どう判断すべきですか？
A3: 出題の文脈（選択肢や想定解）と矛盾がないかをまず確認します。今回のように公式解答が示す値と自分の計算が異なる場合、参照列の区切りや表記ミスの可能性を検討し、両方の解釈を短く検算して整合する方を採るのが実務的です。

関連キーワード: 仮想記憶、ページ置換、LRU、ページアウト、ページフォールト

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！