BohYoh.com《ソフトウェア開発技術者試験》2002年度＝平成14年度午前問25

ソフトウェア開発技術者試験

2002年度＝平成14年度

午前

問25

　プログラムで使用可能な実メモリ枠が3ぺージである仮想記憶システムにおいて、大きさ6ぺージのプログラムが実行されたとき、ぺージフォールトは何回発生するか。ここで、プログラム実行時のぺージ読込み順序は、0、1、2、3、4、0、2、4、3、1、4、5とする。ぺージング方式は、LRU（Least Recently Used）とし、初期状態では、実メモリにはいずれのぺージも読み込まれていないものとする。

ア　9

イ　10

ウ　11

エ　12

解答

ア

解説

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

ページフォールト発生（必要とするページが実メモリ枠に存在しない）　↓ 　　　┌─┬─┬─┐ 　○　│０│　│　│　０をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│０│１│　│　１をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│０│１│２│　２をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│３│１│２│　０をページアウトして３をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│３│４│２│　１をページアウトして４をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│３│４│０│　２をページアウトして０をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│２│４│０│　３をページアウトして２をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　　　│２│４│０│　４を参照・更新　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│２│４│３│　０をページアウトして３をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│１│４│３│　２をページアウトして１をページイン　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　　　│２│４│０│　４を参照・更新　　　└─┴─┴─┘ 　　　┌─┬─┬─┐ 　○　│２│４│５│　０をページアウトして５をページイン　　　└─┴─┴─┘

　以上から、ページフォールトが発生するのは10回であることが分かります。