問題プレビューID: bfc37937

問 20

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

解説

LRU方式（Least Recently Used）は、最も長い間参照されていないページを置き換え対象にするアルゴリズムです。

ページ枠 4 つの変遷を追います（左側ほど最近使われたものとします）。

ページ 1 アクセス：[1, -, -, -]
ページ 2 アクセス：[2, 1, -, -]
ページ 3 アクセス：[3, 2, 1, -]
ページ 4 アクセス：[4, 3, 2, 1]
ページ 5 アクセス：[5, 4, 3, 2] （ページ 1 を追い出す。1 が最も古いため）
ページ 2 アクセス：[2, 5, 4, 3] （ページ 2 は存在するので、順序を最新にする）
ページ 1 アクセス：[1, 2, 5, 4] （ページ 3 を追い出す。3 が最も古いため）
ページ 3 アクセス：[3, 1, 2, 5] （ページ 4 を追い出す。4 が最も古するため）
ページ 2 アクセス：[2, 3, 1, 5] （ページ 2 は存在するので、順序を最新にする）
ページ 6 アクセス：

この時点で、最も古く（右端）にあるのはページ 5 です。したがって、ページ 6 を読み込むためにページ 5 が置き換えられます。

正解は「エ」です。