仮想記憶のページ置換手法としてLRU（Least Recently Used）が使われており，主記憶に格納できるページ数が3，ページの主記憶からのアクセス時間がH［秒］，外部記憶からのアクセス時間がM［秒］であるとする（HはMよりはるかに小さいものとする）。ここでLRUとは最も長くアクセスされなかったページを置換対象とする方式である。仮想記憶にページが何も格納されていない状態から開始し，プログラムが次の順番でページ番号を参照する場合の総アクセス時間として，適切なものはどれか。
2⇒1⇒1⇒2⇒3⇒4⇒1⇒3⇒4
なお，主記憶のページ数が1であり，2⇒2⇒1⇒2の順番でページ番号を参照する場合，最初のページ2へのアクセスは外部記憶からのアクセスとなり，同時に主記憶にページ2が格納される。以降のページ2，ページ1ページ2への参照はそれぞれ主記憶，外部記憶，外部記憶からのアクセスとなるので，総アクセス時間は3M+1H［秒］となる。
① 7M+2H［秒］
② 6M+3H［秒］
③ 5M+4H［秒］
④ 4M+5H［秒］
⑤ 3M+6H［秒］
解答
③
解説
2⇒1⇒1⇒2⇒3⇒4⇒1⇒3⇒4 におけるそれぞれの段階のアクセス時間および主記憶のページの状態{X, X, X}は次の通りです。
- 2：外部記憶へアクセス（M秒） {2, -, -}
- 1：外部記憶へアクセス（M秒） {1, 2, -}
- 1：主記憶へアクセス（H秒） {1, 2, -}
- 2：主記憶へアクセス（H秒） {2, 1, -}
- 3：外部記憶へアクセス（M秒）{3, 2, 1}
- 4：外部記憶へアクセス（M秒）{4, 3, 2}
- 1：外部記憶へアクセス（M秒）{1, 4, 3}
- 3：主記憶へアクセス（H秒） {3, 1, 4}
- 4：主記憶へアクセス（H秒） {4, 3, 1}
これらのアクセス時間を全て足すと，5M+4H［秒］です。
過去の出題
なし
