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

2012年12月
« 11月   1月 »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

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

後期後半の授業の予定としては、メモリ管理手法について説明の手始めとして、 動的メモリ管理の問題を説明する。

まずは、ポインタで共有のある場合の問題について説明する。 例として、リスト構造の和集合とリスト一括廃棄を説明する。

struct List* join( struct List* p1 , struct List* p2 ) {
struct List* ans = p1 ;
for( ; p2 != NULL ; p2 = p2->next )
if ( !find( p1 , p2->data ) )
ans = cons( p2->data , ans ) ;
return ans ;
}
void list_free( struct List*p ) {
struct List* del ;
while( p != NULL ) {
del = p ;
p = p->next ;
free( del ) ;
}
}
void main() {
struct List* n1 = cons( 1 , cons( 2 , NULL ) ) ;
struct List* n2 = cons( 2 , cons( 3 , NULL ) ) ;
struct List* n3 = join( n1 , n2 ) ;
// 何らかの処理
list_free( n3 ) ;
list_free( n2 ) ;
list_free( n1 ) ; // n1はすでにn3と共に捨てられている
}

上記プログラムでは、処理が終わってすべてのリストを捨てようとするが、 すでに list_free( n3 ) にて、n1 部分が廃棄済みであり、 list_free(n1)を実行すると、プログラムが異常動作となる。

参照カウンタ法

これらの解決方法の1つは、参照カウンタ法である。データを参照する ポインタの数をデータといっしょに保存し、共有が発生するたびに 参照カウンタをカウントアップし、データを廃棄する際には、 カウントダウンを行う。カウンタが0になったら参照しているデータ は無くなるので、本当にデータ廃棄を行う。

struct List {
int refc ; // カウンタ
int data ; // データ部
struct List* next ;
} ;
void list_free( strcut List* p ) { // 再帰で全廃棄
if ( p->refc <= 0 ) {      // 参照カウンタを減らし
list_free( p->next ) ; // 0ならば本当に消す
free( p ) ;
}
}

ただし、参照カウンタ法は、循環リストの場合には、カウントダウンが できず永遠に廃棄できないデータができてしまう。

一方、参照カウンタ法は、unix などのファイルシステムでのリンク にも利用されている。unix ではハードリンクが発生するたびに ファイル実体の参照カウンタをカウントアップし、ファイル削除では カウントダウンと0になった場合に削除を行う。

ガベージコレクタ法

循環リストの扱いの問題から、データの廃棄の判断は極めて困難となる。 これらの対応としてガベージコレクタ法がある。この方式では、 確保した動的メモリの廃棄処理は、プログラムでは明示的に書かない。 このため、廃棄されないゴミデータで埋まることになる。 この場合の対応手段がガベージコレクタである。

ガベージコレクタは、メモリを参照する処理を一旦停止させ、 実際に使用中のメモリすべてをポインタを辿りながら「使用中」の 目印をつける。その後、「使用中」の目印がついていないメモリを 回収する。(マーク&スイープ法)

ただし、昔のガベージコレクタは、メモリを使う処理を一旦停止させ、 全メモリ参照という時間のかかる処理を行うことから、 サービスが一時的に停止することとなる。

最近の新しいプログラム言語(Java,D言語,Perl,PHP)では、 参照カウンタ法とガベージコレクタ法を融合したものが採用されている。 このため、複雑にポインタが絡まないようなデータであれば、 参照カウンタ法により早い段階で回収され、ガベージコレクタの 処理の中断も目立たないようになっている。