フラグメンテーションとその解決法

通常の実行状態では命令セグメントは書き込み不可で良いが、新しいプログラムをメモリに書き込む場合には命令セグメントに書き込みを行うことが必要であり、書き込み不可では困る。

このため、OSは、新しいプログラムの命令セグメントはデータセグメントと同様に書き込み可能なセグメントとして生成し、命令データを書き込む。そして、そのセグメントの属性を書き込み不可、実行可能に変更してからユーザ状態に切り替えて実行を開始する。

これで基本的には、複数のプログラムをメモリ上に共存させ、プログラムの領域を超えたアクセスを防止し、さらに、バッファオーバフロー攻撃などの不正なメモリアクセスを防止できるようになった。

しかし、実用上は、まだ、問題がある。図5.1はA、B、C、Dの4つのプログラムがメモリ上に置かれている状態を示しているが、図5.3に示すように、プログラムの終了と新しいプログラムの開始が繰り返されると、空き領域が出来てしまう。

この図5.3の(1)の状態からプログラムBが終了すると、プログラムBが使用していたメモリは不要になる。次に実行すべきプログラムEが必要とするメモリが、プログラムBが使っていたメモリより大きい場合はプログラムBの終了に伴って開放されたメモリ領域には格納できず、プログラムDの領域の後に格納することになり、(2)のようにプログラムBが使用していたメモリ領域は空きとなる。

さらに、その次に開始するプログラムFが必要とするメモリがプログラムBの終了で出来た空き領域より少ない場合は、プログラムBが使用していたメモリ領域を再利用することが出来るが、(3)のように、プログラムFがプログラムBより小さい分のメモリは空きとなる。

このため、プログラムの終了と新しいプログラムの開始を繰り返すと、メモリ上に小さな空き領域が沢山できてしまう。このような状態をフラグメンテーション(Fragmentation)と呼び、空き領域の合計は大きくても、新たなプログラムを開始できないという状況となる。

ページ方式のメモリ管理

フラグメンテーションの問題を解決するには、OSがプログラムをコピーにより移動して空きを詰めるようにする手も考えられるが、大量のメモリのコピーには時間が掛かり、性能に悪影響が出る。

このため、最近のプロセサでは、ページという単位でメモリを管理する方式が一般的である。ページのサイズは典型的には8KBであるが、x86アーキテクチャでは過去の互換性の観点から4KBを使用している。

ページ方式のメモリ管理では、各プログラムごとに仮想メモリ空間をページ単位に分割し、各ページに対応する上位物理メモリアドレス、読み/書き/実行可能などの属性を記憶するテーブルを作る。

このテーブルを使って、ページ単位で仮想アドレスを物理アドレスに変換すれば、論理的なセグメントごとの空き領域は最大でもページサイズを超えることはない。32ビットアーキテクチャの場合は仮想アドレス空間のサイズは4GBであり、これを8KBのページ単位で管理する場合は、ページテーブルは0.5Mエントリが必要になる。各エントリのサイズを8バイトとすると、ページテーブルを格納するのに4MBのメモリが必要となるが、4GBのメモリ全体からみれば0.1%のオーバヘッドであり、フラグメンテーションによるロスに比べれば十分小さい値である。

しかし、メモリのアクセスごとに、メインメモリからページテーブルを読み出していたのでは、メモリアクセス回数が倍増してしまい性能が大幅にダウンしてしまう。このため、ページ方式では、ページテーブルの情報専用のキャッシュが用いられる。歴史的に、このキャッシュはTranslation Lookaside Buffer(TLB)と呼ばれる。

TLBの構造としては、エントリ数が少ない場合は上位仮想アドレス全体のマッチングを探すフルアソシアティブ方式が用いられる。また、エントリ数が多い場合は、セットアソシアティブ方式が用いられる。