【システム構成】キャッシュを爆速にする自然の法則!「局所性の原理」|情報処理問題1000本ノック
コンピュータのメモリやキャッシュが驚異的なヒット率を叩き出せる理由。プログラムが持つデータの「偏り」の性質である「局所性」を攻略しましょう。
1. 【 問題 】:プログラムのアクセス特性と局所性
【 問題 】 コンピュータのCPUがメモリ上のデータや命令にアクセスする際、アクセスされる領域が時間的、または空間的に特定の部分に集中しやすいという性質を「局所性の原理(Principle of Locality)」と呼びます。このうち、「一度アクセスされたデータや命令は、近い将来(短い時間の間)に再びアクセスされる確率が非常に高い」という性質を表す言葉として、最も適切なものはどれでしょうか?
① 空間的局所性 (Spatial Locality)
② 時間的局所性 (Temporal Locality)
③ 順次局所性 (Sequential Locality)
④ 構造的局所性 (Structural Locality)
2. 正解:
正解: ② 時間的局所性(Temporal Locality)
3. 解説:「時間」の偏りと「場所」の偏りの2大巨頭
局所性の原理には、午前試験で対比されて出題される2つの重要な側面があります。今回の正解である時間的局所性と、もう1つの空間的局所性です。
・② 時間的局所性(時間的な偏り):「さっき使ったデータ(命令)は、すぐまた使う」という性質です。プログラムの『ループ処理(for文やwhile文)』の中で何度も繰り返し使われるカウンタ変数や、同じ命令の塊などがこれに該当します。 ← ココが問題の正解!
・① 空間的局所性(場所的な偏り):「あるデータにアクセスしたら、そのすぐ近くの番地にあるデータも続けて使う」という性質です。配列データを先頭から順番に処理していく場合や、関連する命令がメモリ上に並んでいる(ステップ順に実行される)場合がこれに該当します。
★ 時間的局所性の応用:一度読み込んだデータを高速なキャッシュメモリやデータベースバッファ(メモリ)に残しておけば、2回目以降のアクセスを劇的に速くできます。
★ 空間的局所性の応用:直前の問題で学んだDBMSの「ページ管理」のように、1箇所データが必要になったら、周辺のデータごと「塊(ページやブロック)」でまとめてメモリに持ってきておくことで、後からディスクを何度も読み直す無駄を省けます。
1. 理解のコツ: 「仕事のデスクワーク」に例えてみましょう。
・さっきまで使っていた「ハサミ」や「辞書」を、片付けずにデスクの特等席(キャッシュ)に置いておけば、数分後にまた使うとき(時間的局所性)に一瞬で手に取れますよね。これが時間的局所性です。
・また、本棚から「1巻」を取り出したなら、次は隣にある「2巻」や「3巻」を使う可能性が高い(空間的局所性)ため、あらかじめシリーズごとまとめて机に持ってきておく。これが空間的局所性です。
2. 試験対策の視点: 「最近利用したデータや命令を再度利用する確率が高い」=時間的局所性、「一度アクセスしたデータの近くが使われやすい」=空間的局所性、という2つの違いを正確にハサミと本棚のイメージで区別できるようにしてください。ITパスポートから基本情報、応用情報の午前試験において、キャッシュメモリのヒット率の計算問題や、OSの仮想記憶(ページング)、DBMSのパフォーマンス向上を説明するすべての「大前提の自然法則」として超頻出する重要理論です。
4. まとめ
「プログラムの動きには強い偏りがあり、最近触ったデータ(時間的局所性)や、その周辺のデータ(空間的局所性)が何度も集中して使われるという性質」。これが局所性の原理です。コンピュータが1秒間に何億回もの処理をこなせるのは、この局所性を見抜いた天才たちが、ハードウェアやDBMSの内部に「先回りしてデータを置いておく仕組み(キャッシュ)」を組み込んでくれたおかげです。