仮想記憶のページング方式

ページング方式の仮想記憶は、プログラムの仮想アドレス空間と主記憶を同じ大きさの固定長の単位に分けて管理する方式である。必要なページだけを主記憶に置き、参照されたときに不足するページを補うことで、主記憶を効率よく使いながら大きなプログラムを動かせる点に意義がある。

固定長ページによる断片化の扱い

ページング方式は、仮想記憶を固定長のページに分け、主記憶も同じ大きさのページ枠に分けて割り当てる。このため、セグメンテーション方式と比べると、主記憶の外部断片化が発生しないという長所がある。 一方で、最後のページに未使用の部分が生じることがあり、これは内部断片化として残る。固定長であることの利点と、ページ単位で切ることによる無駄の両方を理解しておく必要がある。

ページフォールトとページ置換えの仕組み

参照したページが主記憶上にないときに発生する例外をページフォールトという。ページフォールトが起きると、OSは必要なページを補助記憶から読み込み、必要に応じて既存のページを追い出す。

追い出すページの選び方として、ページ置換えアルゴリズムが用いられる。LRUは、最後に参照されてから最も長い時間が経過したページを置換対象とする方式である。 具体的な参照列に当てはめると、最後にページ4を参照する場面でページ3が最も長く参照されていないため、ページ3がいた枠へページ4が入る。

判断の基準と数値の計算

性能を評価するときは、ページフォールトの発生割合とそれにかかる処理時間を用いて、平均の処理時間を求める。ページインだけで済むフォールトの割合を未知数として平均の式を立てると、その割合を求められる。

主記憶アクセスの平均時間は、主記憶の1回のアクセス時間に、ページフォールト率とフォールト1回あたりのオーバヘッドの積を加えて求める。例えば、100万回に1回の割合で200ミリ秒のオーバヘッドが発生する場合、平均への寄与は200ナノ秒となる。この平均時間を基準に、改善策の効果を計算で比べる。