平成27年度 春期 基本情報技術者試験 午前 問20
テクノロジ／ソフトウェアページング方式の仮想記憶において，ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき，ページ1，2，3，4，5，2，1，3，2，6の順にアクセスすると，ページ6をアクセスする時点で置き換えられるページはどれか。ここで，初期状態では主記憶にどのページも存在しないものとする。
出典：平成27年度 春期 基本情報技術者試験 午前 問20
- ア1
- イ2
- ウ4
- エ5
正解：エ
解説
LRU（Least Recently Used）方式は，最も長い間参照されていないページを置き換える方式です。ページ枠4でアクセス順1,2,3,4,5,2,1,3,2,6をたどると，ページ5をアクセスした時点で枠には[2,3,4,5]（1が追い出される）が入り，その後2,1,3,2とアクセスするうちに1が再ロードされて4が追い出され，枠は[5,2,1,3]になります（参照順は新しい順に2,3,1,5）。6をアクセスする時点で最も長く参照されていないのは5なので，5が置き換えられます。
選択肢ごとの解説
- ア誤り。ページ1は6をアクセスする直前（1,3,2の並びの中）で参照し直されているため，最も長く未参照というわけではありません。
- イ誤り。ページ2は6の直前にも参照されており，最も新しく使われたページなので置き換え対象にはなりません。
- ウ誤り。ページ4はページ5がロードされた時点（5番目のアクセス）で既に枠から追い出されており，6をアクセスする時点では枠に存在しません。
- エ正しい。ページ5は5番目のアクセス以降一度も参照されておらず，6をアクセスする時点で枠の中で最も長く未参照のページとなるため，LRU方式により置き換えられます。