動的メモリの管理手法として、参照カウンタ法・ガベージコレクタ法の説明の最後として、 ヒープメモリの管理手法について説明する。 いつもはこういった講義メモは、授業後に作成しているけど、 今回は他の先生に授業方法開演のために見てもらう『公開授業』となるため、 授業前にメモを記載しておく。
ヒープメモリの必要性
必要に応じてメモリ領域を確保する場合、一般的にはmalloc()+free()を用いる。 メモリは有限でもあり、free()で返却されたメモリ空間の再利用が重要となる。 確保したメモリが不要となるタイミングが『最後に確保したメモリが最初に不要となる』という条件を満たすのであれば、スタックを用いればいい。 スタックを用いるメモリ確保命令は、alloca(int) であり、その仕組みを my_alloca() にて 説明すると、内部はおおよそ、以下のような処理である。
#define HUGE_SIZE (大きな領域サイズ) char u_stack[ HUGE_SIZE ] ; char *u_sp = stack + HUGE_SIZE ; // 領域の末尾アドレスで初期化 char* my_alloca( int size ) { u_sp -= size ; return u_sp ; }
あとは、関数呼び出し時に、戻り番地(プログラムカウンタ:PC)の保存と共に u_sp を保存し、関数を終え元処理に復帰する(PCの復帰)の際に u_sp を復帰すればいい。
ヒープメモリのブロックが固定サイズなら
alloca() では、「最後に確保したメモリが最初に不要となる』の条件が重要であり、 不要となるタイミングが予測できない場合は、どうすればいいか? 基本は、free() で開放したメモリを再利用すればいいのだから、 free() で開放したメモリをリスト構造で連結したスタック(free_list)としておいて、 malloc()の際は、free_listに保存しておいたメモリ領域のリストの先頭を使えばいい。
動作原理を説明する、模式的なプログラムを以下にしめす。 ただし、malloc() の引数で指定するメモリブロックサイズが不均一だと、 処理が分かりにくいので、ブロックサイズは固定で説明する。
#define BLK_SIZE (適当な大きさ) struct MemList { struct MemList* next ; char memory_block[ BLK_SIZE - (nextのサイズ) ] ; } ; // heap内は全てがリストで繋がるように初期化する。 struct MemList heap[ HUGE_SIZE ] ; struct MemList* free_list = (heapの先頭) ; char* my_malloc() { char* ans = free_list ; // 型キャストは省略 free_list = free_list->next ; return ans ; } void my_free( char* p ) { p->next = free_list ; // リストの先頭に入れる free_list = p ; }
可変長ブロックのヒープメモリ管理
上記のプログラムでは、説明のために確保するメモリブロックは固定サイズとしたが、 実際には色々なサイズが使われる。この場合、おおまかに以下のような方法がとられる。
ヒープメモリで管理する個々のメモリブロックには、 管理用にそれぞれ (1)次のメモリブロックへのポインタと、 (2)メモリブロックのサイズ を記録する。
struct HeapList { struct HeapList* next ; int size ; char* memory[ (size) ] ; // 説明用の記述、C言語ではエラー } ;
管理するメモリ領域は、最初1つの巨大なメモリブロックとして初期化し、 そのブロックの先頭を free_list に入れておく。
malloc() では、
- free_list の先頭から、要求サイズよりも十分な大きさのメモリブロックを探す。
- そのメモリブロックの大きさと要求サイズが同じなら、free_list からそのブロックを切り離し、そのブロックをユーザに使ってもらう。
- 十分に大きい場合は、そのメモリブロックの末尾を、要求サイズ分に切り分ける。
- つまり、そのブロックのsizeを、要求サイズ分だけ減らし、
- 分割した末尾部分のアドレスをmallocの返り値として、ユーザに使ってもらう。
free()で、メモリブロックが返却された場合は、 基本的に free_list に連結すればいい。 ただし、このままでは、freeとmallocを繰り返すうちに、メモリブロックは小さく細切れになる一方で、最終的に大きなメモリブロックが使えなくなる。
この対策として、不要となったブロックを free_list につなぐ場合、ブロックはメモリアドレス順に並ぶようにする。 さらに、free_list につなぐ際に、リストの前後のメモリブロックと隣接する場合は、 next と size を調整して1つの大きなメモリブロックとなるように併合を行う。
ヒープホールと断片化
上記のようなmallocとfreeであれば、mallocの呼び出しで細切れにされたメモリブロックも、freeの呼び出し時の併合により、大きなメモリブロックに戻る。 しかしながら、最悪の順序でmallocとfreeを繰り返すと、一連のヒープ領域が「使用・不要・使用・不要・使用」のように交互になった場合、全体では不要メモリの総量は大きくても、mallocの要求メモリサイズの領域を見つけられなくなる可能性がある。
このような、細切れになった状態を断片化(フラグメンテーション)と呼び、 その細分化された不要領域はメモリ領域の小さな穴ということで、ヒープホールと呼ばれる。
毎年、このネタでは鉄板なんだけど、フラグメンテーション解消のデフラグ ということで、ハードディスクのフラグメンテーションの説明とデフラグ処理の 説明を行う。