ホーム » スタッフ » 斉藤徹 » 参照カウンタ法とガベージコレクタ

2010年1月
« 12月   2月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

参照カウンタ法とガベージコレクタ

前回テスト解説で少し説明をしているけど、参照カウンタ法とガベージコレクタについて解説。

参照カウンタ法

例えばリスト操作で、リストの開放を下記のようなコードで作った場合、 データに共有が発生しているため、「持っているデータを free で全部捨てる」 といったコードを書くと、共有部分は2回捨てられる処理となり、 プログラムが異常動作してしまう。

struct List* union( struct List* l1 , struct List* l2 ) {
struct List* ans = l2 ;
for( struct List* p = l1 ; p != NULL ; p = p->next ) {
// find(A,L) : AがリストLに含まれていればTrue
if ( ! find( p->data , l2 ) )
ans = cons( p->data , ans ) ;
}
return ans ;
}
void free_all_list( struct List* p ) {
if ( p != NULL ) {
free_all_list( p->next ) ;
free( p ) ;
}
}
void main() {
struct List* a = リスト ;
struct List* b = リスト ;
struct List* c = union( a , b ) ;
:
なんらかのしょり ;
:
free_all_list( c ) ; // cの後半はbのはず
free_all_list( b ) ; // free_all_list(c)でbは既に捨てられている
free_all_list( a ) ;
}

こういう共有が発生している場合の対処方法として、参照カウンタ法がある。 共有されるデータには、すべてカウンタを設け、共有が発生する場合には、 カウンタを増やし、freeの際には、カウンタを減らし0の場合だけ 本当に捨てるという処理にすればよい。

struct List {
int   refc ; // 初期値1、共有されるたびに+1,共有が解除されれば-1
int   data ; // refc = 0 で、本当に free() を実行する。
struct List* next ;
}

ちなみに、この参照カウンタ法は、unix におけるリンク機能(1つのファイル実体に複数のファイル名をつける場合[ハードリンク])でも使われており、新しくハードリンクを貼れば+1し、 ファイルを消すと-1して、0になれば本当に消す。 ただし、OSの異常停止などで、参照カウンタがおかしくなる場合があるため、unix では、 異常停止からの回復時には fsck で参照カウンタの修正などが行われる。 最近はジャーナリング機能付きファイルシステムが普通なので、fsck 実行は減ったけど….

ガベージコレクタ

上記の参照カウンタは、便利そうに見えるけど、循環リストには対応できない。 こうなってくると、データを本当に捨てるか捨てないかは、プログラマーの判断では極めて難しい。そこで、最近のシステムでは、不要になったデータを捨てる判断は、ガベージコレクタ(ゴミ拾い)に任せるようになってきた。 ガベージコレクタを持った処理系では、free() は存在しない。メモリが不足した場合に、 システムが不要なメモリを回収してくれる。

回収方法としては、古くはマーク&スイープ法が有名。 メモリが不足した時に、全メモリには最初にマークを消しておき、使用中のメモリからたどりながら、実際に使用されているデータには、「使用中マーク」をつけていく。 最後に使用中マークの無いデータを回収する。

しかしながら、この方法はメモリが無くなった時に、処理を全部中断して、時間をかけたメモリ回収(ガベージコレクタ)が起動するため、利用者にしてみるとシステムが突如フリーズしたように 感じる。最近では、このガベージコレクタは、システム処理に並行して実行できるように工夫されている。

最近の新しい言語処理系 Java などはガベージコレクタが搭載されている。 しかし、C,C++ はガベージコレクタが無いので動的メモリを使ったプログラミングでは、 注意深く対応するしかない。

調べてみると、最近のJavaでのGCは、世代別GCという方法が使われているらしい。 若い世代、古い世代、永続的な世代に分け、生存時間順に随時永続側にコピーされていく。 局所変数のデータは、若い世代の場所に置かれ、 関数終了時に不要ならばガンガン消されていく。