2.2メモリと記憶階層

キャッシュメモリと仮想記憶の「仕組み」を知っているだけでは応用情報の午前問題には対応できません。ヒット率が変化したときに実効アクセス時間がどれだけ変わるか、限られた主記憶枠でどのページを追い出すべきかといった、数値・手順を伴う判断まで踏み込んで理解しておく必要があります。

2.2.1実効アクセス時間とヒット率の計算

• 実効アクセス時間＝キャッシュ時間×ヒット率＋主記憶時間×(1−ヒット率)の加重平均で求めます。この式が示す通り、実効アクセス時間を短縮する手段は、キャッシュ自体を高速化することだけでなく、ヒット率を高めることでも同じ効果が得られます。実務では、キャッシュ容量の増設やアクセスパターンの局所性（参照の局所性）を活かした設計でヒット率を高める工夫が行われます。
• 近年のプロセッサはL1／L2／L3のように複数段のキャッシュを持つのが一般的です。CPUに最も近いL1が最速・最小容量、L3が最も低速・大容量という構成で、記憶階層の原則がキャッシュ内部にも適用されています。多段キャッシュでは、まずL1を探し、なければL2、それでもなければL3、最後に主記憶という順にアクセスするため、全体の実効アクセス時間は各段のヒット率を考慮した多段の加重平均になります。

2.2.2ライトスルーとライトバックの深掘り

ヒット率の変化が実効アクセス時間へどれだけ効くかを、具体的な数値で確認しましょう。キャッシュのアクセス時間が5ナノ秒、主記憶のアクセス時間が60ナノ秒のシステムで、ヒット率が95%（0.95）の場合、実効アクセス時間＝5×0.95＋60×0.05＝4.75＋3＝7.75ナノ秒です。ここでヒット率をわずか3ポイント改善して98%（0.98）にできると、実効アクセス時間＝5×0.98＋60×0.02＝4.9＋1.2＝6.1ナノ秒へ短縮されます。ヒット率をたった3ポイント上げただけで実効アクセス時間が約21%（(7.75−6.1)÷7.75）も改善する計算になり、キャッシュ自体を高速な部品に交換するより、ヒット率を高める設計（容量増設やアクセス局所性を活かした配置）の方が費用対効果が高い場合が多いことが読み取れます。次にページ置換アルゴリズムを見ていきます。仮想記憶で主記憶に格納できるページ数に限りがあるとき、新しいページを読み込むために既存のどれかのページを追い出す必要があり、その選び方がページ置換アルゴリズムです。LRU（Least Recently Used）は、最も長い間参照されていないページを追い出す方式で、直近の参照履歴が今後の利用を予測する良い手がかりになるという経験則（参照の局所性）に基づいており、実務で広く使われます。FIFO（First-In First-Out）は、単純に最も先に主記憶へ読み込まれたページを追い出す方式で、実装は単純ですが、頻繁に使われ続けているページでも古いという理由だけで追い出されてしまう弱点があります。ページ置換の判断を誤り、必要なページが直後に再び必要になって読み込み直しが頻発すると、スラッシング（FE/SGで学んだ通り、ページ入れ替えが頻発し処理効率が著しく低下する現象）を招きやすくなるため、ワークロードの参照パターンに応じたアルゴリズム選択が重要になります。

2.2.3この節のまとめ

• 実効アクセス時間＝キャッシュ時間×ヒット率＋主記憶時間×(1−ヒット率)。ヒット率のわずかな改善が実効アクセス時間を大きく縮める
• ライトスルー＝同時書き込み・信頼性重視／ライトバック＝キャッシュのみ書き込み・速度重視だが一時不一致。近年はL1/L2/L3の多段キャッシュが一般的
• LRU＝最も長く未参照のページを置換（参照の局所性が根拠）・FIFO＝最も先に入ったページを置換（頻度を考慮しない）。誤った置換選択はスラッシングを招く