GC/extend/TreadmillGC(Barker 1992)
最終更新：ID:e3W7ppwkaA 2009年08月24日(月) 17:00:10履歴
TreadmillGC(Barker 1992) 
Copyingに似たnon-movingなインクリメンタルGC
アルゴリズム
このアルゴリズムは双方向リンクを利用し，Copyingと似た動きをする．
つまりMark&Sweepは行わない．
Copyingのようにルートからたどったオブジェクトを移動させるアルゴリズムである．
移動の際，単純なChenyCopyingGCだとオブジェクトを物理的に移動するが，このアルゴリズムの場合，双方向リンクを付け替える事で移動とする．
このアルゴリズムではGCの際に4つのセグメントに分かれる．
またその区別の為，4つのポインタをもつ．
初期状態は以下の様な位置関係にある．
freeからオブジェクトを割り当てると，topとbottomの間に位置づける．
そうすると自然とFrom空間は肥大化し，Freeは少なくなる．
Freeが残り半分程になるとGCを開始する．手順は以下である．
私的にはしくみを知ったときに一番感銘を受けたアルゴリズム．
美しいですよね．
つまりMark&Sweepは行わない．
Copyingのようにルートからたどったオブジェクトを移動させるアルゴリズムである．
移動の際，単純なChenyCopyingGCだとオブジェクトを物理的に移動するが，このアルゴリズムの場合，双方向リンクを付け替える事で移動とする．
このアルゴリズムではGCの際に4つのセグメントに分かれる．
- Free 解放済み，もしくは未使用のオブジェクトが所属する空間
- New スキャン中に割り当てたオブジェクトが所属する空間
- To Fromから生きているオブジェクトの移動する先の空間
- From スキャン対象のオブジェクトが所属する空間
またその区別の為，4つのポインタをもつ．
- top To空間との境目に位置
- bottom Free空間との境目に位置
- scan スキャン対象のオブジェクトを指す
- free 次のオブジェクト割り当て対象を指す
初期状態は以下の様な位置関係にある．
- scanとfreeは隣同士に位置
- topとbottomとscanは隣同士に位置
freeからオブジェクトを割り当てると，topとbottomの間に位置づける．
そうすると自然とFrom空間は肥大化し，Freeは少なくなる．
Freeが残り半分程になるとGCを開始する．手順は以下である．
- ルートを探索し，見つかったオブジェクトをscanとtopの間に移動する．ここにTo空間が生まれる．
- ルートを探索し終えると，scanポインタをtop方向にずらし，オブジェクトをスキャンする．
- 見つかったオブジェクトは同様にscanの右に移動する．
- 一つの木を探索し終えると，いったんGCを中断する．
- オブジェクトの割り当て要求がある場合，freeをbottom方向にずらす．この際free-scan間はNew空間になる．
- またGCを再開．
- これを繰り返しscanがtopに到達すると，bottomをtop方向にオブジェクトを解放しながら動かす．
- bottomがtopに到達すると，From空間がまるまるFree空間に変わる．
- その後,scanをfreeの横に，topをscanの横に移動する事でTo空間がFrom空間に変わる．
- GC終了．
私的にはしくみを知ったときに一番感銘を受けたアルゴリズム．
美しいですよね．
利点
- インクリメンタル
- non-movingなCopyingGCのようなものを作成できる
欠点
- CopyingGCとは違いコンパクションされない。フラグメンテーションが発生する。
実コードを見たい場合
- Io(id:keisukefukudaさんより）
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
このページへのコメント
欠点といいますか、
Copying GC と大きく異なるのは compaction が無い点ですよね。
プログラミング言語Ioが、Generational Treadmill GCを採用しているようです。