ガベージコレクタとヒープ管理
前回の授業では、共有のあるデータ構造では、データの解放などで問題が発生することを示し、その解決法として参照カウンタ法などを紹介した。今日は、参照カウンタ法の問題を示した上で、ガベージコレクタなどの説明を行う。
共有のあるデータの取扱の問題
前回の講義を再掲となるが、リスト構造で集合計算おこなう場合の和集合を求める処理を考える。
struct List* list_union( struct List* a , struct List* b )
{ struct List* ans = b ;
for( ; a != NULL ; a = a->next )
if ( !find( ans , a->data ) )
ans = cons( a->data , ans ) ;
return ans ;
}
void list_del( struct List* p )
{ // ダメなプログラムの例
while( p != NULL ) { // for( ; p != NULL ; p = p->next )
struct List* d = p ; // free( p ) ;
p = p->next ;
free( d ) ;
}
}
void main() {
// リストの生成
struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
struct List* c = list_union( a , b ) ; // c = { 1, 1, 2, 3 }
// ~~~~~~~ ここは b
// a,b,cを使った処理
// 処理が終わったのでa,b,cを捨てる
list_del( c ) ;
list_del( b ) ;
list_del( a ) ; // list_del(c)ですでに消えている
} // このためメモリー参照エラー発生
このようなプログラムでは、下の図のようなデータ構造が生成されるが、処理が終わってリスト廃棄を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。
参照カウンタ法
上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。
参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。
- データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
- 処理の中で共有が発生すると、参照カウンタをカウントアップする。
- データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
int refc ; // 参照カウンタ
int data ; // データ
struct List* next ; // 次のポインタ
} ;
void list_del( strcut List* p ) { // 再帰で全廃棄
if ( p != NULL
&& --(p->refc) <= 0 ) { // 参照カウンタを減らし
list_del( p->next ) ; // 0ならば本当に消す
free( p ) ;
}
}
ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。
ガベージコレクタ
では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか？
最も簡単な方法は、「処理が終わっても使い終わったメモリを返却しない」方法である。ただし、このままでは、メモリリークの発生でメモリを無駄に使ってしまう。
そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、
- すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
- 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
- その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)
この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。
最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような関数に入った時点で生成され関数終了ですぐに不要となる領域は、参照カウンタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。
大量のメモリ空間で、メモリが枯渇したタイミングでガベージコレクタを実行すると、長い待ち時間となることから、ユーザインタフェースの待ち時間に、ガベージコレクタを少しづつ動かすなどの方式もとることもある。
ガベージコレクタが利用できる場合、メモリ管理を気にする必要はなくなってくる。しかし、初心者が何も気にせずプログラムを書くと、使われないままのメモリがガベージコレクタの起動まで放置され、場合によっては想定外のタイミングでのメモリ不足による処理速度低下の原因となる場合もある。手慣れたプログラマーであれば、素早くメモリを返却するために、使われなくなった変数には積極的に null を代入するなどのテクニックを使う。
動的メモリ領域とフリーリスト
動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。
この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。
mallocが一定サイズの場合
仕組みを理解する第1歩として、free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。free_list には、貸し出すためのメモリ空間をリスト構造で繋がった状態にしておく。
malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。
任意サイズのメモリ確保の場合
最初のステップでの説明は、mallocのメモリサイズを一定としていたが、本来は確保するメモリサイズが指定する。この場合は、以下の様に管理されている。mallocで貸し出されるメモリ空間には、ヒープメモリの利用者が使うブロックの前に、次のメモリブロックへのポインタとブロックサイズを記憶する領域をつけておく。こういったメモリブロックを free_list の考え方と同じようにリスト構造となるようにつないで保存されている。
この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。(説明を簡単化するためにポインタとメモリブロックサイズの部分は多少いい加減)
malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。malloc(40)
丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。malloc(60)
free()の処理とメモリブロックの併合
この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。
使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。また、free_list のリストが長いと malloc() の処理でジャストサイズのメモリブロック検索などの処理効率が悪くなる。
そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。さらに、併合によりより free_list の長さも短くできる。
また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。
一般的には、上記のようにmalloc(),free()を行うが(K&R の mallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。
ヒープメモリの断片化
ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。
この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。
(補足) 断片化
断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。
上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。
Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。
