世代別ごみ集めとその関連研究

表2.2: 世代別ごみ集め方式一覧

方式 終身雇用ま 半領域の 世代記録 世代間ポインタ

での世代数 種類と個数 記録法 検出法

Liberman[49] G 小×G 半領域 間接参照 書き換え時

Ungar[76] G 大+小×3 オブジェクト RS 書き換え時

Appel[5] 1 2（伸縮） 領域 RS 書き換え時

Wilson[79] 2 大+小×2 領域 RS

小出[40] G 3（伸縮） 生成順序 印付け時

G: 世代数

RS: remember set（世代間ポインタを登録する表）

正が挙げられる．新しい世代のオブジェクトがごみ集めによって回収されないようにしたり，移動し たときの補正を行うために，全ての世代間ポインタを何らかの形で記録しておく必要がある．

このためのひとつの方策は，間接ポインタの表を用意し，世代間ポインタを全て間接参照にするこ と[49]である．これを用いると，オブジェクト参照の度に，間接参照か否かを調べるオーバヘッドが かかり，オブジェクトへ書き込みの度に，間接ポインタの表に登録すべきものか否かを調べ条件を満 たせば間接ポインタの表に追加する手間がかかる．ごみ集めの際は，間接ポインタの表から指されて いるオブジェクトの全てが「使用中」であると仮定して，印付けや複写を行う．

もうひとつの方策は，世代間ポインタの場所の全てをremember set（以下RSと略す）[76]と呼ば れる表に記録しておくことである．この戦略を用いると，オブジェクトへ書き込みの度に，RSへの 追加を行うか否かを決定し，必要なら追加する手間がかかる．ごみ集めの際は，RSから指されてい る全ての（古い領域に配置された）オブジェクトを調べ，ごみ集めの対象となる領域を指しているポ インタであれば指されたオブジェクトは「使用中」と仮定して印付けや複写を行い，そうでなければ RSからそのエントリを削除する．

世代別ごみ集めには，いくつかの方式が提案されているが，それらの論点は終身雇用のポリシ以外 は以下の点に絞られる．

• 世代の分類数

• 半領域の種類と個数

• 世代情報の記録

• 世代間ポインタの管理法（記録法と発生検出法）

2.4.2 既存の世代別ごみ集め

今までに公表されてきた世代別ごみ集めのうちで主要なものの概略を表2.2に示す．これらはすべ て複写法に基づいている．

以下，個別に内容を見ていく．各図で新しいオブジェクトはNEWと記された領域から生成され，

OLDと記された領域はごみ集めの作業を割愛する領域（終身雇用オブジェクトを置く領域）である

2.4. 世代別ごみ集めとその関連研究 25

evacuate evacuate evacuate

Creation region

most frequent little less frequent less frequent

図 2.8: Libermanの世代別ごみ集めのヒープレイアウト

とする．また，「救助」（evacuation）という用語は，領域内に存在する生存しているオブジェクトで あって最終的に複写されるもの全体の複写という意味で使う．

Libermanらの実時間ごみ集め

世代別ごみ集めのさきがけで，Bakerの実時間ごみ集めの一般化と考えられる．図2.8のようにヒー プの組を複数用意し，左側ほど救出の頻度が低くなるようにごみ集めのスケジューリングを調節する．

世代間ポインタの発生はポインタの書き換え時の検査で行い，それらはすべて間接参照とする．

この論文はアイディア論文と考えられ，具体的なヒープのレイアウトやサイズ等についての提案が ない．

Ungerの実時間ごみ集め

Libermanとほぼ同時期に発表された手法で，図2.9のように大きな1つの古い領域と，小さな3

つの領域から構成される．世代管理は，ごみ集め対象領域の各オブジェクトに付されたカウンタでご み集めを生き延びた回数をカウントし，それが閾値を超えたら終身雇用する．カウンタのための余計 な記憶と，カウンタの管理のオーバヘッドが問題となる．

Appelの世代別ごみ集め

Appelが実装したStandard ML of New Jerseyのために設計された世代別ごみ集めである．大きな ヒープを図2.10の(a)のようにOLD，reserve，NEWの3つに分割する．reserveの右壁は，reserve の左壁（つまりOLDの右壁）と，ヒープの右端の中央に設定する．これにより，仮にNEWの全て のオブジェクトが生存している場合でも破綻が起きない．freeを使い切ってごみ集めが起きる度に(b) のようにNEWの生存オブジェクトはreserveの先頭（左端）のXに救出されOLDにつけられる．

(c)のようにOLDがいっぱい（ヒープの半分を超える）になると，(d)のようにOLD’に救出され，

xとOLD’がヒープの先頭に移動される．この方式の興味ある点は，OLDのオブジェクトをコピー

OLD