BohYoh.com《基本情報技術者試験》2008年度＝平成20年度・春期午前問27

基本情報技術者試験

2008年度＝平成20年度・春期

午前

問27

　ページング方式の仮想記憶において、ページ置換えアルゴリズムにLRU方式を採用する。主記憶に割り当てられるページ枠が4のとき、ページ1、2、3、4、5、2、1、3、2、6の順にアクセスすると、ページ6をアクセスする時点で置き換えられるページは、どれか。ここで、初期状態では主記憶にどのページも存在しないものとする。

ア　1

イ　2

ウ　4

エ　5

解答

エ

解説

　仮想記憶管理におけるページ置換えアルゴリズムの一つであるLRU（least recently used）では、最後に使われてから最も時間が経過しているページを最初にページアウトします。すなわち、最も長い間参照されていないページをページアウトする方式です。
　どのようにページイン・ページアウトされるかを考えていきましょう。

　┌─┬─┬─┬─┐ 　│１│　│　│　│　１がページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│１│２│　│　│　２がページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│１│２│３│　│　３がページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│１│２│３│４│　４がページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│５│２│３│４│　１をページアウトして５をページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│５│２│３│４│　２を参照・更新　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│５│２│１│４│　３をページアウトして１をページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│５│２│１│３│　４をページアウトして３をページイン　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│５│２│１│３│　２を参照・更新　└─┴─┴─┴─┘ 　┌─┬─┬─┬─┐ 　│６│２│１│３│　５をページアウトして６をページイン　└─┴─┴─┴─┘

　以上から、最後に置きかえられる（ページアウトされる）のは５ページであることが分かります。