先週に引き続き、動的メモリ領域の管理法の説明を行う。 最初に先週の領域サイズが固定ならば、freelist で管理可能という話と、 「最後に確保したメモリが最初に不要となる…」というのであれば、 スタックで管理が可能という話をしておく。

自由な領域サイズでのmalloc+freeでは、一般的に 次の領域へのポインタと、そのブロックのサイズを使って管理を行う。 このブロックをfreelist でリスト構造にして保存している。

mallocの処理

mallocでは、freelistの中から、要求サイズより十分大きいブロックを探すか、 要求サイズと同じサイズのメモリブロックを検索する。

要求サイズと同じブロックが見つかった場合は、そのブロックを迂回するようにポインタをつなぎかえる。(上図の青) 要求サイズより大きなブロックが見つかった場合は、その領域の後半を切り分けてユーザにメモリを貸し出す。この場合は、ブロックサイズの修正だけ。(上図の赤)

freeの処理

freeでは、返却された領域をfreelistに接続すればいいが、 このままではメモリ領域が細切れになるだけで、 最終的に大きなメモリを確保できなくなってしまう。 このため、返却されたメモリブロックは、freelist内に隣接する領域が無いか検索され、 隣接するメモリブロックと併合する。

一般的に次のメモリブロックへのポインタは、昇順方向になるように接続する。 また、mallocやfreeの処理での freelist 内の検索が行われるため、ヒープホールが 大量発生しているような状況では、処理効率の悪さが問題となる。 この辺の処理を簡単にするために、freelist をメモリブロックの大きさ毎に複数使う方法もある。

補足説明として、実際にユーザが要求したメモリとは別に、nextポインタとブロックサイズを 記憶する必要があるため、小さいメモリ領域をmallocで使うとメモリ使用効率が悪いことを 説明する。また、メモリブロックのサイズは、ワード境界のことを考慮して、4の倍数(32bitコンピュータならば)に切り上げられることを説明する。

ワードアライメントやheap管理データの領域が無駄といった話だけだと、 メモリ倹約至上主義で時代遅れと言われかねない。 補足説明として、メモリ増設もマザーボードから変えなきゃムリって場合はハードウェアの価格に影響が出ることと、 メモリ浪費で仮想メモリが使われだすとスラッシングで処理速度の低下の弊害を説明する。