ガベージコレクション
基本的な考え方
色々なGCアルゴリズムがあるが、基本的に「到達可能なオブジェクト」以外を開放するというアイディアに基づく
1. ルートから参照可能なオブジェクトをたどり「到達可能なオブジェクト」の完全な集合を見つける
2. その集合に含まれないすべてのオブジェクトを解放する
上記の2つの操作をどう行うか？という違いがGCのアルゴリズムの違いである。
到達可能とは？
GC開始時に生きているレジスタ, および大域変数中にあるポインタで指されるオブジェクトは到達可能
(スタックはスタック全体を一つの巨大なオブ ジェクトとみなすことにする).
あるオブジェクトが到達可能な時, そのオブジェクト内に格納されているポインタで指されるオブジェクトも到達可能
スタックやレジスタを根とした, グラフのtraverseを行なうのがGC
GCのアルゴリズムをオブジェクトに「色を塗っていく」プロセスと捉える
白 → まだGCに発見されていないオブジェクト
GC未処理のオブジェクト
灰色 → GCに発見されたが、まだ白色オブジェクトを参照しているかもしれないオブジェクト
GCの追跡処理がまだ途中であるオブジェクト
黒 → GCに発見され, かつ指しているオブジェクトはすべて黒か灰色
つまりGCの追跡処理が完了したオブジェクト
オブジェクトの状態を三色に分けることで、大体のGCは以下のように動作する
code:GCアルゴリズム.txt
すべてのオブジェクトを白にする;
レジスタ, スタックなどのルートオブジェクトを灰色にする;
while (灰色オブジェクトが存在する) {
grayObj := 灰色オブジェクトを1つ取り出す;
grayObj が直接参照する白オブジェクトを灰色に塗る;
grayObj を黒に塗る;
}
この抽象化によって
GCがオブジェクトの参照グラフを走査するときに以下を防止できる
どこをマークしているのかわからなくなる
（循環参照）を堂々巡りとなって無限ループになる
動作
GCが起動して時間が経過するたび、オブジェクト全体が黒になっていく
黒色オブジェクト → 白色ポインタが存在しないオブジェクト
ルートオブジェクトは初期状態で灰色
よってGC終了時にルートオブジェクトは全部黒色
黒色オブジェクトが指すのはすべて黒色
動作イメージ
★がルートオブジェクト
https://www.craftinginterpreters.com/image/garbage-collection/tricolor-trace.png
白いままのオブジェクトはGCに回収される
したがってGCを設計するのに必要な操作は以下の３つ
1. あるオブジェクトを灰色オブジェクトの集合に挿入する
2. 灰色オブジェクトの集合から一つオブジェクトを取り出す
3. あるオブジェクトが白か否か判定する
引用元: