提案方式

提案する方式の実装は第3章に示したアルゴリズムを拡張する形で行った．以下に述べるアルゴリ ズムでは，ごみ集めの対象外にされた古いオブジェクトから，ごみ集めの対象になる新しいオブジェ クトを参照しているポインタの管理のための，remember setや間接参照等を必要としない．

提案方式の世代別ごみ集めとしての振る舞いは，Appelの方式に近い動きをする．ただし，Appel の方式では，複写法に基づいているのでそうせざるを得ないのだが，圧縮の結果できたヒープの空き 領域を半分にして生成領域としていたのに対して，提案方式は空き領域を全て生成領域に振り向け ることができるので，ごみ集めの発生間隔を倍以上にできる．また，Appelの方式では，古い領域が ヒープの半分に達すると，全体的なごみ集めを行うのに対して，提案方式では，古い領域としてヒー プ全体を利用できるので，全体的なごみ集めの発生間隔も倍にできる．ただし，このタイミングは次 に詳述するように，1つのパラメタで制御可能である．

そして，Appelの方式ではremember set（RS）を用いて世代間ポインタの管理を行っているが，

提案方式では世代間ポインタが置かれている位置の最も上（番地が小さいもの）を更新するだけにし て，RSのための領域を必要としない代わりに，古い領域の世代間ポインタを線形探索で調べる必要 がある．

4.2.1 アルゴリズム

ヒープの上端と下端のアドレスをそれぞれHT，HB（HT < HB）とする．次の変数やパラメタを用 意する．

指標cmfa： 逆方向ポインタでヒープの最も上に位置するものを指す．

指標mfa： HTからmfaまでの領域のオブジェクトは印付けや移動の対象にならない．これを「古い 領域」と呼ぶ．mfaより下HBに至るまでの領域を「生成領域」（generation area）と呼び，オ ブジェクトの確保に使われ，ごみ集め時には印付けや移動の対象となる．

パラメタ salvage pointと指標 svgp： 0≤salvage point≤1を満たし，svgpはsvgp=salvage point×

HB+ (1−salvale point)×HTとして与えられる．mfaがsvgpを越えたら，つまり古い領域 のサイズがヒープのsalvage point以上になったら，mfaをHTに戻し，全体的なごみ集めを 行う（系をご破算にする）．

4.2. 提案方式 45

¶ ³

// 初期化 void init() {

mfa = HT;

cmfa = HB;

cross = false;

}

// フィールド f に対する書き換え時の処理

void setf(word *f, word d) { // d はポインタだと仮定

*f = d; // 書き換え

if ((f < d) && // 逆方向ポインタ

(f < cmfa)) // 始点がcmfaより小さい

cmfa = f; // cfmaを更新

if ((f < mfa) && // 始点が古い領域内で

(mfa < d)) // 終点が古い領域の外

cross = true; // 古い領域を跨ぐ逆方向ポインタあり

}

// ごみ集め void GC() {

if (cross == true) // 古い領域から飛び出していたら

mfa = cmfa; // 逆方向ポインタを全てごみ集め！

if (mfa > svgp) { // 古い領域が水準を越えたら mfa = HT; cmfa = HB; } // ご破算

cross = false; // この時点で古い領域を跨ぐ逆方向ポインタは

// 全てごみ集め済み

mfaとヒープ先頭の間のオブジェクトを辿らないようにして印付け；

クラスタ化とソーティング;

後ろ向き走査; // ヒープを下から上への走査(クラスタのみ)

if (C0 が古い領域に隣接 // ごみ集めを1回生き延びた

mfa = C0の次のアドレス;

// 前向き走査では古い領域も含める．

// 古い領域で最初の逆方向ポインタをcmfaに設定．

}

µ ´

図4.1: 生成順序保存に注目した世代別管理

フラグcross： mfaを跨ぐ逆方向ポインタ，つまり古い領域から生成領域のオブジェクトを指すポイ

ンタが発生したことを示す．

cmfa

mfa

mfa = cmfa lower

address

higher address

cmfa

mfa reverse C0

pointer

cross == false

cmfa

mfa

cmfa

mfa

cross == true

program execution

garbage collection

garbage collection

OLD-region generation area

OLD-region

HT

HB

図4.2: 古い領域の変化

図4.1にアルゴリズムを，図4.2に古い領域の変化の例を示す．図では古い領域のことをOLD-region と標記している．