参照カウンタ法とガベージコレクタ
後期後半の授業の予定としては、メモリ管理手法について説明の手始めとして、 動的メモリ管理の問題を説明する。
まずは、ポインタで共有のある場合の問題について説明する。 例として、リスト構造の和集合とリスト一括廃棄を説明する。
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)では、 参照カウンタ法とガベージコレクタ法を融合したものが採用されている。 このため、複雑にポインタが絡まないようなデータであれば、 参照カウンタ法により早い段階で回収され、ガベージコレクタの 処理の中断も目立たないようになっている。