修了試験 2011-06-26実施分 基本情報技術者試験 問24

解説

正解は4です。 この問題は、ページ置換えアルゴリズムのLRU（Least Recently Used）方式の動きをたどる問題です。 LRU方式では、最後に参照されてから最も長い時間が経ったページを追い出します。 【計算】 ページ1，2，3，4の参照で、ページ枠4つが埋まります。 ページ5の参照では、最も古く参照された1を追い出し、主記憶は2，3，4，5になります。 ページ2の参照は、主記憶にあるのでそのまま使います。 ページ1の参照では、最後の参照が最も古い3を追い出し、主記憶は4，5，2，1になります。 ページ3の参照では、最後の参照が最も古い4を追い出し、主記憶は5，2，1，3になります。 ページ2の参照は、主記憶にあるのでそのまま使います。 ページ6の参照時点で、最後の参照が古い順に5，1，3，2なので、5が置き換えられます。 【選択肢別解説】 1：× ページ1は7番目に参照されており、5より新しく使われています。 そのため追い出されません。 2：× ページ2は直前の9番目に参照されたばかりで、最も新しいページです。 そのため追い出されません。 3：× ページ4は、8番目のページ3の参照のときにすでに追い出されています。 ページ6の時点では主記憶にありません。 4：○ ページ6の参照時点では、主記憶の中でページ5の最終参照（5番目）が最も古いので、5が置き換えられます。 【ポイント】 LRUは「最後に使った時刻」で判断し、FIFOは「主記憶に入った時刻」で判断します。 途中で参照されたページは最終参照時刻が更新される点に注意します。