LRU（Least Recently Used）ページ置換えアルゴリズムのページフォールト回数追跡

LRU（Least Recently Used）方式 は、主記憶上のページ枠が満杯になったときに「最も長い間参照されていないページ」を追い出して新たなページをロードする方式です。ページ枠数3での参照履歴をステップごとに追跡します（右側を最新参照とします）： 1. 参照 1 : [1] 読込み（1回目） 2. 参照 2 : [1, 2] 読込み（2回目） 3. 参照 3 : [1, 2, 3] 読込み（3回目） 4. 参照 2 : [1, 3, 2] ヒット 5. 参照 3 : [1, 2, 3] ヒット 6. 参照 1 : [2, 3, 1] ヒット 7. 参照 4 : 最古の 2 を追い出し [3, 1, 4] 読込み（4回目） 8. 参照 2 : 最古の 3 を追い出し [1, 4, 2] 読込み（5回目） 9. 参照 4 : [1, 2, 4] ヒット 10. 参照 3 : 最古の 1 を追い出し [2, 4, 3] 読込み（6回目） 11. 参照 1 : 最古の 2 を追い出し [4, 3, 1] 読込み（7回目） 以上より、ページの読込みは合計 7回 発生します。したがって、正解は エ です。 ア: 4回は、ユニークなページ種類数（1, 2, 3, 4の4種類）を誤認した値です。 イ: 5回は、ページ参照の局所性を誤って追跡した計算値です。 ウ: 6回は、最終ステップでの参照1の読込みをカウントし忘れた誤りです。

ページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用した場合，ページの参照順序が 1, 2, 3, 2, 3, 1, 4, 2, 4, 3, 1 であるプログラムを実行するとき，ページの読込みは何回発生するか。ここで，主記憶のページ枠は3で，初期状態では主記憶にどのページも存在しないものとする。

出典平成31年度 春期 エンベデッドシステムスペシャリスト試験 午前Ⅱ 問10
ア
4
イ
5
ウ
6
エ
7