エンベデッドシステムスペシャリスト 2015年 午前2 問08

ページ置換えのLRU方式【午前2解説】

正解の理由

解法ステップ

1. 最初に参照するページ1、2、3は、主記憶に存在しないため、それぞれ読込みます。
2. その後の2、3、1は主記憶にあるため、読込みは発生しません。
3. ページ4を参照すると、ページ枠が満杯です。ページ1、2、3のうち、最後に参照された時点が最も古いページ2を置き換えます。
4. 次のページ2、ページ3、ページ1も順に主記憶にないため、それぞれ読込みます。
5. 読込みが発生した回数を数えると、合計7回です。

選択肢別の誤答解説

• ア：4
  ページ枠が満杯になった後の置換えを正しく数えられていない可能性があります。ページ4以降も、主記憶に存在しないページを参照するたびに読込みが発生します。
• イ：5
  置き換えたページが後で再び参照されると、そのページをもう一度読み込む必要があります。ページ2、3、1の再読込みをすべて数える必要があります。
• ウ：6
  置換え時にLRUの対象ページを誤ると、後続の参照で主記憶にないページを見落とすことがあります。各参照のたびに、最も古く参照されたページを確認します。
• エ：7
  読込みが発生する参照は、ページ1、2、3、4、2、3、1です。合計7回となるため、正しい選択肢です。

よくある誤解

• ページ枠から追い出されたページは、再参照されても読込み不要だと思う
  追い出されたページは主記憶に存在しないため、再び参照されたときには読込みが発生します。
• LRUを、最も長く主記憶に置かれているページを追い出す方式だと考える
  判断基準は主記憶に入った時刻ではなく、最後に参照された時刻です。
• 主記憶にあるページへの参照も読込みとして数える
  主記憶に存在するページへの参照はヒットであり、ページの読込みは発生しません。

補足コラム

FAQ