令和4年度 I-2-3

解説

この問題で問われていること

主記憶に格納できるページ数が3のLRU方式の仮想記憶において、ページ参照列2→1→1→2→3→4→1→3→4に対する総アクセス時間を、主記憶アクセス時間H・外部記憶アクセス時間Mを用いて求める問題。

解き方

① LRU: 満杯のときは、最も長く使われていないページを追い出す。主記憶にあればH、なければM
② 2(M)→1(M)→1(H)→2(H)→3(M)→4(M、1を追い出し)→1(M、2を追い出し)→3(H)→4(H) → M5回、H4回
③ 5M+4H(③)

正解が正しい理由

参照列を順に主記憶の状態(LRU順)を追跡すると、2(外部記憶,主記憶={2})、1(外部記憶,{2,1})、1(主記憶,ヒット)、2(主記憶,ヒット)、3(外部記憶,{1,2,3})、4(外部記憶,LRUの1を追い出し{2,3,4})、1(外部記憶,LRUの2を追い出し{3,4,1})、3(主記憶,ヒット)、4(主記憶,ヒット)となる。外部記憶からのアクセス(ミス)は2,1,3,4,1の5回、主記憶からのアクセス(ヒット)は1,2,3,4の4回であるため、総アクセス時間は5M+4Hとなる。したがって③が正しい。

各選択肢について

• ① 7M+2Hは、ミスとヒットの回数を正しく数え上げた結果(5回・4回)と一致しない。
• ② 6M+3Hも、正しいミス・ヒットの回数(5回・4回)とは一致しない。
• ③ 参照列をLRU方式で1つずつ追跡した結果、ミス(外部記憶アクセス)が5回、ヒット(主記憶アクセス)が4回となり、総アクセス時間5M+4Hと一致しており、これが正答。
• ④ 4M+5Hは、ミスとヒットの回数が実際の追跡結果(5回・4回)と逆になっている。
• ⑤ 3M+6Hも、ミスとヒットの回数が実際の追跡結果と一致しない。

覚えるべきポイント

LRU方式では、主記憶が満杯のときに新しいページへアクセス(ミス)すると、最も長くアクセスされていないページ(最近使われていない順で末尾)を追い出す。ページ参照列を1つずつ丁寧に追跡し、各参照がヒット(主記憶,H)かミス(外部記憶,M)かを正確に数え上げることが重要である。