最終更新:ID:e3W7ppwkaA 2009年08月24日(月) 17:00:10履歴
このアルゴリズムは双方向リンクを利用し,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終了.
私的にはしくみを知ったときに一番感銘を受けたアルゴリズム.
美しいですよね.
- カテゴリ:
- パソコン
- ガーベッジコレクタ(GC)
このページへのコメント
欠点といいますか、
Copying GC と大きく異なるのは compaction が無い点ですよね。
プログラミング言語Ioが、Generational Treadmill GCを採用しているようです。