平成27年度 春期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問8

解説

LRU（Least Recently Used）方式は，最も長く参照されていないページを置換え対象とするアルゴリズムです。主記憶のページ枠が3で初期状態が空の場合，参照順序 1，2，3，2，3，1，4，2，4，3，1 について，最初の1，2，3の参照はページ枠に空きがあるため必ずページフォールト（読込み）が発生し，3回のフォールトで枠が {1，2，3} で埋まります。続く2，3，1の参照はいずれも既に枠内にあるためヒットし，参照順に最も新しい順序が 1，3，2 という利用順（1が最新）に更新されます。次の4の参照は枠にないためフォールトとなり，最も長く使われていない2が追い出されて枠は {1，3，4} になります（4回目のフォールト）。続く2の参照も枠にないためフォールトとなり，最も長く使われていない3が追い出されて枠は {1，4，2} になります（5回目）。次の4の参照はヒットします。続く3の参照は枠にないためフォールトとなり，最も長く使われていない1が追い出されて枠は {4，2，3} になります（6回目）。最後の1の参照も枠にないためフォールトとなり，最も長く使われていない2が追い出されます（7回目）。したがって，ページの読込みは合計7回発生します。

選択肢ごとの解説

• ア誤り。4回は，最初の1，2，3の参照によるページフォールトの回数だけであり，その後の4，2，3，1の参照で発生する追加のフォールトが考慮されていません。
• イ誤り。5回は，途中までのページフォールトの回数であり，最後まで参照順序をたどると，更にフォールトが発生するため，総数としては不足しています。
• ウ誤り。6回は，最後の1の参照で発生するフォールトが考慮されておらず，総数としては一つ少ない値です。
• エ正しい。参照順序全体をLRU方式でたどると，1，2，3，4，2，3，1の参照時にそれぞれページフォールトが発生し，合計7回のページの読込みが発生します。