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

参照カウンタ法

例えばリスト操作で、リストの開放を下記のようなコードで作った場合、 データに共有が発生しているため、「持っているデータを 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して、0になれば本当に消す。 ただし、OSの異常停止などで、参照カウンタがおかしくなる場合があるため、unix では、 異常停止からの回復時には fsck で参照カウンタの修正などが行われる。 最近はジャーナリング機能付きファイルシステムが普通なので、fsck 実行は減ったけど….

ガベージコレクタ

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

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

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

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

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

仕事始めの校長年頭挨拶がありました。 今年の目標としては、以下のものが掲げられました。

• 入試倍率の確保
• 様々な意味でのActivityの拡大
• 国際化

昨年より取り組まれていた、高専のイメージ戦略として作られた、 PR用の旗が会議室に飾られていました。校章は相変わらず使われるけど、 用途によってはこちらの旗を見る機会が増えるかも。

昨日は職場の一斉有給で今日が仕事始め。 といっても、今日はやり残していた自室の大掃除の続きが目的だったり。 ということで、まずは長期休暇明けということで、一発目は管理サーバのアップデート。

サーバに次々とログインし、"aptitude update ; aptitude safe-upgrade"を打ちまくる。 学科のメインサーバだけ、stableとtestingが混在しているので、aptitude が、 "E: このAPTが対応している以上の数の説明が要求されました"なる意味不明な メッセージが表示される。"export LANG=C"にして、日本語localeをはずすと、 正常にアップデートできるんだけど….前回も同じトラブルが発生しているし、ひとまずメモ。