Reduction of Pause Time due to Snapshot Parallel GC

IPSJ Web Site 1 Citations 13 References

Bibliographic Information

Other Title
  • Snapshot型並列GCにおけるルート挿入時間の削減
  • Snapshotガタ ヘイレツ GC ニ オケル ルート ソウニュウ ジカン ノ サクゲン

Search this article

Description

並列GCは リスト処理の実時間処理 (無停止処理) の実現が可能なGC方法である. snapshot 型アルゴリズムの並列GCでは ルート挿入時点で生きていたオブジェクトのsnapshotをとるため ルート挿入時にはmutatorとcollectorとで同期を取り mutatorのリスト処理を一時中断してmutatorのルート挿入を行わなければならない. 1回の停止時間をできるだけ小さくするためには 同期の時間を削減するか mutatorのルート挿入時間を削減するかのいずれかである. 同期の時間はハードウェアとオペレーティングシステムの機能に関係し 停止時間を減少させる事が難しい. 我々はsnapshotを取るためのルート挿入は mutatorがルートを書き換えるまで行う必要がない事に着目した. 書き換えの起こったルートの含まれるぺージだけのルート挿入を行うことで 一般的なsnapshot型並列GCのルート挿入によるmutatorの停止時間を減らすアルゴリズムを提案する. 並列Lispへの拡張性を考えこの並列GCの手法を用いて実装し実験した結果 GC時のルート挿入による停止時間が一定時間内に抑えられることが確認された. この結果は 実時間GCの実用化に大きく貢献すると考えられる.

Parallel garbage collection enables list processing in realtime (non stop processing). The garbage collection (GC) of snapshot algorithm is one of parallel GC. It is necessary for this GC to use the mutual exclusion between mutator and collector for taking the snapshot at root insertion, and to pause temporarily the mutator, and to make mutator do root insertion. For one pause time is as short as possible, it is necessary to shorten each the time of mutual exclusion or root insertion. The time of the mutual exclusion depends on hardwire and operating system, and it is difficult to shorten the pause time. We note that the root insertion is not necessary until the mutator rewrites root area. We propose the method of decreasing pause time that approaches that only pages that is rewritten are copied. For the expansion to parallel Lisp we implement this method, experiment, and obtain that the pause time of mutator is less than certain constant time. The GC with this method contributes to practical use realtime GC.

Journal

Citations (1)*help

See more

References(13)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top