ホーム » スタッフ » 斉藤徹 » ヒープメモリの管理法

2012年1月
« 12月   2月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

ヒープメモリの管理法

動的メモリの管理手法として、参照カウンタ法・ガベージコレクタ法の説明の最後として、 ヒープメモリの管理手法について説明する。 いつもはこういった講義メモは、授業後に作成しているけど、 今回は他の先生に授業方法開演のために見てもらう『公開授業』となるため、 授業前にメモを記載しておく。

ヒープメモリの必要性

必要に応じてメモリ領域を確保する場合、一般的には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() では、

  1. free_list の先頭から、要求サイズよりも十分な大きさのメモリブロックを探す。
  2. そのメモリブロックの大きさと要求サイズが同じなら、free_list からそのブロックを切り離し、そのブロックをユーザに使ってもらう。
  3. 十分に大きい場合は、そのメモリブロックの末尾を、要求サイズ分に切り分ける。
    • つまり、そのブロックのsizeを、要求サイズ分だけ減らし、
    • 分割した末尾部分のアドレスをmallocの返り値として、ユーザに使ってもらう。

free()で、メモリブロックが返却された場合は、 基本的に free_list に連結すればいい。 ただし、このままでは、freeとmallocを繰り返すうちに、メモリブロックは小さく細切れになる一方で、最終的に大きなメモリブロックが使えなくなる。

この対策として、不要となったブロックを free_list につなぐ場合、ブロックはメモリアドレス順に並ぶようにする。 さらに、free_list につなぐ際に、リストの前後のメモリブロックと隣接する場合は、 next と size を調整して1つの大きなメモリブロックとなるように併合を行う。

ヒープホールと断片化

上記のようなmallocとfreeであれば、mallocの呼び出しで細切れにされたメモリブロックも、freeの呼び出し時の併合により、大きなメモリブロックに戻る。 しかしながら、最悪の順序でmallocとfreeを繰り返すと、一連のヒープ領域が「使用・不要・使用・不要・使用」のように交互になった場合、全体では不要メモリの総量は大きくても、mallocの要求メモリサイズの領域を見つけられなくなる可能性がある。

このような、細切れになった状態を断片化(フラグメンテーション)と呼び、 その細分化された不要領域はメモリ領域の小さな穴ということで、ヒープホールと呼ばれる。

毎年、このネタでは鉄板なんだけど、フラグメンテーション解消のデフラグ ということで、ハードディスクのフラグメンテーションの説明とデフラグ処理の 説明を行う。