An Incremental Garbage Collector Based on a Lazy Garbage Collection Scheme

使用済みになったデータオブジェクトの回収を遅延させて行う圧縮型ガーベッジコレクション（mark-and-compact GC）の実時間化とその評価について述べる．回収の遅延とは最新に作られたオブジェクトが存在する領域の回収処理を次回に延ばすことであり，比較的短い生存期間のオブジェクトを圧縮処理から除くことができる．さらに，世代別GCに見られるようにGCを経たオブジェクトを殿堂入りさせると，ある上下限で規定される生存期間を持つオブジェクトのみが圧縮処理の対象となり，圧縮処理の軽減が図られることが停止回収型の実装から示されている．このGCの実時間化では，write-barrierを使用するsnapshot-at-the-beginningとオブジェクトの複製圧縮の各技法が使用されている．前者は，read操作の多い純計算側の負荷を確実に減らすとともに，最新のオブジェクトが未処理で残るような遅延GCにはむしろ効果的に機能する．後者は一度に圧縮するオブジェクトを移動先にその複製が作られる範囲に限定することで，圧縮処理中でのGCの中断を可能にする．GC回数の増加につれて，圧縮済オブジェクト群の領域と最新のオブジェクトを含む未処理のオブジェクト群の領域の間には1つの空き領域が生まれる．これが飢餓状態の回避に役立つ．評価実験は，GCと純計算側のmutatorをコルーティン化して行った．そして，数種のLispプログラムの実行結果に基づく本GCの評価を述べる．

The implementation and evaluation of an incremental garbage collector based on mark-and-compact garbage collection (GC)are presented that put collection of unused data objects off. Such lazy GCdoes not scavenge a space where new objects are allocated and put collection of unused objects of the space off for a one GCcycle, so that relatively short-lived objects are omitted from GCprocessing. In addition to this, the promotion that long-lived objects with GC experiences are omitted from future GC, as seen in generational GC, makes objects with a certain lifetime processed. The decrement of objects being compacted is shown by a prototype of stop-and-collect version. The incremental version uses two techniques, namely, snapshot-at-the-beginning using write-barrier and duplication of objects. The former is less costly in time for coordination with mutator that performs many read operations, and has good effects on the lazy GCwhere new objects remain unprocessed. The latter is to relocate objects in use stepwise so that both the relocated and original objects exists till the relocated objects are updated, and this enables the GCto break it process at any stage. According as the GCproceeds, a continuous empty space appears between the space of compacted objects and the space of unprocessed objects. This space is useful to avoid starvation. The analysis of the GCon its performance is done by implementing co-routine made of the GCand the mutator routines, and obtained from the execution of typical Lisp programs.