GCアルゴリズム詳細解説

生きてるものだけ違う入れ物にいれて，死んでるものは入れ物毎捨てる

Copying GC アルゴリズムは、生きたオブジェクトをすきまをつめながら移動するというものである。
これにより、mark sweep やreference counting で問題となるfragmentation が全く起らないという利点がある。
また、多くのSchemeやML処理系で採用されている。

ここでは最も単純な、ヒープを2 等分する方式を紹介する。
この方式では、一度に使えるヒープは2等分のうち片方のみである。使用中の片方が埋まった時点でGC を起動する。
そして到達可能なオブジェクトたちを、そっくりもう片方のヒープに隙間をつめながらコピーする。
コピー元のヒープをfrom-space、コピー先のヒープをto-space と呼ぶ。
コピーが終った時点ではすでにfrom-space には生きたオブジェクトの残骸とゴミしか残っていないので用無しとなる。
GC 終了後、ユーザプログラムはto-space を用いて動作を続ける。このように、GC の度に2 つのヒープの役割を交替しながらシステムは動作する。

この方式を実装しようとするとき、いくつか注意が必要である。
例えばコピー後のグラフは必ずto-space内で完結し、from-space にポインタがのびていてはいけない。
また、複数箇所から同オブジェクトが参照されている場合にも注意する。
図ではb とc がd を参照しているので、to space においてもb'とc'は同オブジェクトを参照しなければならない。
アルゴリズムを3 色モデルを用いて考えると以下のようになる。

• 白· · · まだコピーされていない(from-space にしかない) オブジェクト
• 灰色· · · それ自身はコピーされたが、from-space のオブジェクト(白オブジェクトや他のオブジェクトのコピー前) を指している可能性がある。
• 黒· · · それ自身はコピーされたし、from-space を指している可能性もない。

上のような条件を満たしていれば、深さ優先でも幅優先でも良い。ここでは、copying GC の代名詞に
なっている、Cheney の幅優先アルゴリズムを紹介する。これは再帰呼び出しもマークスタックのような領域も使わない。
ヒープ以外のメモリ使用量はO(1)!
GC 開始時に、ルートオブジェクトから直接参照されるオブジェクト(図ではa のみ) をto space にコピーする。この時点でa は灰色と考えられる。
このアルゴリズムは再帰探索のために2 つのポインタを用いる。

1. scanned· · · 初期値はto-space の先頭。scanned より手前は全て黒オブジェクトである。
2. unscanned· · · 初期値は、図の場合(to-space の先頭) +sizeof(a)。scanned とunscanned の間は全て灰色オブジェクトであり、unscanned 以降は空き領域。

GC は以下の処理を繰り返す。scanned が指す先頭オブジェクトo を取り出し、o の子オブジェクト達のうち、
未コピーであるものをアドレスunscanned にコピーする(o の子オブジェクト達を灰色にする)。その度にunscanned を進める。
同時に、o 中のポインタがコピー先をさすように書き換え、scanned を進める(o を黒にする)。
scanned がunscanned に追いついたら、GC を終了する。

さて、同じオブジェクトへの複数参照に対応するためには、from-space 中のd を見ただけで、
「これはすでにコピー済みであり、コピー先はd' である」
ということが分かる必要がある。
そのために、灰色化の時点でd にforwarding tag (コピー済みであることを表す)、
forwarding pointer(コピー先を教えてくれる)を書き込んでおく。

1. メモリ回収と同時にcompactionできる。
2. 参照関係を考慮したコンパクションにより、キャッシュとの相性がよい(＝プログラムの実行速度が上がる)。
3. Mark&Sweepなどと比べてallocate処理が早い(FreeListなど使わなくていい為)
4. また解放処理も早いよ。

1. オブジェクトの移動により、ポインタの書き換えが起こり、保守的GCは作りにくい。
2. ヒープ領域を分割するため、メモリ領域を何倍も取る。

• Scheme処理系の何か

• Cheney's Algorithm
  • 動くデモがあり、想像しやすい