基本情報技術者試験「ページ置換アルゴリズム」の問題
ページ枠が3つあり最初は全て空である。ページ参照が 4,3,2,1,3,5,2,1,3 の順で発生したとき、LRU(最も長く参照されていないページを置換)方式を適用すると、発生するページフォルトは合計何回か。
ア6回となる
イフォルトは8回である
ウ全部で7回
エ9回すべてがフォルト
正解
イ．フォルトは8回である
LRUは最後に参照された時刻が最も古いページを追い出す。順に追うと4F3F2F、1で最古4を追出F、3はヒット、5で最古2を追出F、2で最古1を追出F、1で最古5を追出F、3で最古2を追出F。ヒットは1回のみでフォルトは8回となり正しい。
?選択肢ごとの解説
ア ×6回は5・2・1・3の終盤で連続する置換フォルトの一部を数え漏らした過少な値である。
イ ○LRUは最後に参照された時刻が最も古いページを追い出す。順に追うと4F3F2F、1で最古4を追出F、3はヒット、5で最古2を追出F、2で最古1を追出F、1で最古5を追出F、3で最古2を追出F。ヒットは1回のみでフォルトは8回となり正しい。
ウ ×全部で7回は終盤の置換のうち1回を数え落とした誤りで、各参照で最古ページを正しく更新できていない。
エ ×9回すべてがフォルトは5回目の参照3がヒットすることを見落とし、全てミスと数えた誤りである。
✎くわしく
LRUは参照局所性に基づき『最近使われていないものは今後も使われにくい』と仮定して追い出す。各ページの最終参照時刻を管理する必要があり、FIFOより性能は良いが管理コストが高い。本問はヒットが1回のみで、参照列に局所性が乏しいとLRUでもフォルトが多発する例である。
✓本番での押さえどころ
試験のコツ
枠ごとに最終参照位置を記録し、フォルト時は最も古い位置のページを追い出す。ヒットでも必ず最終参照を更新する。
覚え方
LRU=Least Recently Used=『最近いちばんご無沙汰』のページから退場、と直訳で覚える。
よくある誤り
追い出す基準を『入った順』(FIFO)と取り違える、ヒットのたびに最終参照時刻を更新し忘れて古いものを誤判定する間違いが多い。
コンピュータ構成要素の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0162