GC/extend/MostlyCopyingGC(Bartlett 1989)
最終更新：
author_nari 2008年11月03日(月) 13:17:42履歴
MostlyCopyingGC(Bartlett 1989) 
あいまいなポインタを考慮し，極力CopyingをするGC
(1)
(2)
(3)
(4)
(5)
(6)
(1)
(2)
(3)
(4)
(5)
(6)
アルゴリズム
conservativeなGCにおいてCopyingGCを実装できないのは前述した通りである．
関数スタックやレジスタなどに格納されているルートが即値とポインタの区別がつかない為，
参照先のオブジェクトを移動できないからであった．
確実のオブジェクトのポインタと判断できない値を，「あいまいなルート」と呼ぶ．
このアルゴリズムではその「あいまいなルート」に関してはコピーを行わず，オブジェクト内から
指している確実に参照されているオブジェクトについてのみコピーを行う事でCopyingGCを実現する．
上図において，それぞれのオブジェクトの役割を説明しておく．
今回説明するのはオリジナルよりも少し拡張されたMostlyCopyingである．
この中でDの「あいまいなルートをもつオブジェクト」について説明する．
例えばSchemeの場合だと継続オブジェクトである．
継続オブジェクトには関数スタックの情報等あるため，これは「あいまいなルートをもつオブジェクト」だと言える．
またこのような共用体の場合も同様である．
拡張されていないMostlyCopyingのアルゴリムではこの「あいまいなルートをもつオブジェクト」についてサポートされていない．
メモリの割り当ては2段階で行われる．
GC起動のタイミングは割り当てたブロック（図で言うとFromの箇所）が全体の半分に達したタイミングである．
実際のGC処理内容は以下の通りである．図とあわせて参照してほしい．
関数スタックやレジスタなどに格納されているルートが即値とポインタの区別がつかない為，
参照先のオブジェクトを移動できないからであった．
確実のオブジェクトのポインタと判断できない値を，「あいまいなルート」と呼ぶ．
このアルゴリズムではその「あいまいなルート」に関してはコピーを行わず，オブジェクト内から
指している確実に参照されているオブジェクトについてのみコピーを行う事でCopyingGCを実現する．
上図において，それぞれのオブジェクトの役割を説明しておく．
今回説明するのはオリジナルよりも少し拡張されたMostlyCopyingである．
- A ルート（あいまいなルート）から参照されている
- B A,Dから参照されているオブジェクト
- C Aから参照されているオブジェクト
- D あいまいなルートを持つオブジェクト
- E，F どこからも参照されていないオブジェクト
この中でDの「あいまいなルートをもつオブジェクト」について説明する．
例えばSchemeの場合だと継続オブジェクトである．
継続オブジェクトには関数スタックの情報等あるため，これは「あいまいなルートをもつオブジェクト」だと言える．
またこのような共用体の場合も同様である．
union {
int n;
thing *ptr;
}
拡張されていないMostlyCopyingのアルゴリムではこの「あいまいなルートをもつオブジェクト」についてサポートされていない．
メモリの割り当ては2段階で行われる．
- ブロック中のメモリを割り当てる際には，空き領域の先頭を指すポインタを進めるだけでよい．
- ブロック内に処理系が要求したサイズの空き容量がない場合，次の空きブロックを探し，以降はそのブロックのメモリ割り当てを利用する．
GC起動のタイミングは割り当てたブロック（図で言うとFromの箇所）が全体の半分に達したタイミングである．
実際のGC処理内容は以下の通りである．図とあわせて参照してほしい．
- 割り当て済みのブロックはFromフラグを設定し，From空間として扱う．
- あいまいなルートから参照されているオブジェクトが存在するブロックはPromotedフラグを設定し，昇格させる．昇格されたブロックは最終的にはTo空間と見なされそのブロック内のオブジェクトはゴミでさえも生き残る．
- 空きブロックからToブロックを指定する．昇格したブロックに含まれるオブジェクトを全てそこにコピーする．この時，コピー元（A)にはフォワーディングポインタを残しておく．
- ここからはCheneyのコピーGCの要領でTo空間をスキャンし，幅優先でTo空間にコピーする．この際に「あいまいなルートを持つオブジェクト」(D)を発見した場合，その参照先を昇格させる．
- To空間にあるオブジェクトをもう一度スキャンし，ポインタを更新する．ただし，昇格したブロック中を指すポインタ('A,B')は更新せずに残す．ポインタの更新にはコピー元に置いておいたフォワーディングポインタを利用する．(C,D)
- 昇格したブロックをスキャンし，フォワーディングポインタを使って，コピー先のオブジェクト内容(A, B)をTo空間から書き戻す．残ったFrom空間は空き領域として再利用する．ここでゴミであるFは解放された．しかし，昇格されたブロックにあるゴミオブジェクトのEは解放されない，という事になる．
長所
- conservativeなGCでCompactionがある程度可能である．
- つまりフラグメンテーションが起きにくい．
短所
- あいまいなルートが多い場合，削除されるごみがすくなくなる．
実コードを見たい場合
- 不明
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
コメントをかく