平成24年度 秋期 基本情報技術者試験 午前 問19
テクノロジ／ソフトウェアページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。ここで，初期状態では主記憶にどのページも存在しないものとする。
出典：平成24年度 秋期 基本情報技術者試験 午前 問19
- ア1
- イ2
- ウ4
- エ5
正解：エ
解説
LRU方式は最も長く参照されていないページを置き換えます。ページ枠4でアクセス列1,2,3,4,5,2,1,3,2,6を追跡すると，5をロードした時点で page1 が追い出されて枠は[2,3,4,5]（古い順）。その後2がヒットして順序は[3,4,5,2]，1がミスして3を追い出し[4,5,2,1]，3がミスして4を追い出し[5,2,1,3]，2がヒットして[5,1,3,2]となります。6のアクセス時点で最も古い（最も長く未参照の）ページは5であり，5が置き換えられます。
選択肢ごとの解説
- ア誤り。1は5のロード時に一度追い出された後，その後のアクセス列で再ロードされて3を追い出しており，6の時点では主記憶に存在しています。
- イ誤り。2はその後も繰り返しヒットして参照されているため，最も長く未参照のページではありません。
- ウ誤り。4は3のミス時に追い出されており，6の時点では既に主記憶に存在しません。
- エ正しい。5をロードした後は一度も再参照されず，6がアクセスされる時点で最も長く参照されていないページとなるため置き換えられます。