著者

川又 晃 羅翔 寺島 元章

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.2, pp.105-105, 2000-03-15

---

当研究室で開発した便宜的ガーベッジコレクション(ccasional G)の並行化とその実装について述べる.便宜的GCとは,リスト処理などの純計算側が消費したヒープ中の最新の使用域のみを対象として使用中オブジェクトの圧縮(liding compactio)処理を行うものである.その効果として,GC処理時間の短縮化と,ヒープ使用の節約に伴うワーキングセットの縮小で純計算時間の短縮も図れることが停止回収型の実装から示されている.この便宜的GCの並行化は,毎回行われるGC処理の実時間(ealtim)化と定期的に行われるGCの並列(oncurren)化とからなる.前者は通常の掃除をこまめに行うことを,後者は時間のかかる大掃除を別個に行うことを意味する.GCの圧縮処理の実時間化に必要な,write?barrierと輪切り複写の機能は,そのまま並列化にも適用できる.並列化ではこれらに,排他制御が付加されるだけである.輪切り複写とは,一度に圧縮するオブジェクトを移動先にその複製が作られる範囲に限定することであり,GCの圧縮処理中での中断を可能にする.また,write?barrierはオブジェクト参照に伴う純計算側の負荷を減らす.純計算側はLispの一方旨であるPHLを用い,GC側はスレッドライブラリを利用したコルーティンという汎用的な環境下で実装を行った.数種のLispプログラムの実行結果から得られた本GCの実時間特性についても述べる.The design and implementation ofincremental occasional garbage collection are presented. The occasional garbage collectionis a new type of garbage collection(GC)based on a "mark-and-compact" or sliding compaction scheme.The GC focuses its task of scavenging on most recently generated data object to gain time, and its good performance is shown by a prototype of "stop-and‐collect" version. The incremental occasional garbage collection is made up of two features:"realtime"and"concurrency''. The former is performed usually, while the latter is periodically to gain more spaces.They need common schemes of a write barrier and a coherent copy.The write barrier is less costly in time for coordination than a read barrier, and the coherent copy makes each data object consistent upon its relocation. The concurrency needs exclusive control in addition to them, so that these two features are implemented effectively in the GC.The incrementaI GC is implemented on a multi‐processor machine with shared memory by using(POSI・ス)thread library that makes it portable. The analys of the GC on its performance is done by using our experimental data obtained from the execution of typical Lisp programs.