インクリメンタルなメジャーコレクションを行う世代別GC

IPSJ

Bibliographic Information

Other Title
  • Generational Garbage Collector with Incremental Major Collection

Search this article

Abstract

マークスイープアルゴリズムに基づくインクリメンタルガーベジコレクタは，停止時間をごく短時間に抑えることが可能であるが，効率が悪く，CPU時間が増加する．この性能低下の原因は，細かすぎる粒度でGCを起動することによるコンテキスト切替えのオーバへッドと，アロケーション処理がインライン展開できないことによる．一方，世代別ガーベジコレクタは高いCPU効率が得られ，また平均の停止時間は比較的短いが，旧世代領域のGC（メジャーコレクション）の際には長い時間にわたって計算処理が停止してしまい，リアルタイム応用には適さない．我々は，新世代領域のGC（マイナーコレクション）のたびに，インクリメンタルに旧世代領域のガーベジコレクションを行う新しいGCアルゴリズムを提案する．インクリメンタル化のために必要となるライトバリアは，世代別ガーベジコレクタの実装にいずれにせよ必要なライトバリアと同じ仕組みを利用する．このアルゴリズムにより，通常の世代別ガーベジコレクタに近い効率を保ちながら，停止時間を短く保ち，ガーベジコレクタのリアルタイム性を向上させることができる．

Incremental garbage collectors based on mark-sweep algorithms can minimize the pause caused by garbage collection at the expense of increased CPU time. The performance degradation is due to context switch overhead of GC invocation of too fine granularity, and the fact that allocation operations cannot be inlined. Generational collectors, on the other hand, can achieve high efficiency and relatively short average pause time, while occasional long pause for collection of old generation space (major collection)makes these collectors unsuitable for real-time applications. We propose a new GC algorithm which incrementally reclaims old generation space every time a minor collection is performed. Write barrier for generational collector is also used for incremental collection. With this algorithm, we can improve real- time response of garbage collector by keeping pause time short, with little overhead added to ordinary generational collectors.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top