環状分散ゴミ集めのための局所ゴミ集めの最小限の拡張

概要

論文の詳細を見る
多くの分散ゴミ集めでは, 環状分散ゴミの検出は1)遠隔参照から到達可能なものすべて, 2)遠隔参照からのみ到達可能なもの, という2つの情報を利用して行われる.本発表では, この情報を局所ゴミ集めから抽出できるようにするための最小限の拡張を提案する.我々の提案する拡張を利用することにより分散ゴミ集めを局所ゴミ集めとを独立に実装できるが, このことは次の利点をもたらす.1)分散ゴミ集めに必要な情報を局所ゴミ集めから得るので効率が良い.2)分散ゴミ集めは同じ拡張を持つ局所ゴミ集めの上で動作可能である.3)分散ゴミ集めの方式に局所ゴミ集めが依存しないため保守が容易である.提案する拡張は既存の局所ゴミ集めに対して最小限のものであり, 種々の局所ゴミ集めで簡単に実現できる.我々は, Sun JDK1.2の局所ゴミ集めに提案する拡張を実装し, それを用いて山本のアルゴリズムを変更した分散ゴミ集めを実装した.局所ゴミ集めの拡張により生じたオーバーヘッド測定の結果, 我々の提案する枠組みは十分効率の良いものであることが分かった.
2001-03-15