エンベデッドシステムスペシャリスト 2019年午前2 問10

問題文

ページング方式の仮想記憶において、ページ置換えアルゴリズムにLRU方式を採用した場合、ページの参照順序が

1, 2, 3, 2, 3, 1, 4, 2, 4, 3, 1

であるプログラムを実行するとき、ページの読込みは何回発生するか。ここで、主記憶のページ枠は3で、初期状態では主記憶にどのページも存在しないものとする。

🖊️ 解答を隠して解いてみる

ア：4

イ：5

ウ：6

エ：7（正解）

🔒 解説は解答すると表示されます

ページ枠が3個で、最初は主記憶にページがありません。したがって、最初に参照するページ1、2、3はすべて読み込みが発生します。

その後、主記憶にないページを参照したときは、LRU方式に従って「最も長い間使われていないページ」を置き換えます。ページ読み込みが発生する回数は、最初の3回に加えて、ページ4、2、3、1を参照したときの4回です。合計は7回なので、該当する選択肢はエです。

表の「使用順」は、参照後のページを「古い順 → 新しい順」に並べたものです。ページが主記憶にない場合は読み込みが発生し、枠が埋まっていれば最も古いページを置き換えます。

参照ページ	結果	置換え	使用順（古い順 → 新しい順）
1	読み込み	なし	1
2	読み込み	なし	1, 2
3	読み込み	なし	1, 2, 3
2	読み込みなし	なし	1, 3, 2
3	読み込みなし	なし	1, 2, 3
1	読み込みなし	なし	2, 3, 1
4	読み込み	2を置換え	3, 1, 4
2	読み込み	3を置換え	1, 4, 2
4	読み込みなし	なし	1, 2, 4
3	読み込み	1を置換え	2, 4, 3
1	読み込み	2を置換え	4, 3, 1

読み込みが発生した参照は、1、2、3、4、2、3、1の7回です。

ア：4
最初の3ページの読み込みを数えず、枠が埋まった後の置換え時だけを数えた場合に起こりやすい誤りです。最初のページ参照でも読み込みは発生します。
イ：5
ページを参照しても、すでに主記憶にあれば読み込みは発生しません。参照のたびに使用時刻を更新しないなど、LRUの扱いを誤ると、読み込み回数を少なく数えることがあります。
ウ：6
主記憶に存在しないページを参照したときの読み込みを1回数え落とした可能性があります。置換えが発生する場面だけでなく、最初の3ページの読み込みも含めて数えます。
エ：7
最初の3回の読み込みと、その後のページ4、2、3、1の読み込みを合わせた回数です。

LRUは「Least Recently Used」の略で、最も長い間参照されていないページを置き換える方式です。FIFO方式のように「主記憶に入ってから最も時間がたったページ」を選ぶのではありません。ページを再参照したら、そのページを「最近使った」として扱う点が違いです。

Q. ページ読み込みは、ページフォールトが起きた回数と同じですか？
A. この問題のように、主記憶にないページを読み込む回数を問う場合は、ページフォールトが発生した回数と同じように数えられます。

Q. LRU方式では、ページを参照するたびに置換えが起きますか？
A. いいえ。参照したページがすでに主記憶にあれば、置換えも読み込みも発生しません。

関連キーワード: LRU、ページ置換え、ページング方式、仮想記憶、ページフォールト

\ せっかくなら /

エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？

すぐに利用可能！