LRU 方式のページ置換
仮想記憶システムにおいて，主記憶のページ枠は 3 で，最初はすべて空いている。ページ参照列が 1，2，3，4，1，2，5，1，2，3，4，5 のとき，LRU 方式でページを置き換える場合のページフォールトの回数は何回か。
- ア7
- イ9
- ウ10
- エ12
正解と解説を見る
正解 ウ
この問題の基礎知識
- ページフォールトは，参照したページが主記憶上にないときに発生し，空きページ枠がなければいずれかのページを追い出して読み込む。最初の空き枠への読込みもフォールトに数える。
- LRU 方式は最後に参照されてから最も長い時間が経過したページを，FIFO 方式は最も早く主記憶に読み込まれたページを追い出す。
- OPT（最適）方式は，将来最も長く参照されないページを追い出す方式であり，フォールト回数は最小になるが，将来の参照を知る必要があるので比較の基準として扱われる。
- 置換方式の計算は，参照ごとにページ枠の内容と各ページの最終参照の順序を書き出してたどると誤りにくい。
ア7
将来最も長く参照されないページを置き換える最適（OPT）方式で置換した場合の回数である。LRU 方式では過去の参照履歴だけで置き換えるページを決める。
イ9
最も古く読み込まれたページを置き換える FIFO 方式で置換した場合の回数である。LRU 方式とは置き換えるページが異なる。
ウ10正解
最初の 7 参照（1，2，3，4，1，2，5）はすべてフォールトとなり，次の 1，2 はヒットする。続く 3，4，5 はいずれも主記憶になく，最も長く参照されていないページを追い出すのですべてフォールトとなり，合計 10 回である。
エ12
すべての参照でフォールトが発生した場合の回数である。8 番目と 9 番目の参照（1 と 2）は主記憶上にあるためヒットする。
検証用の出典一部照合
A. S. Tanenbaum, Modern Operating Systems照合の根拠（1 件）
- ウ（正解）: LRU と FIFO がページ置換方式であることの確認（方式の定義そのものは記載なし）
ページリプレースメント，LRU，FIFO，ワーキングセット
IPA 応用情報技術者試験シラバス Ver.7.2 · 3.1 仮想記憶（新しいタブで開きます）
シミュレーションの検算: LRU（3 枠）で 1,2,3,4,1,2,5 は全てフォールト（7 回），1,2 はヒット，3（5 を追出し），4（1 を追出し），5（2 を追出し）がフォールトで計 10 回。FIFO は 9 回，OPT は 7 回で各誤答肢の解説とも一致。ただし LRU・FIFO・OPT の定義を述べた読める一次資料が見つからず partial