先週の説明のガベージコレクタの補足説明として、 実装方法の他の方法としてコピー法などを紹介。

この後、リスト構造の応用の最後の説明として、mallocとfreeの実装方法を 説明する。ただし、順序良く理解をしてもらうために、 確保する領域サイズが固定の場合を説明する。

mallocで確保する領域サイズが一定であれば、 最後にfreeされたものを最初にmalloc用に使う…と考えれば、 freeされた領域を、リスト構造のスタックとすればいい。

struct HeapList {
struct HeapList* next ;
// データ領域
} ;
struct HeapList* freelist ;
void* my_malloc() {
struct HeapList* ans = freelist ;
freelist = freelist->next ;
return (void*)ans ;
}
void my_free( void* p ) {
struct HeapList* hp = (struct HeapList*)p ;
hp->next = freelist ;
freelist = hp ;
}

ただし、freelist は決められた領域のブロックをリストで連結しその先頭で初期化する。

ヒープ領域の断片化

実際のmalloc() , free() は、確保領域が自由な大きさを指定できる。 しかしながら、使用領域と開放領域が交互に並んだ状態で、 最初の使用領域よりも小さな領域の要求があると、 小さなメモリブロックが細切れで発生する。 この細切れで有効活用のできないメモリをヒープホールと呼ぶ。 また、このように細切れになることを断片化(フラグメンテーション) と言う。

関連する用語では、ハードディスクの断片化(フラグメンテーション)がある。 これは、ハードディスク内で散らばった小さなファイルが削除され、 この後に巨大なファイルが新規作成されると、1つのファイルが 分散して配置される。このような状態を断片化と呼び、 このファイルを読み出す場合、分散して配置されているため、 次の場所への移動で、シーク時間・回転待ち時間が余計に発生する。 これによりファイルの読み書き速度が遅くなる。 Windowsでは、これらの不連続状態の改善のために、 デフラグ機能がある。デフラグでは、ファイルの配置を入れ替え、 ファイルが連続して配置されるようにしてくれる。