著者

小池 龍信 岩井 輝男 中西 正和

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.7, pp.1-8, 1999-08-15

参考文献数

8

被引用文献数

1

---

ごみ集め処理(GC)を必要とする言語がいくつか存在し Lisp言語などのような関数型言語処理系にはGCが不可欠である.これらの処理系は 実時間性に向いてないとされてきた.理由としては GCを行っている時に処理が一時中断することがあげられる.この中断時間をできるだけ減らすための研究がなされている.このようなGCを実時間GCと呼び その中の一つにTreadmill GCがある.Treadmill GCは複写式GCを改良したものである.このGCでは全てのオブジェクトを双方向環状リストで連結し GCは複写によるオブジェクトの移動ではなく 双方向ポインタのつけかえ(relink)で実現する.これにより複写式GCの利点を保持し さらにオブジェクトの移動を行わないため複写式GCで問題となるreadバリアが解消されている.Treadmill GCの時間的コストは生きているオブジェクトの数に比例する.よって生きているオブジェクトが多い場合には実時間性が乏しい.この問題点の解決方法として世代別GCの考えを取り入れた.世代別GCの考え方は ある程度生き続けたオブジェクトは半永久に生き残り また生成して間もないオブジェクトの殆どは寿命が短いというものである.本稿では 世代別GCの考えを取り入れたTreadmill GC(Opportunistic Treadmill GC)の提案及びその実現方法 さらにいくつかのベンチマークアプリケーションを実行し その実験結果から1回のGC時間 総実行時間を削減したことについて報告を行う.Real-time Garbage Collection is a study that makes pause time of GC as short as possible. Treadmill GC, one of the real-time GC algorithms, is improved Copying GC. In this scheme all objects are linked by cyclic doubly-linked lists (treadmill). Objects are not removed by copying, and objects' pointer of treadmill are relinked. This means that advantages of Copying GC are preserved, solving read barrier problem at the same time. We propose the "Opportunistic Treadmill GC", which is a Garbage Collection technique that the collector traces only short-life objects, setting long-life objects out of collector's view. There is a strong evidence that the overwhelming majority of objects die very young, although a small proportion may live for a long time. In Treadmill GC, pause time of GC is mostly the time for relinking alive objects. Especially in the original Treadmill GC, collector has to relink all alive object. However in Opportunistic Treadmill GC, collector only has to relink short-life objects of all alive objects. Hence we can make a pause time of GC shorter and improve effective real-time GC. Then we implemented the original Treadmill GC and Opportunistic Treadmill GC on an incremental garbage collector of the Lisp1.5 based system, and showed how efficient it is by a few experiments, in comparison with the original Treadmill GC, we could decrease average time of one GC execution as well as total execution time. We refined incremental GC so that the real-time systems with our Opportunistic Treadmill GC will be more useful.