ソフトウェア開発技術者平成19年秋期問25 LRU方式によるページ置換え

ソフトウェア開発技術者平成19年秋期午前問25

仮想記憶管理におけるページ置換えアルゴリズムとして，LRU方式を採用する。参照かつ更新されるページ番号が，1，2，3，4，1，2，5，1，2，3，6，5で，ページ枠が4のとき，ページフォールトに伴って発生するページアウトは何回か。ここで，初期状態では，いずれのページも読み込まれていないものとする。

テクノロジ系 » ソフトウェア » オペレーティングシステム

イ

置換えアルゴリズムとして使用されるLRU(Least Recently Used)は、置き換え対象の中で最後に参照されてからの時間が最も長いページを置き換え対象とするアルゴリズムです。

ページ枠の遷移を順に考えていきます。

最初の1から4までは空き領域にページインします。
1234
1は主記憶に存在するのでページアウトは発生しません。
1234
2は主記憶に存在するのでページアウトは発生しません。
1234
5は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは3なので、3をページアウトしその位置に5をページインします。(置換え1回目)
1254
1は主記憶に存在するのでページアウトは発生しません。
1254
2は主記憶に存在するのでページアウトは発生しません。
1254
3は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは4なので、4をページアウトしその位置に3をページインします。(置換え2回目)
1253
6は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは5なので、5をページアウトしその位置に6をページインします。(置換え3回目)
1263
5は主記憶に存在しないのでページ置換えが必要になります。この時点で最も昔に参照されたページは1なので、1をページアウトしその位置に5をページインします。(置換え4回目)
5263

したがってページアウトの回数は「4回」になります。