malloc() + free() による動的メモリの管理方法について説明を行う。 理解を簡単にするために、確保領域が固定サイズであったときのフリーリストを説明する。

フリーリストとは、free() によって開放された領域をリスト構造で保存しておき、 malloc() 要求があったら、フリーリストの先頭から再利用する手法。 簡単な手抜き実装であれば、初期状態で巨大なmalloc用配列を準備しておき、 その領域すべてをフリーリストとして繋げておけばいい。

通常のmallocは、引数として確保するメモリのbyte数を指定することができるため、 前の説明のように簡単な状況とはならない。 free()によって開放されたメモリ領域はfreelistに保存されるが、 リストにつなぐ際に隣り合った再利用領域は併合される。 malloc()で、フリーリスト内に適切なサイズのメモリブロックが無い場合は、 それより大きい領域を探し、分割される。 このため、malloc+freeの順序が最悪であれば、メモリ空間にヒープホールなどが発生してしまう(メモリの断片化:フラグメンテーション)。

関連する雑談として、同じ断片化(フラグメンテーション)ということで、 ハードディスクの断片化について説明する。 ハードディスクで断片化が発生すると、ムダなシーク時間・回転待ち時間が発生し、 アクセス速度が低下する。 Windowsなどでは、デフラグツールが一般的で、 この処理を行うとハードディスクの実体を覚えている場所を移動させ、 連続したセクタにデータが並ぶように再配置してくれる。