ページング方式 ページカラーリング

ウィキペディア

ページング方式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/15 03:44 UTC 版)

ページカラーリング

ページカラーリングの概念図

キャッシュメモリでのスラッシングを防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法をページカラーリングと呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。

キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー（色）が4種類存在すると称する。

物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。

ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにもかかわらず、特定のカラーの空きページがないためにページ置換アルゴリズムが起動してしまい性能低下するといった問題が発生する。これに対処する方法は様々である。

仮想インデックスキャッシュでは、ある物理ページが複数のプロセスに共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミス時に他のカラーの位置をチェックしてエイリアスがあればそれらのキャッシュラインを全てフラッシュして無効化する)。一時期のシステムでは、この性能低下が無視できないレベルであったため、OSがなるべくエイリアス問題を発生させないようにすることで性能低下を防ぐ必要があった。その際に使用されたのがページカラーリングである。ちなみにR4000では二次キャッシュと一次キャッシュの間の矛盾状態をエイリアス検出に利用していたため、二次キャッシュのないシステムではエイリアス状態を検出することすらできなかった(検出した場合も対処はOS任せである)。最近のシステムではキャッシュの性能向上によってペナルティが無視できるレベルになっているため、エイリアス問題への対策としてページカラーリングを行う必要性は小さくなっている。