GCアルゴリズム詳細解説

　ずばり
　「日本語によるGCアルゴリズムの詳細解説」
　です。
　
　このWikiには最新の技法から古い技法まで，自分のまとめたものをちまちま書いていくつもりです。
　編集は自由ですので，よかったら何か書いてもらえるとありがたいです．

　id:authorNariが管理人です．
　何か有りましたら，authorNari at gmail.com の方へどうぞ．

　どこからも参照されなくなった(つまり不要)メモリ領域を自動で掃除してくれる便利なやつ。
　本当はmalloc/freeと手動でメモリ管理しなければならない所（C言語など）を
　あるタイミング(使う側には指定できない事が多い)でいらない領域をfreeしてくれる。
　本Wikiは概要についてはあんまり説明しないのでガベージコレクション(wikipedia)を参照
　
　GCは二つの略語をさします。

• (garbage collection) ガベージコレクション -- プログラム上で不要となったメモリを回収する動作。
• (garbage collector) ガベージコレクタ -- 上記を実現するメカニズム。

　本Wikiでは、統括して「GC」と呼ぶ事にします。

専門用語を知らないと中々辛いので、まとめています。
用語集

これからの物事を理解するために、プログラムが動いている時のメモリ領域の構造を図 に示す。
大まかには、Java, ML, C 言語も含めほとんどの言語は似たような構造になる。
ヒープ内の小さい四角はオブジェクトを表す。
また、あるオブジェクトA の中に含まれるポインタが、別のオブジェクトB を指していることがある。
(record の中にrecord がある場合や、オブジェクトのフィールドに別のオブジェクトを含む場合など)
図中では参照関係を、A からB への矢印で表す。

• スタックには、局所変数や関数呼び出しの履歴などが格納される。(話をごく簡単にすると) 関数呼び出しが起こると伸びて、return が起こると縮む。

• 大域変数を格納する領域が用意される。定数が格納される領域も独立に用意される場合が多い。

• レジスタは、関数の引数、計算の途中結果など様々な値をとる。オブジェクトを指すポインタの可能性もある。

• ヒープは自由な順番でメモリ領域を確保/解放できる領域である。

　オブジェクト作成(C ではmalloc)を行なうと、ヒープの中に必要な大きさの領域が確保される。

• 図には示していないが、プログラムのコード領域もどこかにある。

世の中にあるGCアルゴリズムはこの3パターンに最終的に集約される．
基本中の基本のアルゴリズムである．

参照カウント(GC)

印づけ、掃除

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

ここでは基本アルゴリズムを応用し、欠点を解決したアルゴリズムの紹介をする。

ちょっとづつGC

若いやつらを優先するGC

開始時の写真を元にゴミ掃除

遅延Sweep

空いてる所につっこむ

先頭にずらす

部分的なMarkandSweep

極力ParallelなGCを行う

Old世代を車両に分割してインクリメンタルにGC

あいまいなポインタを考慮し，極力CopyingをするGC

Copyingに似たnon-movingなインクリメンタルGC

大抵のGCでは最初にルートの走査を行う。
具体的には参照先のアドレス(ポインタ)がヒープ領域内にあるかどうか？という
チェックをルートすべてに行うのだが、
この際に、もし、ヒープ領域内を指す数値が見つかった場合、
それがプログラム中に使用された数値(intなど)なのか、オブジェクトへの参照(ポインタ)なのか
判断する事ができない。
この問題にどう対処するかによって、conservativeGCとexactGCの2種類にGCは分けられる。

conservativeGCはこの場合、オブジェクトへの参照では無く、只の数値だったとしても
そのオブジェクトの解放は行わない。
つまり、数値であった場合にポインタの値を変更(CopyGCなど)した時はプログラムとして致命的である為、
何も触らない方向に倒すという事だ。
まさに保守的なGCだ。

利点

• 無駄な細工をせずに済むので処理が軽い
• 実装が楽

欠点

• 回収されないゴミが残る可能性がある
• CopyingGCなどオブジェクトを移動する事ができない。

　→解決方法1：オブジェクトとポインタの間に一枚ハンドルを噛まして抽象化する。
　　　　　　　　実際にハンドルの数値だけが変わり元のポインタに影響はない。
　　　　　　　　(間接参照になる為、通常の処理が遅くなる欠点)

詳細な解説

• ConservativeGCとは何か

conservativeGCではなんでもオブジェクトとみなして、ゴミが残る可能性があったが
exactGCではポインタと数値をはっきり区別し、ゴミを残さず回収する事をポリシーとする。
ポインタと数値を区別する具体的な方法は、

• 整数値の範囲を1 bit減らして、その1bitをタグビットとして利用する。
• stack map方式

がある。

ほとんどの処理系は，処理系自身がルートを提供する事であいまいなポインタがなくなりexactGCとなる．
この場合，GCにより協力的な処理系と言える．

利点

• ゴミを全て回収するのでメモリ効率がいい
• オブジェクトの移動が楽にできる。(コンパクション)

欠点

• 色々と制限がつく
• 実装が面倒

ちなみに「絶対的GC」という訳はオリジナル。べたに訳すと「確実なGC」になる。
またexactと同じ意味でprecise（プリサイス）と呼ぶ事もある．
（英語ではこっちの方が多いかも）

Mark&Sweepアルゴリズムでは「Root から到達可能かどうか」をチェックするためにオブジェクトにマークを行っていたが、
これとは別に「書き換えられたオブジェクト」をチェックするために別種類の印をつける。
例えば、以下のような Java プログラムを実行しているスレッドが、 object1 のフィールドになんらかのオブジェクトの参照を書き込む場合、
object1 に「書き込まれた」という印を付けるのである。
この処理を ライトバリア (write barrier) と呼ぶ。
object2 が null でない場合は、どんなオブジェクトでもチェックを行う。

void method( Class1 object, Class2 object2 ){ object1.field = object2; }

ライトバリアされた後の、メモリ中のイメージとしては下の図のようになる。

個人的にわからなかった単語たち

和訳：保有権のある、終身在職権のある、身分保障のある
世代別GCの古い世代を置く領域の事

オブジェクトの状態を書き換える者、すなわちユーザープログラムのこと

和訳：清掃をする

和訳：ゴミを掃き出す

和訳：根、根源
GCにおいて、「確実に必要なオブジェクト」。
スタック領域、レジスタ、グローバル変数、定数などから参照されているヒープ領域を指す。
このオブジェクトを起点に必要なオブジェクトが探索され、探索されなかったオブジェクトがGCの対象になる。

和訳：大きな塊
GCの対象になる塊、場合によってはオブジェクトだったりデータだったり

Mark&Sweepを何度も繰り返すとメモリの断片化が起こるが、
その状態を整頓するする事を指す。
Windowsで言う所のデフラグの様なもの。

和訳：割り当てる
メモリ割り当てる行為。GC関連の資料では管理対象のオブジェクトを作成する事を指すことが多い。

和訳：昇進させる、昇格させる
新世代から旧世代に移動させること、殿堂入りとも言う。

和訳：飢餓状態
要求に応じられるだけのフリーなデータがなくなった状態

ルート集合から直接さされているセル(データ)に一括して印をつけ、GC用スタックに挿入すること

GCではよくLispなどの処理系で説明が行われる。オブジェクトと同義だと思ってよい。

• BoehmGCHackers
• 一般教養としてのGarbageCollection(pdf)
• 微酔半壊 Copying Garbage Collector
• Gaku's Space Wiki (Garbage Collection)
• RHG ガベージコレクション
• VisualWorks の GC の戦略発表 OHP
• GC on GC
• Mostly-Concurrent Mark & Sweep GC のアルゴリズム
• Garbage Collection Jones&Lines著（GCの教科書。。。英語だけどね）

• ガベージコレクションのアルゴリズムと実装（拙著です）

id:authorNari